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 }

 

 
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 14:08
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务