Codeforces1466C：CaninePoetry——思维与贪心算法的应用分析

给出一个仅由小写字母组成的字符串. 你可以把任意位置的字符修改为任意小写字母.

问: 至少进行多少次修改, 可以使得字符串中所有长度大于1的连续子串不为回文串.

解题思路

思维

长的回文串内部一定含有短的回文串, 因此如果我们想破坏一个回文串, 我们应破坏其内部的所有短回文串. 这样破的坏的才"彻底".

考虑到字符串的回文串只有两种: AA型 和 ABA型. 因此我们只需要枚举两种回文类型进行判断即可.

贪心

考虑到如果我们从前向后扫描, 如果此时出现了AA型, 则我们应当修改靠后位置的字符. 因为靠后位置可能再与其后续组成回文串. 对于ABA型, 我们同理也应当修改靠后位置的字符.

即: 如果在index位置产生了AB型回文, 则我们应修改index&＃43;1位置; 若产生了ABA型回文, 则修改index&＃43;2位置.

我们应当如何修改字符(把字符修改成什么)?

我们只需要防止修改后再出现AA型和ABA型回文串即可. 因此如果对于pos位置进行修改:
我们需要防止[pos - 1, pos], [pos - 2, pos], [pos, pos &＃43; 1], [pos, pos &＃43; 2]组成回文串.
因此我们只需要修改为不是[pos - 1, pos &＃43; 2]区间的字符即可. (如果[pos - 2, pos]形成回文, 则s[pos - 2] &＃61;&＃61; s[pos], 因此无需判断pos - 2位置)

char fact(int pos) {set<char> st;for (int i &＃61; pos - 1; i <&＃61; pos &＃43; 2; &＃43;&＃43;i) st.insert(s[i]);for (int i &＃61; &＃39;a&＃39;; i <&＃61; &＃39;z&＃39;; &＃43;&＃43;i) if (!st.count(i)) return i;}


综上所述, 我们发现我们一定可以找到一个合法字符, 使得修改pos位置后, pos位置不会再和其余位置组成回文串. 因此我们也可以简化查找这一过程, 把被修改的字符用特殊字符去替代.

AC代码

#include
#define rep(i, n) for (int i &＃61; 1; i <&＃61; (n); &＃43;&＃43;i)
using namespace std;
typedef long long ll;
const int N &＃61; 1E5 &＃43; 10;
char s[N];
int main()
{int t; cin >> t;while (t--) {scanf("%s", s &＃43; 1);int len &＃61; strlen(s &＃43; 1);int res &＃61; 0;rep(i, len - 1) {if (s[i] &＃61;&＃61; &＃39;$&＃39;) continue; //已经修改过了if (i &＃43; 2 <&＃61; len) {if (s[i] &＃61;&＃61; s[i &＃43; 2]) {s[i &＃43; 2] &＃61; &＃39;$&＃39;; //特殊字符 &＃39;$&＃39;res&＃43;&＃43;;}}if (s[i] &＃61;&＃61; s[i &＃43; 1]) {s[i &＃43; 1] &＃61; &＃39;$&＃39;; //特殊字符 &＃39;$&＃39;res&＃43;&＃43;;}}printf("%d\n", res);}return 0;
}


END