题解Codeforces Round #598 (Div. 3)（CF1256）

昨晚忘记有比赛了，今早补题。

A：x*n+y=s是否有解。。弱智题懒得讲了。

 1 #include<stdio.h>
 2 #define it register int
 3 #define il inline
 4 #define Max(a,b)(a>b?a:b)
 5 long long a,b,n,s,T,left;
 6 il void fr(long long &num){
 7     num=0;char c=getchar();int p=1;
 8     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
 9     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
10     num*=p;
11 }  
12 int main(){
13     fr(T);
14     while(T--){
15         fr(a),fr(b),fr(n),fr(s),left=s-a*n;
16         if(left>=0) left<=b?puts("YES"):puts("NO");
17         else left=s-s/n*n,left<=b?puts("YES"):puts("NO");
18     }
19     return 0;
20 }

View Code

B：先从后往前扫一遍把小的换到前面去再从前往后扫一遍把大的换到后面去。

 1 #include<stdio.h>
 2 #define it register int
 3 #define il inline
 4 const int N=1000005;
 5 il void sp(int &p,int &q){
 6     p+=q,q=p-q,p-=q;
 7 }
 8 bool tg[N];
 9 int a[N],n,T;
10 il void fr(int &num){
11     num=0;char c=getchar();int p=1;
12     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
13     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
14     num*=p;
15 }   
16 int main(){
17     fr(T);
18     while(T--){
19         fr(n);
20         for(it i=1;i<=n;++i) fr(a[i]),tg[i]=0;
21         for(it i=n;i>1;--i)
22             if(a[i]<a[i-1]) sp(a[i],a[i-1]),tg[i-1]=1;
23         for(it i=1;i<n;++i)
24             if(a[i]>a[i+1]&&!tg[i]) sp(a[i],a[i+1]),tg[i]=1;
25         for(it i=1;i<=n;++i) printf("%d ",a[i]);putchar('
');
26     }
27     return 0;
28 }

View Code

C：直接按照题意大力模拟即可。

 1 #include<stdio.h>
 2 #define it register int
 3 #define il inline
 4 const int N=1000005;
 5 int n,m,d,a[N],ans[N],s[N];
 6 il int Min(it p,it q){
 7     return p<q?p:q;
 8 }
 9 il void fr(int &num){
10     num=0;char c=getchar();int p=1;
11     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
12     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
13     num*=p;
14 }   
15 int main(){
16     fr(n),fr(m),fr(d); 
17     for(it i=1;i<=m;++i) fr(a[i]),s[i]=s[i-1]+a[i];
18     it pos=0;
19     for(it i=1;i<=m;++i){
20         it nowd=Min(d,n-(s[m]-s[i-1]+pos)+1);
21         pos+=nowd+a[i]-1;
22         for(it j=pos-a[i]+1;j<=pos;++j) ans[j]=i;
23     }
24     if(pos+d<n+1||pos-a[m]+1>n) return puts("NO"),0;
25     puts("YES");
26     for(it i=1;i<=n;++i) printf("%d ",ans[i]); 
27     return 0;
28 }

View Code

D：和B好像哦。。但是增加了次数限制而且只有01串。显然我们每次优先把前面的0换到前面去，显然我们上一次换过的0的位置到当前这个0中间所有的都是1，所以只要把这个0挪到pos+1就可以了。然后注意m要开long long ，因为n很大。

 1 #include<stdio.h>
 2 #define it register int
 3 #define il inline
 4 const int N=1000005;
 5 int T,n;
 6 long long m;
 7 char s[N];
 8 int main(){
 9     scanf("%d",&T);
10     while(T--){
11         scanf("%d%lld%s",&n,&m,s+1);
12         for(it i=1,pos=1;m&&i<=n;++i)
13             if(s[i]=='0')
14                 if(i-pos<=m) m-=(i-pos),s[i]=s[pos],s[pos]='0',++pos;
15                 else pos=i-m,s[i]=s[pos],s[pos]='0',m=0;
16         printf("%s
",s+1);
17     }
18     return 0;
19 }

View Code

E：把一些人划分成一些组使得每组相差和最小。。太经典了好不好。。肯定dp啊。一般的思路是f[i][j]表示前i个人分到j组里面其中第i个人分到第j组。但是这题n非常大，不能二维dp。那肯定降维呗，把j那一维扔掉就行。我们看到题目中的条件“每组不得少于3人”，仔细想想，如果我们有一个6人的小组，那么我们可以把它分成3人+3人的，这并不会使答案更劣只会更优（因为中间没有必要的差我们不累加了）。于是每组的人数为3<=totsize<=5.那么我们只要把状态改成前i个人，第i个人分到人数为j的小组里。很显然我们可以先按照高度排序，这样i一定和i-1分一组或者i单独一组。那么就非常好办啦！

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 #define it register int
 5 #define il inline
 6 using namespace std;
 7 const int N=1000005;
 8 typedef long long ll;
 9 int n,ans[N],cnt,pre[N];
10 struct ky{
11     int x,id;
12     bool operator<(const ky&p)const{
13         return x<p.x;
14     }
15 }a[N];
16 ll f[N];
17 il void fr(int &num){
18     num=0;char c=getchar();int p=1;
19     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
20     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
21     num*=p;
22 }   
23 int main(){
24     fr(n);
25     for(it i=1;i<=n;++i) fr(a[i].x),a[i].id=i;
26     memset(f,0x3f3f3f3f,sizeof(f)),sort(a+1,a+1+n),f[1]=0;
27     for(it i=1;i<=n;++i)
28         for(it j=3;j<=5;++j){
29             register ll val=f[i]+a[i+j-1].x-a[i].x;
30             if(val<f[i+j]) f[i+j]=val,pre[i+j]=i; 
31         }
32     it now=n+1;
33     while(pre[now]){
34         ++cnt;
35         for(it i=pre[now];i<now;++i) ans[a[i].id]=cnt;
36         now=pre[now];
37     } 
38     printf("%lld %d
",f[n+1],cnt); 
39     for(it i=1;i<=n;++i) printf("%d ",ans[i]); 
40     return 0;
41 }

View Code

F：首先我们知道如果S和T中字母不一样肯定不行。然后乱搞一下我们会发现只要S或T中的某个字母出现两次以上肯定可以翻转得到（自己画画）。对于剩下的情况也就是s和t中的每个字母都只出现过一次，我们每次累加的时候从当前字符开始往后找所有比它字典序大的字符进行和的统计以确定是否可以翻转。很水但是注意下细节。

 1 #include<stdio.h>
 2 #define it register int
 3 #define il inline
 4 const int N=1000005;
 5 int a[N],b[N];
 6 char s[N],t[N];
 7 int n,T;
 8 long long s1,s2;
 9 int main(){
10     scanf("%d",&T);
11     while(T--){
12         scanf("%d%s%s",&n,s+1,t+1);
13         for(it i=1;i<=26;++i) a[i]=b[i]=0;s1=s2=0;
14         for(it i=1;i<=n;++i){
15             ++a[s[i]-'a'+1],++b[t[i]-'a'+1];
16             for(it j=s[i]-'a'+1;j<=26;++j) s1+=a[j];
17             for(it j=t[i]-'a'+1;j<=26;++j) s2+=b[j];
18         }
19         register bool fl=1;
20         for(it i=1;i<=26;++i) if(a[i]!=b[i]) fl=0,i=27;
21         if(!fl){puts("NO");continue;}
22         fl=0;for(it i=1;i<=26;++i) if(a[i]>=2) fl=1,i=27;
23         if(fl){puts("YES");continue;}
24         (s1-s2)&1?puts("NO"):puts("YES");
25     }
26     return 0;
27 }

View Code

感觉最近一场Div2和这场Div3题目都挺没意思的，一眼题。。希望以后能多出几套高质量的题！