Codeforces Round #615 (Div. 3)补题

发表于 更新于 分类于 阅读次数：

2020年1月24日，武汉加油，全国医疗工作者加油。
可能是我这三个月以来打的最菜的一场了……
Codeforces Round #615 (Div. 3)

本场关键词

读题、贪心、数学、乱搞、树的直径

A. Collecting Coins

给你$n$和$a,b,c$，问你是否可以将$n$完全分配给$a,b,c$，使分配后三者数量相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f;
int main()
{
    ll n,t,a[3];
    cin>>t;
    while(t--)
    {
        for(int i=0;i<3;i++)
            cin>>a[i];
        cin>>n;
        sort(a,a+3);
        int dis=a[2]-a[1]+a[2]-a[0];
        if(n>=dis&&(n-dis)%3==0)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}

B. Collecting Packages

题意

在网格上有n个宝箱，第$a_i$个坐标为$(x_i,y_i)$，机器人初始坐标为$(0,0)$，只能向右或向上移动，问是否可以拿到全部宝箱，若可以，输出移动路线（优先选择向右移动）。

思路

按$x$轴排序，然后贪心

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005,inf=0x3f3f3f3f;
struct node
{
    int x,y;
} a[maxn];
bool cmp(const node&a,const node&b)
{
    return a.x<b.x;
}
bool cmp2(const node&a,const node&b)
{
    return a.y<b.y;
}
int main()
{
    ll n,t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i].x>>a[i].y;
        sort(a+1,a+n+1,cmp2);
        stable_sort(a+1,a+n+1,cmp);
        bool flag=1;
        int nx=0,ny=0;
        string ans;
        for(int i=1;i<=n;i++)
        {
            if(a[i].y<ny||a[i].x<nx)
            {
                flag=0;
                break;
            }
            while(a[i].x>nx)
            {
                nx++;
                ans+='R';
            }
            while(a[i].y>ny)
            {
                ny++;
                ans+='U';
            }
        }
        if(flag)
        {
            cout<<"YES\n"<<ans<<endl;
        }
        else
            cout<<"NO\n";
    }
    return 0;
}

C. Product of Three Numbers

woc这题我演了两个小时，最后发现是没开根号的锅。

题意

给你一个整数$n$，找到三个大于等于2的不同整数$a,b,c$，使得$abc=n$，输出$a,b,c$。

思路

先打1e5内质数表，在质数表内查询$n$的第一个因数$a$，如果没找到，则$n$无法分解。
然后在$(a,\sqrt{n}\ ]$枚举，找到第二个因数$b$，此时$\frac{n}{ab}$即为第三个因数$c$，判断$c$是否大于$b$，若不大于$b$，则无解，否则输出答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005,inf=0x3f3f3f3f;
const int MAXN=1e5+3;
ll prime[MAXN+1],primesize;//primesize是素数的个数,prime[i]存着第i个素数
bool isprime[MAXN+1];
void getlist(void)
{
    memset(isprime,1,sizeof(isprime));
    primesize=0;
    isprime[1]=false;
    for(int i=2;i<=MAXN;i++)
    {
        if(isprime[i])
            prime[++primesize]=i;
        for(int j=1;j<=primesize&&i*prime[j]<=MAXN;j++)
        {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)
                break;
        }
    }
}
int main()
{
    ll t,n;
    getlist();
    scanf("%I64d",&t);
    while(t--)
    {
        scanf("%I64d",&n);
        bool flag=0;
        vector<ll>ans;
        int cnt=0;
        for(ll i=1;i<=primesize;i++)
        {
            if(n%prime[i]==0)
            {
                n/=prime[i];
                cnt++;
                ans.push_back(prime[i]);
                break;
            }
        }
        if(!cnt)
            printf("NO\n");
        else{
            ll lim=sqrt(n)+1;//开根号!!!
            for(ll i=ans[0]+1;i<=lim;i++)
            {
                if(n%i==0)
                {
                    ans.push_back(i);
                    n/=i;
                    if(n>ans[1])
                    {
                        ans.push_back(n);
                        flag=1;
                        break;
                    }
                    else
                        break;
                }
            }
            if(flag)
            {
                printf("YES\n");
                for(auto &i:ans)
                    printf("%I64d ",i);
                printf("\n");
            }
            else
                printf("NO\n");
        }
    }
    return 0;
}

D. MEX maximizing

又是读不懂题的一天。
赛中以为只能在询问时挑选集合中一个元素并将其加减$x$一次，然后又开始演起来了……

题意

$MEX$运算为不在集合中的最小非负整数。
一开始，你有一个空集合$a$和一个整数$x$。$q$次询问，第$j$次询问给出一个整数$y_j$，并将$y_j$加入集合中。
您可以选择集合中的任意元素$a_i$，并将其加减$x$任意次（只要保证不为负）。
对于第$j$个询问，输出加入$y_j$后集合$a$的最大$MEX$。

思路

数论，贪心。
因为可以加减$x$的任意倍，所以集合中的元素只与$x$的余数有关。
$ans$即为当前集合$a$的$MEX$，可以发现$ans$一定不会变小，初始为0。
存储的时候只存储对应余数的个数，所以当余数为$ans%x$的数量不为0时，可以将一个$ans%x$通过增加特定个$x$来得到元素$ans$，此时$MEX$在原来的基础上$+1$，当$ans\le x$时也是如此。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+5;
int arr[maxn];
int main()
{
    int q,x,y,ans=0;
    cin>>q>>x;
    while(q--)
    {
        cin>>y;//x可以增减任意次
        arr[y%x]++;//那么只和余数有关
        while(arr[ans%x]>0)//
        {
            arr[ans%x]--;//拿出一个ans%x变为ans
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

E. Obtain a Permutation

思路很清晰……就是太麻烦……Orz，还是码力不够……

题意

给你一个$n\times m$矩阵，每次你可以选择一下一个操作：

  • 选择任何一个元素，并将其变为$[1,nm]$范围内任何一个数。
  • 将某一列第一行元素放到最后一行。

求变为要求形式矩阵最小操作次数。

思路

静态内存开不下……要开vector存数组。
很明显列和列之间不会相互影响，所以每一列单独计算最优方案即可。
对于第$i$列，$O(n)$枚举符合该列要求的元素到符合位置的步长，并且用$cnt[j]$记录步长为$j$的$i$列元素个数。该列的贡献即为移动的代价+修改的代价最小值，详见代码……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,inf=0x3f3f3f3f;
vector<int> a[maxn];
int cnt[maxn];
int main()
{
    int n,m,tmp,ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        a[i].push_back(0);
        for(int j=1;j<=m;j++)
        {
            cin>>tmp;
            a[i].push_back(tmp);
        }
    }
    for(int i=1;i<=m;i++)//每一列单独计算
    {
        int now=inf;
        for(int j=0;j<=n;j++)
            cnt[j]=0;//向上移动i位符合的元素
        for(int j=1;j<=n;j++)//第j行元素向上移动x行到合适位置
        {
            if(a[j][i]<1||a[j][i]>n*m||(a[j][i]-i)%m!=0)//不符合这一列的元素
                continue;
            int sup=(a[j][i]-i)/m+1;//应该在的行数
            cnt[(j-sup+n)%n]++;
        }
        for(int j=0;j<n;j++)
            now=min(now,j+n-cnt[j]);
        ans+=now;
    }
    cout<<ans<<endl;
    return 0;
}

附：TLE代码

很明显的思路……复杂度$O(n^3)$，妥妥的TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,inf=0x3f3f3f3f;
vector<int> a[maxn];
int n,m;
int jud(int col,int k)//第col列向上窜k个的代价
{//a[i][j]应为(i-1)*m+j
    int ret=0;
    for(int i=1;i<=n;i++)//枚举第i行
    {
        int now=(i-k+n)%n;//窜之后的所在行
        if(now==0)
            now=n;
        if(a[i][col]!=(now-1)*m+col)
            ret++;
    }
    return ret;
}
int main()
{
    int tmp,ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        a[i].push_back(0);
        for(int j=1;j<=m;j++)
        {
            cin>>tmp;
            a[i].push_back(tmp);
        }
    }
    for(int i=1;i<=m;i++)//每一列单独计算
    {
        int now=inf;
        for(int j=0;j<n;j++)
            now=min(now,jud(i,j)+j);
        ans+=now;
    }
    cout<<ans<<endl;
    return 0;
}

F. Three Paths on a Tree

Orz，读题又双叒叕失误，这种图论题我也能演起来……

题意

在树上寻找三个节点$a,b,c$，使得$a,b,c$三个节点间的路径最长。

思路

树上距离+树的直径。
很显然三条路径$(a,b),(b,c),(a,c)$有一条为树的直径（我说显然是因为我不会证明呜呜呜）。
先任选一个点，进行BFS，找到树的直径的一端，记录为$a$，再以$a$为源点进行BFS，求出树的直径另一端点$b$，以及树上所有点到$a$的距离，记录到$rec1[maxn]$，再以$b$为源点进行BFS，求出树上所有点到$b$的距离记录到$rec2[maxn]$。
此时我们知道了书上任意一节点到$a$和$b$的距离，可以枚举得到$c$，注意$c$不能为$a$或$b$即可。
$ans=\frac{dist(a,b)+dist(a,c)+dist(b,c)}{2}$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
vector<int>G[maxn];
int root=1,dist[maxn],rec1[maxn],rec2[maxn];
bool vis[maxn];
void bfs(int rt)
{
    memset(vis,0,sizeof(vis));
    queue<int>QAQ;
    QAQ.push(rt);
    dist[rt]=0;
    vis[rt]=1;
    while(!QAQ.empty())
    {
        int u=QAQ.front();
        if(dist[u]>dist[root])
            root=u;
        QAQ.pop();
        for(auto &v:G[u])
        {
            if(vis[v])
                continue;
            vis[v]=1;
            dist[v]=dist[u]+1;
            QAQ.push(v);
        }
    }
}
int main()
{
    int n,u,v;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(1);//找到一个端点a
    int a=root,b,c=0,ans;
    bfs(root);//求出直径,找到另一个端点b
    b=root,ans=dist[root];
    memcpy(rec1,dist,sizeof(int)*(n+1));//节点到a距离
    bfs(root);//求出节点到b距离
    memcpy(rec2,dist,sizeof(int)*(n+1));
    for(int i=1;i<=n;i++)
    {
        if(i!=a&&i!=b&&rec1[i]+rec2[i]>rec1[c]+rec2[c])
            c=i;
    }
    ans=(ans+rec1[c]+rec2[c])/2;
    cout<<ans<<endl;
    cout<<a<<' '<<b<<' '<<c<<endl;
    return 0;
}

2020年1月24日17点27分