Codeforces Round #601 (Div. 2)补题

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

Codeforces Round #601 (Div. 2)
官方题解

本场关键词

暴力、乱搞、模拟、贪心、出锅

A.Changing Volume

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;
typedef long long ll;
int main()
{
    ll a,b,t;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        ll diss=(ll)abs(a-b);
        int cnt=0;
        cnt+=diss/5;
        diss%=5;
        cnt+=diss/2;
        diss%=2;
        cnt+=diss;
        cout<<cnt<<endl;
    }
    return 0;
}

B.Fridge Lockers

这题出锅了，不过出题人迅速修改

思路

很明显所需最少锁链数为n，即所有冰箱连成环的情况。所有节点度数为2.
因为给定m<=n，当m=n时一定有解，否则无解。贪心即可。

AC的代码

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
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int no,val;
};
node a[2005];
bool cmp(const node &a,const node &b)
{
    return a.val<b.val;
}
int main()
{
    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;//n台冰箱,凑齐m条锁链
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].val;
            a[i].no=i;
        }
        if(m<n||n==2)
        {
            cout<<"-1"<<endl;
        }
        else
        {
            sort(a+1,a+n+1,cmp);
            vector<pair<int,int> > rec;
//            long long ans=2*(a[1].val+a[2].val+a[3].val);
            long long ans=a[1].val+a[n].val;
            int rem=m-n;//富余的边数
//            rec.push_back(make_pair(a[1].no,a[2].no));//最便宜三个互联,三条边
//            rec.push_back(make_pair(a[1].no,a[3].no));
//            rec.push_back(make_pair(a[2].no,a[3].no));
            rec.push_back(make_pair(a[1].no,a[n].no));
            for(int i=2;i<=n;i++)//和除了他价值最小的两个连,
            {
                ans+=a[i-1].val+a[i].val;
//                ans+=a[i].val+a[2].val;
                rec.push_back(make_pair(a[i-1].no,a[i].no));
//                rec.push_back(make_pair(a[2].no,a[i].no));
            }
            cout<<ans+rem*(a[1].val+a[2].val)<<endl;
            for(auto i:rec)
                cout<<i.first<<" "<<i.second<<endl;
            while(rem--)
                cout<<a[1].no<<" "<<a[2].no<<endl;
        }
    }
    return 0;
}

C.League of Leesins

思路

乱搞题，统计每个数字出现次数，找到起点，减去当前三元组数目，再找新产生的cnt为1的数字，一个一个输出就好。

AC代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int cnt[maxn];//统计
bool vis[maxn];
vector<int> G[maxn];
int main()
{
    int n,a,b,c;
    cin>>n;
    list<int> QAQ;
    for(int i=2;i<n;i++)
    {
        cin>>a>>b>>c;
        cnt[a]++;
        cnt[b]++;
        cnt[c]++;
        G[a].push_back(b);
        G[a].push_back(c);
        G[b].push_back(a);
        G[b].push_back(c);
        G[c].push_back(a);
        G[c].push_back(b);
    }
    int st=0,nex;
    for(int i=1;i<=n;i++)
        if(cnt[i]==1)
        {
            st=i;
            break;
        }
    stack<int>ans;
    int n1=G[st][0],n2=G[st][1];//与st连接的有两个
    if(cnt[G[st][0]]==2)
    {
        n1=G[st][0];
        n2=G[st][1];
    }
    else{
        n1=G[st][1];
        n2=G[st][0];
    }
    for(int k=1;k<=n;k++)
    {
//        printf("第%d轮,选择了%d\n",k,st);
        if(!vis[st])
            ans.push(st);//将st放入
        vis[st]=1;
        cnt[st]--,cnt[n1]--,cnt[n2]--;//去掉一个三元组
        if(k==n-2)
        {
//            if(cnt[n1]==1)
//            {
                ans.push(n1);
                ans.push(n2);
                break;
//            }
//            else{
//                ans.push(n2);
//                ans.push(n1);
//                break;
//            }
        }
//        printf("cnt[%d]=%d,n1cnt[%d]=%d,n2cnt[%d]=%d\n",st,cnt[st],n1,cnt[n1],n2,cnt[n2]);
        if(cnt[n1]==1)
        {
            st=n1;
            for(auto i:G[n1])
            {
                for(auto j:G[n2])
                {
                    if(i==j&&!vis[i])
                    {
                        n1=n2;
                        n2=i;
//                        vis[i]=1;
                        goto label;
                    }
                }
            }
        }
        else if(cnt[n2]==1)
        {
            st=n2;
            for(auto i:G[n1])
            {
                for(auto j:G[n2])
                {
                    if(i==j&&!vis[i])
                    {
                        n2=i;
//                        vis[i]=1;
                        goto label;
                    }
                }
            }
        }
        label:
            continue;
    }
    while(!ans.empty())
    {
        cout<<ans.top()<<' ';
        ans.pop();
    }
    return 0;
}

D.Feeding Chicken

题意

r行c列矩阵网格，其中一些网格有水稻，并且在里面养了k只鸡，鸡的数量不会多于水稻的格数。现在要将这些方格分给这些鸡，要求：
①一个方格必须且只能分给一只鸡
②每只鸡至少分到一个方格
③同一只鸡分到的方格必须连成一片
④领地上最多的水稻数与最少的水稻数之差尽量小
输出标注鸡的领地的矩阵。

思路

大模拟
统计R的数量，记为$rice$
分类讨论，若$rice%k$==0，则所有鸡分的稻田的数量都是一样的都为$\dfrac{rice}{k}$块稻田
若$rice%k$不为0
那么有$rice%k$只鸡分得$\ulcorner \dfrac{rice}{k} \urcorner$块稻田
剩下$k-rice% k$只鸡分得$\llcorner \dfrac{rice}{k} \lrcorner$ 块稻田
这个思想很重要，edu77的A题又出现了这个
这里采用从左上角开始蛇形分配土地，并将多余的空地分给最后一只鸡的分配方法。

代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
char mp[maxn][maxn],ans[maxn][maxn];
char index[maxn]="!abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
inline bool fun(int no,int n,int m,int sec)
{//编号,行数,列数,鸡的编号
    int y=(no+n-1)/n,x;//x轴实现向上取整
    if(y&1)//y从上到下编号
        x=no-(y-1)*n;
    else
        x=n-(no-(y-1)*n)+1;
//    if(x<1||x>n||y<1||y>m)
//        throw x;
//    printf("%d:(%d,%d)\n",no,x,y);
    ans[x][y]=index[sec];
    if(mp[x][y]=='R')
        return 1;
    else
        return 0;
}
int main()
{
    int t,r,c,k;
    cin>>t;
    while(t--)
    {
        cin>>r>>c>>k;//k只鸡
        int rice=0;
        for(int i=1;i<=r;i++)//读入
        {
            for(int j=1;j<=c;j++)
            {
                cin>>mp[i][j];
                if(mp[i][j]=='R')
                    rice++;
            }
        }
        bool diff;
        int sum1=0,sum2=0,st=rice/k,no=0;//
        if(rice%k==0)
        {
            diff=0;//分得数量全部相同
            sum1=k;
        }
        else
        {
            diff=1;
            sum1=rice%k;//分得r/k向上取整
            sum2=k-sum1;//向下取整个数
        }
        for(int i=1;i<=k;i++)//给i号鸡分地
        {
            int cnt=0;//记录分得rice
            if(sum1>0)
            {
                while(cnt<st+diff)
                {
                    if(fun(++no,r,c,i))
                        cnt++;
                }
                sum1--;
            }
            else if(sum2>0)
            {
                while(cnt<st)
                {
                    if(fun(++no,r,c,i))
                        cnt++;
                }
                sum2--;
            }
            else{//剩下的地分给同一只
                break;
            }
            while(k==i&&no<r*c)
            {
                no++;
                fun(no,r,c,i);
            }
        }
        for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
            {
                putchar(ans[i][j]);
            }
            putchar('\n');
        }
    }
    return 0;
}

E1. Send Boxes to Alice (Easy Version)

题意

洛谷页面
n个盒子，里面有0或1块巧克力，你每次可以将1块巧克力移动到相邻盒子里。保证不全为0，要求最后所有有巧克力的盒子巧克力数量不互素。求最少的移动次数。

思路

求1的总和sum，枚举每一个sum的因子（包括sum）。
将n分成一些区间，使得这一段区间的巧克力数量能被k整除。
显然当这一段区间和为k时移动代价最小，且移动到中间位置$mid$时代价最小。
这里的mid是这一段最中间的1的下标，而不是区间端点的中间值。
记录一个区间所有1的位置到临时数组rec，本轮代价$\sum\limits_{i=1}^kabs(rec_i-mid)$
记录最小代价即为答案

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100005,inf=0x3f3f3f3f3f3f3f3f;
int a[maxn];
inline int iabs(int x)
{
    if(x>=0)
        return x;
    else
        return -x;
}
signed main()
{
    int n,sum=0;
    cin>>n;
    vector<int>pos;//所有1的位置
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==1)
            pos.push_back(i);//pos[i]表示第i个1的位置
        sum+=a[i];
    }
    int ans=inf;
    if(sum==1)
    {
        cout<<"-1\n";
        exit(0);
    }
    for(int i=2;i<=sum;i++)
    {//枚举因数i,段数seg
        if(sum%i)
            continue;
//        printf("k=%d:\n",i);
        int cost=0,seg=sum/i;//因子为i时的代价,与段数
        int mid=0,cnt=0;
        vector<int>rec;
        for(int j=0;j<pos.size();j++)
        {
            if(cnt<i)//连着取i个1
            {
                rec.push_back(pos[j]);
                cnt++;
            }
            if(cnt==i)
            {
//                int mid=(rec[0]+rec[i-1])>>1;
                int mid=rec[(i-1)>>1];//mid要这样写?
                for(int k=0;k<rec.size();k++)
                {
                    cost+=iabs(rec[k]-mid);
//                    printf("从%d移到%d\n",rec[k],mid);
                }
                rec.clear();
                cnt=0;
            }
        }
//        printf("cost=%d\n",cost);
        ans=min(cost,ans);
    }
    cout<<ans<<"\n";
    return 0;
}

2019年11月28日21点36分