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...

 #include<bits/stdc++.h>

 using namespace std;

 const int amn=5e5+;

 char mp[amn];

 int a[amn],c[];

 int main(){

     int n,k;

     ios::sync_with_stdio();

     cin>>n>>k;

     for(int i=;i<=n;i++){

         cin>>mp[i];

         a[i]=mp[i]-'A'+;

     }

     int ans=,c1=,c2=;

     if(k==){       ///k==2时必定是奇偶位不相同，要选一个最少改变方案，所以要知道奇位放A要改变的数多还是偶位放A要改变的数多

         for(int i=;i<=n;i++){  /// 我们先假设奇位为A，偶位为B，因为有可能合法情况是偶位为A，奇数位为B，所以最后要比较哪个不合法的数量少，这样更改少的那个才能得到最少改变方案，故下面统计不合法数，

             if(i%==){     ///若偶位为A，则A的不合法数加1，否则B的不合法数加1

                 if(mp[i]=='A')c1++;

                 else c2++;

             }

             else{           ///若偶位为A，则B的不合法数加1，否则A的不合法数加1

                 if(mp[i]=='A')c2++;

                 else c1++;

             }

         }

         ans=min(c1,c2); ///选一个最小不合法数，得到最少改变方案

         for(int i=;i<=n;i++){

             if(ans==c1){    ///若偶数位为A是不合法的，要将奇位变为A，偶位变为B

                 if(i%)

                     mp[i]='A';

                 else

                     mp[i]='B';

             }

             else{

                 if(i%)     ///若奇数为位A是不合法的，要将偶数位变为A，奇数位变为B

                     mp[i]='B';

                 else

                     mp[i]='A';

             }

         }

     }

     else{

     a[n+]=;

     memset(c,,sizeof c);

     bool f=,d=;

     int fr=,ta=,frc,mic,tac,it,cc;

     for(int i=;i<=n;i++){

         if(a[i]==a[i-]){

             d=;

             if(fr>ta){

                 fr=i-;

                 if(i->=){

                     frc=a[fr-];//cout<<frc<<'!'<<endl;

                     c[a[i]]=c[frc]=;

                 }

                 else{

                     c[a[i]]=;

                     f=;

                 }

                 mic=a[i];

                 ta=i+;

                 tac=a[ta];

                 c[tac]=;

             }

             else{

                 ta=i+;

                 tac=a[ta];

                 c[tac]=;

             }

                 //printf("i:%d fr:%d ta:%d\n",i,fr,ta);

                 if(!f&&i==n){

                     ans+=(ta-fr)/;

                     it=fr+;

                     cc=frc;

                     while(it<ta){

                         a[it]=cc;

                         mp[it]=a[it]-+'A';

                         it+=;

                     }

                     break;

                 }

         }

         else if(d){

             //printf("i:%d fr:%d ta:%d tac:%d\n",i,fr,ta,tac);

             d=;

             ans+=(ta-fr)/;

             if(f){

                 cc=tac;

                 if(ta>n)

                     for(int i=;i<=k;i++){

                         if(!c[i]){

                             cc=i;

                             break;

                         }

                     }

                 it=ta-;

                 while(it>){

                     a[it]=cc;

                     mp[it]=a[it]-+'A';

                     it-=;

                 }

                 f=;

             }

             else{

                 cc=frc;

                 //printf("---\ni:%d frc: %d tac: %d\n",i,frc,tac);

                 //for(int i=1;i<=26;i++)cout<<c[i]<<' ';

                 //cout<<"\n---\n";

                 if(frc==tac){

                     for(int i=;i<=k;i++){

                         if(!c[i]){

                             cc=i;

                             break;

                         }

                     }

                 }

                 //cout<<i<<'?'<<cc<<endl;

                 memset(c,,sizeof c);

                     it=fr+;

                     while(it<ta){

                         a[it]=cc;

                         mp[it]=a[it]-+'A';

                         it+=;

                     }

             }

             fr=ta;

             ta--;

         }

     }

     if(f){

         ans+=(ta-fr)/;

         for(int i=;i<=k;i++){

                         if(!c[i]){

                             cc=i;

                             break;

             }

         }

         memset(c,,sizeof c);

                     it=fr+;

                     while(it<ta){

                         a[it]=cc;

                         mp[it]=a[it]-+'A';

                         it+=;

                     }

             fr=ta;

             ta--;

     }

     }

     cout<<ans<<endl;

     cout<<mp+<<endl;

 }

巴特西

Codeforce219C-Color Stripe

最新文章

热门文章