题解：P10368 「LAOI-4」Colors

lkrqwq · 2024-04-21 08:57:23 · 题解

经过观察发现 k \le 10^{18} 且 \sum n \le 10^7。

这说明直接按题意模拟是会超时的，所以我们可以编写一个函数检测是否存在可消除字符，当没有时，我们就没有操作下去的必要了，这样可以让程序的运行效率更高。

代码如下：

#include <iostream>
#define int long long
using namespace std;
string ans;
bool chk(string x) {
    int cnt = 0;
    ans = "";
    for (int i = 0; i < x.size(); i++) {
        if (i - 1 >= 0 && i + 1 < x.size() && x[i - 1] == x[i + 1]) cnt++;
        else ans += x[i];
    }
    return cnt != 0;
}
signed main() {
    int t, id;
    cin >> t >> id;
    while (t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        while (k-- && chk(s)) {
            s = ans;
        }
        cout << s << endl;
    }
}