题解：P10368 「LAOI-4」Colors

· · 题解

「LAOI-4」Colors

题目大意

给定一个长度为 n 的字符串 A，如果 A_{i-1} = A_{i+1}，则称 A_i 为「可消除的」。定义一次操作为：消除 A 中所有「可消除的」字符。输出操作 k 次后的 A。

题目思路

首先，我们可以观察到，对于给定的字符串，经过一定次数的操作后，字符串会进入一个循环，不断重复出现相同的状态。我们可以利用这个特点，先找到循环的起点和长度，然后直接计算出第 k 次操作后的字符串。

具体步骤如下：

  1. 使用 op 函数对字符串进行一次操作，删除所有可消除的字符。

  2. 使用哈希表 mp 来记录每个状态第一次出现的位置，使用数组 st 来存储所有出现过的状态。

  3. 不断对字符串进行操作，直到遇到一个之前出现过的状态。此时，我们就找到了循环的起点和长度。

  4. 如果 k 小于循环的起点，那么第 k 次操作后的字符串就是 st[k]。

  5. 否则，我们将 k 减去循环的起点，然后对循环的长度取模，得到在循环中的位置。最终的字符串就是 st[ls + k]。

代码

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

string op(string s) {
    int n = s.size();
    string ns;
    ns.reserve(n);

    for (int i = 0; i < n; ++i) {
        if (i == 0 || i == n - 1 || s[i - 1] != s[i + 1]) {
            ns += s[i];
        }
    }

    return ns;
}

string solve(string s, long long k) {
    unordered_map<string, int> mp;
    vector<string> st;

    while (mp.count(s) == 0) {
        mp[s] = st.size();
        st.push_back(s);
        s = op(s);
    }

    int ls = mp[s];
    int ll = st.size() - ls;

    if (k < ls) {
        return st[k];
    } else {
        k -= ls;
        k %= ll;
        return st[ls + k];
    }
}

int main() {
    int T, id;
    cin >> T >> id;

    while (T--) {
        int n;
        long long k;
        string s;
        cin >> n >> k >> s;

        cout << solve(s, k) << endl;
    }

    return 0;
}

这个算法的时间复杂度是 O(n^2)，空间复杂度是 O(n^2)。