Codeforce219C-Color Stripe

╰+攻爆jí腚メ 2021-11-14 13:34 267阅读 0赞

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 }

转载于:https://www.cnblogs.com/brainm/p/11270244.html