【解题报告】CF DIV2 #ROUND 707 A~D
比赛链接
比赛评价：
一般性，有段时间没打了，甚至忘记多组输入hh。顺便吐槽一下翻译软件确实不行，以后还是直接看英文好了
A. Polycarp and Coins
题意
给定n,要求满足，让a和b尽量接近
思路
直接三等分，然后暴力上下微调即可（懒得动脑了hh）
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
int T;
int main(){
cin>>T;
while(T--){
int n;cin>>n;
int k=n/3;
int l=max(0,k-100);
LL d=n;
int A,B;
for(int i=l;i<=k+100;i++){
int c1=n-2*i;
if(c1>=0){
if(abs(c1-i)<=d){
d=abs(c1-i);
A=c1;B=i;
}
}
}
cout<<A<<" "<<B<<endl;
}
return 0;
}
B1. Wonderful Coloring - 1
题意
给两种颜色，n个格子然后染色，每个格子有一个字母。
要求：
染成红/绿/不染色
红色和绿色数量相同
同种颜色不能出现相同字符
尽可能多染色
思路
统计字母数量，>=2的直接算一次贡献，其余的统计数量计算为cnt，贡献为cnt/2
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
int T;
map<char,int>mp;
int main(){
cin>>T;
while(T--){
string s;cin>>s;
mp.clear();
for(int i=0;s[i];i++){
mp[s[i]]++;
}
int ans=0,cnt=0;
for(int i=0;i<26;i++){
char c='a'+i;
if(mp[c]>=2)ans++;
else if(mp[c]==1)cnt++;
}
cout<<ans+cnt/2<<endl;
}
return 0;
}
B2. Wonderful Coloring - 1
题意
变成k种颜色，其他要求相同
思路
模拟乱搞，参考这个视频代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
int T;
const int N=2e5+10;
int a[N],color[N],ls[N];
vector<int>num[N];//记录每个数字位置
int main(){
cin>>T;
while(T--){
int n,k;cin>>n>>k;
for(int i=0;i<=n;i++)num[i].clear(),color[i]=0;
for(int i=0;i<=n-1;i++){
cin>>a[i];
num[a[i]].push_back(i);
}
int kd=0;
for(int i=0;i<=n;i++){//枚举数
for(int j=0;j<=min(k,(int)num[i].size())-1;j++){//枚举当前数出现位置
color[num[i][j]]=kd+1;
ls[kd+1]=num[i][j];//某个颜色最后存储的位置,用于染不完了要还原
kd++;kd%=k;
}
}
for(int i=1;i<=kd;i++)color[ls[i]]=0;
for(int i=0;i<=n-1;i++)cout<<color[i]<<" ";
puts("");
}
return 0;
}
C. Interesting Story
题意
单词由abcde组成，给你一些单词让你组成文章，要求文章里某个字母数量比其他字母加起来还多。问最多用多少个单词
思路
只有五个字母，把每个字符串对abcde的贡献算出来，然后五个排序统计前缀和即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
int T;
const int N=2e5+10;
int a[N],b[N],c[N],d[N],e[N];
int sa[N],sb[N],sc[N],sd[N],se[N];
int ans[6];
bool cmp(int P,int Q){
return P>Q;
}
int main(){
cin>>T;
while(T--){
int n;cin>>n;
memset(a,0,sizeof a);
memset(b,0,sizeof b);
memset(c,0,sizeof c);
memset(d,0,sizeof d);
memset(e,0,sizeof e);
for(int i=1;i<=n;i++){
string s;cin>>s;
int A=0,B=0,C=0,D=0,E=0;
for(int j=0;s[j];j++){
if(s[j]=='a')A++;
if(s[j]=='b')B++;
if(s[j]=='c')C++;
if(s[j]=='d')D++;
if(s[j]=='e')E++;
}
a[i]=A-B-C-D-E;
b[i]=B-A-C-D-E;
c[i]=C-A-B-D-E;
d[i]=D-A-B-C-E;
e[i]=E-A-B-C-D;
}
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
sort(c+1,c+1+n,cmp);
sort(d+1,d+1+n,cmp);
sort(e+1,e+1+n,cmp);
memset(ans,0,sizeof ans);
for(int i=1;i<=n;i++){
sa[i]=sa[i-1]+a[i];
sb[i]=sb[i-1]+b[i];
sc[i]=sc[i-1]+c[i];
sd[i]=sd[i-1]+d[i];
se[i]=se[i-1]+e[i];
if(sa[i]>0)ans[0]++;
if(sb[i]>0)ans[1]++;
if(sc[i]>0)ans[2]++;
if(sd[i]>0)ans[3]++;
if(se[i]>0)ans[4]++;
}
int res=0;
for(int i=0;i<=4;i++)res=max(res,ans[i]);
cout<<res<<endl;
}
return 0;
}
D1. Domino (easy version)
题意
放多米诺骨牌，给nxm网格，nxm偶数。要求k个多米诺骨牌横着放，其他竖着放。问能不能放下nxm/2个（其实就是铺满）
思路
参考这个视频 我们知道如果是2x2的正方形，那么铺起来就比较方便，两个横的或者两个竖的，那么我们将情况先转化成这种偶数x偶数的情况处理
如果有奇数行，那么最后一行必须铺m/2个横着的。如果有奇数列，那么最后一列必须铺n/2个竖着的。
对于偶数成偶数的，因为横放竖放都是两两配对的，所以和k的奇偶性要相同
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
int T;
int main(){
cin>>T;
while(T--){
int n,m,k;cin>>n>>m>>k;
int ls=0;
if(n&1){n--;ls+=m/2;}
if(m&1)m--;
if(ls>k)puts("NO");
else{
ls+=(n*m)/2;
if(ls<k||(ls&1)!=(k&1))puts("NO");
else puts("YES");
}
}
return 0;
}
反思
A：
没啥说的，网再快些
B:
记得开多组输入！！！记得少用翻译软件！！！B2用了奇妙翻译，想半天没写出来呜呜。
C:
有数量对比要求，联想到做差求贡献然后看正负
D:
铺地转类问题联想到两个，把情况处理成偶数x偶数，状态压缩DP