题解：P3279 [SCOI2013] 密码

August_Light · 2025-10-15 18:49:06 · 题解

我不会 Manacher，所以我用暴力数据结构过了这道题。

我们发现这个回文的限制和 P3295 [SCOI2016] 萌萌哒 很像。我们直接把那道题的 ST 表并查集搬过来就做完了。

具体来说我们在原串后面拼一个翻转的原串，原串一部分回文就等价于原串的这部分和反转后的这部分相等。

时间复杂度 O(n \log n \alpha(n))，因为有 ST 表所以比普通做法多一个 \log n。ST 表空间带个 \log，小心 MLE。

代码比较丑。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
using namespace std;
typedef long long ll;

const int MAXN = 2e5 + 5;
const int LOGN = 17;

struct DSU {
    int fa[MAXN], siz[MAXN], mn[MAXN];
    void init(int n) {
        rep(u, 1, n)
            fa[u] = u, siz[u] = 1, mn[u] = u;
    }
    int find(int u) {
        return fa[u] == u ? u : (fa[u] = find(fa[u]));
    }
    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v)
            return;
        if (siz[u] > siz[v])
            swap(u, v);
        fa[u] = v;
        siz[v] += siz[u];
        mn[v] = min(mn[v], mn[u]);
    }
    int query_min(int u) {
        return mn[find(u)];
    }
};

int n;
DSU dsu[LOGN + 1];

void merge(int l1, int r1, int l2, int r2) {
    int len = r1 - l1 + 1;
    int i = __lg(len);
    dsu[i].merge(l1, l2);
    dsu[i].merge(r1 - (1 << i) + 1, r2 - (1 << i) + 1);
}
int flip(int x) {
    return 2 * n + 1 - x;
}

char ans[MAXN];

int r1[MAXN], r2[MAXN];
vector<int> G[MAXN];
void add_edge(int u, int v) {
    if (1 <= u && u <= n && 1 <= v && v <= n) {
        u = dsu[0].find(u), v = dsu[0].find(v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

char mex(set<char> &st) {
    for (char c = 'a'; c <= 'z'; c++)
        if (!st.count(c))
            return c;
    return '#';
}

int main() { ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;

    rep(i, 0, LOGN)
        dsu[i].init(n * 2);
    rep(i, 1, n) {
        int r; cin >> r; r = (r + 1) / 2;
        merge(i-r+1, i, flip(i+r-1), flip(i));
        r1[i] = r;
    }
    rep(i, 1, n-1) {
        int r; cin >> r; r = r / 2;
        if (r != 0)
            merge(i-r+1, i, flip(i+r), flip(i+1));
        r2[i] = r;
    }

    per(i, LOGN, 1) {
        rep(u, 1, n * 2 - (1 << i) + 1) {
            int v = dsu[i].find(u);
            if (u != v) {
                dsu[i-1].merge(u, v);
                dsu[i-1].merge(u + (1 << (i-1)), v + (1 << (i-1)));
            }
        }
    }

    rep(i, 1, n) {
        int r = r1[i];
        add_edge(i-r, i+r);
    }
    rep(i, 1, n-1) {
        int r = r2[i];
        add_edge(i-r, i+r+1);
    }

    set<char> st[MAXN];
    rep(i, 1, n) {
        int u = dsu[0].query_min(i);
        if (i == u) {
            int rt = dsu[0].find(i);
            ans[i] = mex(st[rt]);
            for (auto v : G[rt])
                st[v].insert(ans[i]);
        } else
            ans[i] = ans[u];
        cout << ans[i];
    }

    return 0;
}