CodeForeces 665C Simple Strings

C. Simple Strings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

zscoder loves simple strings! A string t is called simple if every pair of adjacent characters are distinct. For example ababa,zscoder are simple whereas aaadd are not simple.

zscoder is given a string s. He wants to change a minimum number of characters so that the string s becomes simple. Help him with this task!

Input

The only line contains the string s (1 ≤ |s| ≤ 2·105) — the string given to zscoder. The string s consists of only lowercase English letters.

Output

Print the simple string s' — the string s after the minimal number of changes. If there are multiple solutions, you may output any of them.

Note that the string s' should also consist of only lowercase English letters.

Examples
input
aab
output
bab
input
caaab
output
cabab
input
zscoder
output
zscoder

把重复的区间找出来,隔一个变一个。
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
#define MAX 100000
int len[2*MAX+5];
char a[2*MAX+5];
int main()
{
    scanf("%s",a);
    int l=strlen(a);
    len[l-1]=1;
    for(int i=l-2;i>=0;i--)
    {
        len[i]=1;
        if(a[i]==a[i+1])
            len[i]+=len[i+1];
    }
    for(int i=0;i<l;i)
    {
        if(len[i]!=1)
        {
            for(int j=i+1;j<=i+len[i]-1;j+=2)
            {
                if(j==i+len[i]-1)
                {
                    for(int p=0;p<26;p++)
                    {
                        if(('a'+p)==a[i]||('a'+p)==a[j+1])
                            continue;
                        a[j]='a'+p;
                        break;
                    }
                }
                else
                   a[j]=(a[i]=='z'?a[i]-1:a[i]+1);
            }
            i=i+len[i];
        }
        else
            i++;
    }
    for(int i=0;i<l;i++)
    {
        printf("%c",a[i]);
    }

    cout<<endl;
    return 0;
}




原文地址:https://www.cnblogs.com/dacc123/p/8228676.html