[JSOI2008] 火星人 题解

· · 题解

我校小朋友发现暴力能过。

注意要利用 STL 容器 string，这样插入的效率很快，但是比对那里 \mathcal O(n) 咋过的就很玄学。

原因主要是因为 STL 容器在随机数据下跑得飞快的原因。

建议加强数据。

提供一种 Hack 方法，没有修改插入操作，全是查询，然后字符串所有字符都一样，然后每次查询的位置是 1 和 \dfrac 1 2 (n+1)。

Upd：根据我的测试，我的方案并不能卡掉暴力，目测是查询次数在 10^4 次以内，每次 \mathcal O(n) 可以勉强撵过去。

而其他操作虽然是 \mathcal O(n)，但是 STL，懂得都懂，卡不了啊......

#include <bits/stdc++.h>
#define fo(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
string s;
int n, m;
int main() {
    cin >> s;
    n = s.size();
    cin >> m;
    fo(i, 1, m) {
        string o, c;
        int x, d;
        cin >> o >> x;
        if (o == "Q") {
            cin >> d;
            x--, d--;
            int lcq = 0;
            for (int i = x, j = d; i < n && j < n; i++, j++)
                if (s[i] == s[j])
                    lcq++;
                else
                    break;
            printf("%d\n", lcq);
        }
        if (o == "R") {
            cin >> c;
            s[x - 1] = c[0];
        }
        if (o == "I") {
            cin >> c;
            s.insert(x, c);
            n = s.size();
        }
    }
    return 0;
}

代码是我校一个小朋友的，不是我的。