CF1466Cの题解

· · 题解

题意

给你一个字符串 s，问最少要修改多少次，才可以使得串 s 中不存在长度大于 1 的回文子串。

前传

什么是回文串呢？

举个例子：abcdcba 是一个回文串，而 cdc 是其中之一的回文子串，以此类推，还有 bcdcb , abcdcba 等。

很明显，都包含 cdc 这个字符串，但是修改 d 无意义，所以对于这个字符串，我们只需要更改 c 的为其他的字符就好了，可得到 abzdcba 或 abcdzba，显然就不是回文串了。

再举个例子，对于 cbaabc 这个字符串，我们只需要修改 a 为其他的字符就可以了。

总结：

对于一个字符串，如果出现相邻两个字符相同或于后面于后面第二个字符相同，ans++，将后面的字符标记，以防重复标记，最后输出 ans。

AC code：

#include <bits/stdc++.h>
using namespace std;

int t;
string s;

int main(){
    cin >> t;
    while(t--){
        cin >> s;
        int ans=0;
        for(int i=0;i<s.length()-1;i++){
            if(s[i]==s[i+1]&&s[i]!='0')s[i+1]='0',ans++;
            if(s[i]==s[i+2]&&s[i]!='0')s[i+2]='0',ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

应该算的上是最短的了吧。