[数据结构与算法]Codeforces Round #734 (Div. 3) 题解（A-D)

Codeforces Round #734 (Div. 3) 题解（A-D)

A. Polycarp and Coins

题目大意：

用面值为$1$和面值为$2$的硬币凑$n$元钱，使得两种硬币的数量尽量接近。

解题思路：

设1元硬币需要$a$枚，2元硬币需要$b$枚。由贪心策略可得：

1. 当$n\%3=0,a=n/3,b=n/3$
2. 当$n\%3=1,a=n/3+1,b=n/3$
3. 当$n\%3=2,a=n/3,b=n/3+1$

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int t=n%3;
        int a=n/3,b=n/3;
        if(t==1) a++;
        else if(t==2) b++;
        printf("%d %d\n",a,b);
    }
    return 0;
}

B1. Wonderful Coloring - 1

题目大意：

给一个由小写字母组成的字符串进行染色，如果满足以下条件则这种染色方案是wonderful的：

• 每个字符都应该被染成某一种颜色（红色或者绿色）或不染色
• 相同的字符不能染成同一种颜色
• 染成红色的数量应该等于染成绿色的数量
• 满足上述三个条件的情况下尽量多染色

对于给出的字符串求出在wonderful染色方案中被染成红色的数量。

解题思路：

因为有相同的字符不能染成同一颜色的限制条件，所以每种字母最多只能被染色两次。

可以求出在这个限制下一共有多少字母可以被染色，然后再将总和除二下取整即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=55;
char s[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        int num[26]={0};
        int res=0;
        for(int i=0;s[i];i++){
            num[s[i]-'a']++;
            if(num[s[i]-'a']<=2) res++;
        }
        printf("%d\n",res/2);
    }
    return 0;
}

B2. Wonderful Coloring - 2

题目大意：

$B2$和$B1$大致的题意一致，区别就在于$B2$可以染$k$种不同的颜色，并且本题从字母变成了数字，同样要满足相同的数字不能染相同的颜色和每种颜色的数量要相同。

并且这题不是要求最多染色的数量，而是要输出具体的染色方案。

解题思路：

通过上一题的启发，我们可以发现每种数字最多由最多只能涂$2$次变成只能涂$k$次，同样可以求出能被涂色的字符总和$sum$。

接下来考虑怎么给每种字母染色，我们可以采取对同一种数字进行滚动染色的方式，这样就不会使得每种字母染上相同的颜色。

要实现这种效果，我们将数字按照某种顺序排列，这样就会使得相同的数字紧靠在一起，可以用$STL$中的$priorit{y}_{q}ueue$轻松实现。

算法时间复杂度：$O(n\log n)$

代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;
int num[N],ans[N];
int n,k;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) num[i]=ans[i]=0;
        priority_queue<PII,vector<PII> > heap;
        for(int i=1;i<=n;i++){
            int t;
            scanf("%d",&t);
            num[t]++;
            if(num[t]<=k) heap.push({t,i});
        }
        int sum=heap.size()-heap.size()%k;
        int cur=0;
        while(sum--){
            PII t = heap.top();
            heap.pop();
            ans[t.second]=cur+1;
            cur=(cur+1)%k;
        }
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
        puts("");
    }
    return 0;
}

C. Interesting Story

题目大意：

如果由一个故事的组成单词中某个字符的出现次数大于其他字符出现次数的总和，那么就称这个故事是有趣的。

现在给出$n$个由$a,b,c,d,e$五种小写字母组成的单词，问如何最多能挑选多少个单词使得组成的故事的有趣的。

解题思路：

看上去数据范围很大，其实只要分别考虑五种字母作为出现次数最多的情况即可。

假设将$a$作为出现次数最多的字母，设每个字母a出现的次数为$nu{m}_a$，单词长度为$len$，那么可以将每个单词的权值设为$nu{m}_a?(len?nu{m}_a)$。然后按照从大到小的顺序排序，按照贪心策略选尽可能多的单词就可以得到将$a$作为出现次数最多的字母的最优解。

剩下四种情况同理，五种情况取一个$\max$就是最终答案。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=N*2;
int a[N][5],len[N];
char s[M];
int n;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            for(int j=0;j<5;j++) a[i][j]=0;
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            len[i]=strlen(s);
            for(int j=0;s[j];j++) a[i][s[j]-'a']++;
        }
        int res=0;
        for(int i=0;i<5;i++){
            vector<int> v;
            for(int j=1;j<=n;j++) v.push_back(a[j][i]-(len[j]-a[j][i]));
            sort(v.begin(),v.end(),greater<>());
            int sum=0,temp=0;
            for(int j=0;j<v.size();j++){
                sum+=v[j];
                if(sum<=0) break;
                temp++;
            }
            res=max(res,temp);
        }
        printf("%d\n",res);
    }
    return 0;
}

D1. Domino (easy version)

题目大意：

一个$n\times m$的二维矩阵，现在要用$\frac{n?m}{2}$张多米诺骨牌将其填满，其中多米诺骨牌有两种尺寸，分别是水平的$1\times 2$和垂直的$2\times 1$，其中水平的有$k$张。给出$n,m,k(1\le n,m\le 100,0\le k\le n?m,\frac{n?m}{2}是偶数)$，问这种情况下能否填满整个二维矩阵。

解题思路：

因为$\frac{n?m}{2}$是偶数，所以我们可以分以下几种情况讨论：

• $n$和$m$都是偶数

  1. 如果$k$是奇数，那么留下长度为奇数的两列，所以这种情况不可行
  2. 如果k是偶数，从下到下从左往右地一个个填，一定是可行的。

• $n$是奇数,$m$是偶数

  因为这种情况下会有长度为奇数的$m$列，为了使得剩下的垂直多米诺骨牌能够正确填入，必须将每列的长度修正为奇数。

  将每列长度减一需要耗费$m/2$个垂直的多米诺骨牌，修正之后就是在一个长宽都为偶数的矩阵中填入$k?m/2$个垂直多米诺的情况了，参照上一种情况的考虑，我们可以发现只要$k?m/2$是偶数就可行，否则不可行。

  综上：

  1. 如果$k\ge m/2$并且$k?m/2$是偶数，就一定可行
  2. 否则不可行

• $n$是奇数，$m$是偶数

  因为$m$是奇数，所以每行最多可以放下$(m?1)/2$个$1\times 2$的多米诺骨牌，一共可以放下$n?(m?1)/2$个，如果$k$比这个数大的话是肯定不可行的。

  在保证能放下所有的水平多米诺骨牌的前提下，我们发现因为是长度为偶数的m列，所以如果$k$是奇数的话在放完所有的水平多米诺骨牌之后肯定会有奇数的列留下，导致垂直的多米诺骨牌无法填入。

  所以：

  1. 如果$k>n?(m?1)/2$或者$k$是奇数的话，不可行
  2. 否则可行

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        if(n%2==0&&m%2==0){
             puts(k%2==0?"YES":"NO");
        }
        else if(n%2) {
            puts(k>=m/2&&(k-m/2)%2==0?"YES":"NO");
        }
        else{
            puts(k>n*(m-1)/2||k%2?"NO":"YES");
        }
    }
    return 0;
}

D2. Domino (hard version)

题目大意：

跟D1题意一致，就是在输出YES的时候要输出具体方案。

解题思路：

按照D1的思路，对于所有可行的方案从上到下从左到右先填水平的多米诺骨牌，然后再把垂直的多米诺骨牌填入即可。

注意：其中对于$n$是奇数，$m$是偶数的情况要先把最上面一层填满，再填剩下的。

每次插入的字符要与周围的字符不相同，所以就每次插入之前需要check一下。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,k;
char ans[N][N];
int nxt[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char check(int x1,int y1,int x2,int y2){
    set<char> se;
    for(int i=0;i<4;i++){
        int tx=x1+nxt[i][0];
        int ty=y1+nxt[i][1];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&ans[tx][ty]) se.insert(ans[tx][ty]);
    }
     for(int i=0;i<4;i++){
        int tx=x2+nxt[i][0];
        int ty=y2+nxt[i][1];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&ans[tx][ty]) se.insert(ans[tx][ty]);
    }
    for(int i=0;i<26;i++){
        char c='a'+i;
        if(!se.count(c)) return c;
    }

}
void draw(int x,int y,int cnt){
    for(int i=y;i<=m&&cnt<k;i+=2){
        for(int j=x;j<=n&&cnt<k;j++){
            ans[j][i]=ans[j][i+1]=check(j,i,j,i+1);
            cnt++;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!ans[i][j]){
                ans[i][j]=ans[i+1][j]=check(i,j,i+1,j);
                cnt++;
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%s\n",ans[i]+1);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        memset(ans,0,sizeof ans);
        if(n%2==0&&m%2==0){
            if(k%2) puts("NO");
            else{
                puts("YES");
                draw(1,1,0);
            }
        }
        else if(n%2){
            if(k>=m/2&&(k-m/2)%2==0){
                puts("YES");
                int cnt=0;
                for(int j=1;j<=m;j+=2) ans[1][j]=ans[1][j+1]=check(1,j,1,j+1),cnt++;
                draw(2,1,cnt);
            }
            else puts("NO");
        }
        else{
            if(k>n*(m-1)/2||k%2) puts("NO");
            else{
                puts("YES");
                draw(1,1,0);
            }
        }
    }
    return 0;
}