题解：CF1466C Canine poetry

题意

给你一个字符串，让你修改一些位置，使得这个字符串中不包含回文子串（一个字母的那种不算）

分析

这道题该怎么做呢？让我们思考一下。

先来考虑发现长度为 2 的回文子串。我们只需要改掉其中的一个字符就可以捣毁这个回文子串。

其次考虑长度为 3 的回文子串。如果发现一个字符和后面的第二个字符相等，那么就是一个回文子串，我们也只需要修改两侧的字符的其中一个就可以捣毁这个回文串。

如果更多的呢？我们已经捣毁了长度为 2，长度为 3 的回文子串，那么更长的回文子串中肯定包含这些子串，这些子串已经不是回文子串了，更长的回文子串肯定不能形成。

总结：我们只要找到长度为 2 和长度为 3 的回文子串，找到其中的一个字符改掉就可以了。

具体实现中，最好做一个标记，标记哪个字符有没有被改过更好。

代码

#include<bits/stdc++.h>
using namespace std;
int t;
string s;
int main(){
	cin>>t;
	while(t--){
		cin>>s;
		int ans=0;
		bool vis[100005]={0};
		for(int j=0;j<s.size()-1;j++){
			if(s[j]==s[j+1]&&!vis[j]){
				ans++;
				vis[j+1]=1;
			}
			if(s[j]==s[j+2]&&!vis[j]){
				ans++;
				vis[j+2]=1;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

TIPS

记得清空上一次保留的数据（如果你是在循环中定义的变量，也可以不用，但是函数中定义的数组的初始值不好确定）