Codeforce219C-Color Stripe
E. Color Stripe
time limit per test
2 seconds memory limit per test
256 megabytes input
standard input output
standard output A colored stripe is represented by a horizontal row of n square cells, each cell is pained one of k colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to k to repaint the cells.
Input
The first input line contains two integers n and k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26). The second line contains n uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first k English letters may be used. Each letter represents the color of the corresponding cell of the stripe.
Output
Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.
Examples
input
Copy
6 3
ABBACC
output
Copy
2
ABCACA
input
Copy
3 2
BBB
output
Copy
1
BAB
题意：给你一行n个元素，k种颜色，要求相邻的元素颜色不能相同，输出最少改变颜色的数量和n个元素最后的颜色（若有多种可能可任意输出一种）
注意：k==2时必定是奇偶位不相同，要选一个最少改变方案，所以要知道奇位放A要改变的数多还是偶位放A要改变的数多，在训练时卡在这种情况了，
其实一开始想到了ABBA这种情况，但当时的思路是只改变相同颜色的元素，没想到不同颜色元素也能改变，所以当时就假设如果有偶数个相同颜色的元素，其两边元素颜色必不同，结果就一直wrong answer on the test 15...
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int amn=5e5+5; 4 char mp[amn]; 5 int a[amn],c[30]; 6 int main(){ 7 int n,k; 8 ios::sync_with_stdio(0); 9 cin>>n>>k; 10 for(int i=1;i<=n;i++){ 11 cin>>mp[i]; 12 a[i]=mp[i]-'A'+1; 13 } 14 int ans=0,c1=0,c2=0; 15 if(k==2){ ///k==2时必定是奇偶位不相同，要选一个最少改变方案，所以要知道奇位放A要改变的数多还是偶位放A要改变的数多 16 for(int i=1;i<=n;i++){ /// 我们先假设奇位为A，偶位为B，因为有可能合法情况是偶位为A，奇数位为B，所以最后要比较哪个不合法的数量少，这样更改少的那个才能得到最少改变方案，故下面统计不合法数， 17 if(i%2==0){ ///若偶位为A，则A的不合法数加1，否则B的不合法数加1 18 if(mp[i]=='A')c1++; 19 else c2++; 20 } 21 else{ ///若偶位为A，则B的不合法数加1，否则A的不合法数加1 22 if(mp[i]=='A')c2++; 23 else c1++; 24 } 25 } 26 ans=min(c1,c2); ///选一个最小不合法数，得到最少改变方案 27 for(int i=1;i<=n;i++){ 28 if(ans==c1){ ///若偶数位为A是不合法的，要将奇位变为A，偶位变为B 29 if(i%2) 30 mp[i]='A'; 31 else 32 mp[i]='B'; 33 } 34 else{ 35 if(i%2) ///若奇数为位A是不合法的，要将偶数位变为A，奇数位变为B 36 mp[i]='B'; 37 else 38 mp[i]='A'; 39 } 40 } 41 } 42 else{ 43 a[n+1]=27; 44 memset(c,0,sizeof c); 45 bool f=0,d=0; 46 int fr=1,ta=0,frc,mic,tac,it,cc; 47 for(int i=2;i<=n;i++){ 48 if(a[i]==a[i-1]){ 49 d=1; 50 if(fr>ta){ 51 fr=i-1; 52 if(i-2>=1){ 53 frc=a[fr-1];//cout<<frc<<'!'<<endl; 54 c[a[i]]=c[frc]=1; 55 } 56 else{ 57 c[a[i]]=1; 58 f=1; 59 } 60 mic=a[i]; 61 ta=i+1; 62 tac=a[ta]; 63 c[tac]=1; 64 } 65 else{ 66 67 ta=i+1; 68 tac=a[ta]; 69 c[tac]=1; 70 } 71 //printf("i:%d fr:%d ta:%d\n",i,fr,ta); 72 if(!f&&i==n){ 73 ans+=(ta-fr)/2; 74 it=fr+1; 75 cc=frc; 76 while(it<ta){ 77 a[it]=cc; 78 mp[it]=a[it]-1+'A'; 79 it+=2; 80 } 81 break; 82 } 83 84 } 85 else if(d){ 86 //printf("i:%d fr:%d ta:%d tac:%d\n",i,fr,ta,tac); 87 d=0; 88 ans+=(ta-fr)/2; 89 if(f){ 90 cc=tac; 91 if(ta>n) 92 for(int i=1;i<=k;i++){ 93 if(!c[i]){ 94 cc=i; 95 break; 96 } 97 } 98 it=ta-2; 99 while(it>0){ 100 a[it]=cc; 101 mp[it]=a[it]-1+'A'; 102 it-=2; 103 } 104 f=0; 105 } 106 else{ 107 cc=frc; 108 //printf("---\ni:%d frc: %d tac: %d\n",i,frc,tac); 109 //for(int i=1;i<=26;i++)cout<<c[i]<<' '; 110 //cout<<"\n---\n"; 111 if(frc==tac){ 112 for(int i=1;i<=k;i++){ 113 if(!c[i]){ 114 cc=i; 115 break; 116 } 117 } 118 } 119 //cout<<i<<'?'<<cc<<endl; 120 memset(c,0,sizeof c); 121 it=fr+1; 122 while(it<ta){ 123 a[it]=cc; 124 mp[it]=a[it]-1+'A'; 125 it+=2; 126 } 127 } 128 fr=ta; 129 ta--; 130 } 131 } 132 if(f){ 133 ans+=(ta-fr)/2; 134 for(int i=1;i<=k;i++){ 135 if(!c[i]){ 136 cc=i; 137 break; 138 } 139 } 140 memset(c,0,sizeof c); 141 it=fr+1; 142 while(it<ta){ 143 a[it]=cc; 144 mp[it]=a[it]-1+'A'; 145 it+=2; 146 } 147 fr=ta; 148 ta--; 149 } 150 } 151 cout<<ans<<endl; 152 cout<<mp+1<<endl; 153 }
查看8道真题和解析