安徽省程序设计大赛H题 不要回文

 上一题 正确率: 42.98%42.98% 下一题 

 "

给出一个字符串S,你需要尽可能少的修改S中的字符，使得S不包含长度大 于等于2的回文子串。

输人的第一行是一个字符串S, S只包含小写字母 S的长度大于5小于300

输出使得S中不包含长度大于等于2的回文，最少要修改几个字符(可以修改
成任意字符)
 

abbaa

2

这一题我一开始没有思路，脑子比较整，后来看了题解才知道怎么做，相当于贪心从最小的情况分析，大得回文串必须是由小的回文串组成，所以我们只要把回文串最小的单位修改，就可以让字符串没有回文子串。使用num记录最小修改次数。

一共有三种情况：

（1）aa型但不是aaa型，所以只要修改第二个就可以(num + 1)

（2）aaa型，只要修改第二个和第三个就可以（num + 2）

（3）aba型只要修改最后一个（num + 1）

代码如下：

#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include

typedef long long ll;
typedef pairPII;
const int N = 1e6 + 50;

void work()
{
    string s;
    cin >> s;
    ll num = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (i + 2 < s.size() && s[i] == s[i + 1] && s[i + 1] == s[i + 2])
        {
            num += 2;
            i += 2;
        }
        else if (i + 1 < s.size() && s[i] == s[i + 1])
        {
            num += 1;
            i += 1;
        }
        else if (i + 2 < s.size() && s[i] == s[i + 2])
        {
            num += 1;
            i += 2;
        }
    }
    cout << num << 'n';
}
int main()
{
    work();
    return 0;
}