CF319D

Methyl_CH3 · 2023-01-28 14:21:11 · 题解

思路

这是一道 哈希+二分 的题目，一道黑题，但是它太简单了，建议降黄，但是由于我是我是一枚蒟蒻，在这里就不介绍哈希的做法了。在这里我使用的是模拟的做法，用字符串去操作（难道真的不是因为懒？）。这里我用一个函数 F 去模拟每一次操作，分别去枚举子串长度与始发点。如果可以找到 “XX” 字符串，则删除其一，并继续执行。否则退出循环，中止合并操作，接着输出。虽然很容易超时，但是数据实在是太水了，常数是很小的，不必要担心。相信大家看了这么多，都想知道是如何实现的，那就不多说，请看代码：

代码

#include <iostream>
using namespace std;
string s;
bool f() {
    int len = s.size();
    for (int j = 1; j <= len / 2; j++)  {//枚举子串长度
        for (int i = 0; i <= len - j * 2; i++) {//枚举子串始发点
            bool opo = 0;
            for (int k = 0; k < j; k++)//检查
                if (s[i + k] != s[i + j + k]) {
                    opo = 1;
                    break;
                }
            if (opo == 0) {//若相同则处理，不同则跳过
                s.erase(i, j);
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> s;
    while (f());//若返回值为真，继续执行直到无法操作
    cout << s;
    return 0;
}