CF319D题解

WD2c0mP · 2023-07-17 11:23:00 · 题解

题意

给定一个字符串 S，每次操作将字符串中形如XX（相邻并且相同的两个子串）变为X，问最后不能继续操作的字符串是什么。

思路

本题数据较水，暴力就可以过。

每次操作寻找相同的子串，两层循环分别枚举两个相同子串的长度、子串的起始下标，再判断两个子串是否相等，相等即删除其中一半。

通过 find_ 函数，用 while 循环来重复进行操作，如果 find_ 函数没有找到符合要求的子串，返回 false，即可结束操作。

最后输出剩下的字符串即可。

代码

#include <bits/stdc++.h>
#define ls s.size()
using namespace std;
string s;
bool find_() {
    for (unsigned i = 1; i <= ls / 2; i ++) {
        for (unsigned j = 0; j < ls - i + 1; j ++) {
            bool flag = true;
            for (unsigned k = 0;k < i;k ++) {
                if (s[j + k] != s[j + i + k]) {
                    flag = false;
                    break;
                }
            } 
            if (flag) {
                s.erase(j,i);
                return true;
            }
        }
    }
    return false;
}
int main() {
    cin >> s;
    while (find_()) {

    }
    cout << s << endl;
    return 0;
}