题解：CF1455F String and Operations

xz001 · 2025-11-10 15:14:10 · 题解

首先我们发现一个点最多被交换两次，所以首先我们可以记忆化搜索，设 f_{i,q_1,q_2,q_3,at} 表示到达第 i 个位置，以 q_3 作为第 i 个字符，q_1,q_2 在其前面，at 表示初始第 i 个现在在哪里（q_2 还是 q_3）。然后可以直接转移，用 map 记忆化，加上很多剪枝后可以发现只有 8000 多个状态，复杂度 8000\times 500，但因为 1000 组测试数据，不可行。

发现复杂度瓶颈在于字符串的存储和比较，所以我们不存字符串了，我们存转移点，并用倍增维护哈希值，从而实现单次 \log n 的字符串大小比较。

这样大约跑 8000 \times 1000\times 10=8\times 10^7 次左右，但我们一开始使用的 map 记忆化，所以不容易过去。

注意到每一种状态都可以变进制哈希成一个小于 4\times 10^7 的数字，因此我们可以先搜出所有状态，给它们编号，然后再写一个搜索将这些编号清空，这样就可以优化掉 map 这个 \log，即可卡过。

代码：

#include <bits/stdc++.h>

#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

using namespace std;

const int N = 1e6 + 5;

int t, idx;

int n, k;

char s[N];

unsigned long long c[N];

bool f[N];

struct node {
    int i, q1, q2, q3, at;
};

node d[N];

int id[40 * N]; 

int st[12][20005];

unsigned long long h[12][20005];

inline unsigned long long hs (const int i, const int q1, const int q2, const int q3, const int at) {
    unsigned long long h = i;
    h = h * 26 + q1;
    h = h * 26 + q2;
    h = h * 26 + q3;
    h = h * 4 + at;
    return h;
} 

inline unsigned long long hs (const node &a) {
    unsigned long long h = a.i;
    h = h * 26 + a.q1;
    h = h * 26 + a.q2;
    h = h * 26 + a.q3;
    h = h * 4 + a.at;
    return h;
}

int cnt;

inline void Dfs (const int i, const int q1, const int q2, const int q3, const int at) {
    unsigned long long now = hs(i, q1, q2, q3, at);
    if (i > n) {
        if (id[now]) return;
        d[ ++ idx] = {i, q1, q2, q3, at};
        id[now] = idx;
        d[ ++ idx] = {i + 1, q2, q3, 0, at};
        id[hs({i + 1, q2, q3, 0, at})] = idx;
        return;
    }
    if (id[now]) return;
    d[ ++ idx] = {i, q1, q2, q3, at};
    id[now] = idx;
    if (at == 2) {
        if (q1 != q2) {
            if (q1 < q2) {
                if (q3 < min((q2 + 1) % k, (q2 - 1 + k) % k)) {
                    Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
                } else if (q3 > min((q2 + 1) % k, (q2 - 1 + k) % k)) {
                    Dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
                } else {
                    Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
                    Dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
                }
            } else {
                Dfs (i + 1, q1, q3, s[i + 1] - 'a', 3);
            }
        } else {
            Dfs (i + 1, q1, q3, s[i + 1] - 'a', 3);
            Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
            Dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
        }
    } else {
        if (q3 < q2) {
            Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
        } else if (q3 > q2) {
            Dfs (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
        } else {
            Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
            Dfs (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
        }
        if (i != n) {
            Dfs (i + 1, q2, s[i + 1] - 'a', q3, 2);
        }
    }
    return;
}

inline void DFS (const int i, const int q1, const int q2, const int q3, const int at) {
    unsigned long long now = hs(i, q1, q2, q3, at);
    if (i > n) {
        if (!id[now]) return;
        f[id[now]] = false;
        id[now] = 0;
        f[id[hs({i + 1, q2, q3, 0, at})]] = false;
        id[hs({i + 1, q2, q3, 0, at})] = 0;
        return;
    }
    if (!id[now]) return;
    f[id[now]] = false;
    id[now] = 0;
    if (at == 2) {
        if (q1 != q2) {
            if (q1 < q2) {
                if (q3 < min((q2 + 1) % k, (q2 - 1 + k) % k)) {
                    DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
                } else if (q3 > min((q2 + 1) % k, (q2 - 1 + k) % k)) {
                    DFS (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
                } else {
                    DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
                    DFS (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
                }
            } else {
                DFS (i + 1, q1, q3, s[i + 1] - 'a', 3);
            }
        } else {
            DFS (i + 1, q1, q3, s[i + 1] - 'a', 3);
            DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
            DFS (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
        }
    } else {
        if (q3 < q2) {
            DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
        } else if (q3 > q2) {
            DFS (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
        } else {
            DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
            DFS (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
        }
        if (i != n) {
            DFS (i + 1, q2, s[i + 1] - 'a', q3, 2);
        }
    }
    return;
}

inline void dfs (const int i, const int q1, const int q2, const int q3, const int at) {
    int now = id[hs(i, q1, q2, q3, at)];
    if (i > n) {
        h[0][now] = q1 + 'a';
        int t = id[hs({i + 1, q2, q3, 0, at})];
        st[0][now] = t;
        h[0][t] = q2 + 'a';
        for (int j = 1; j <= 10; ++ j ) {
            st[j][now] = t;
            h[j][now] = h[j - 1][now] * c[1 << (j - 1)] + h[j - 1][st[j - 1][now]];
        }
        return;
    }
    if (f[now]) return;
    f[now] = true;
    if (at == 2) {
        if (q1 != q2) {
            if (q1 < q2) {
                if (q3 < min((q2 + 1) % k, (q2 - 1 + k) % k)) {
                    st[0][now] = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})];
                    h[0][now] = q1 + 'a'; 
                    dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
                } else if (q3 > min((q2 + 1) % k, (q2 - 1 + k) % k)) {
                    st[0][now] = id[hs({i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3})];
                    h[0][now] = q1 + 'a';
                    dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
                } else {
                    const int U = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})], V = id[hs({i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3})];
                    int u = U, v = V;
                    dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
                    dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
                    int cnt = 0;
                    for (int i = 10; i >= 0; -- i ) {
                        if (h[i][u] == h[i][v]) {
                            u = st[i][u], v = st[i][v];
                            cnt += 1 << i;
                        }
                    }
                    if (cnt >= 1e3) {
                        st[0][now] = U;
                        h[0][now] = q1 + 'a';
                    } else if (h[0][u] < h[0][v]) {
                        st[0][now] = U;
                        h[0][now] = q1 + 'a';
                    } else {
                        st[0][now] = V;
                        h[0][now] = q1 + 'a';
                    }
                }
            } else {
                st[0][now] = id[hs({i + 1, q1, q3, s[i + 1] - 'a', 3})];
                h[0][now] = q2 + 'a';
                dfs (i + 1, q1, q3, s[i + 1] - 'a', 3);
            }
        } else {
            h[0][now] = q2 + 'a';
            dfs (i + 1, q1, q3, s[i + 1] - 'a', 3);
            dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
            dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
            const int U = id[hs({i + 1, q1, q3, s[i + 1] - 'a', 3})], V = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})];
            int u = U, v = V;
            int cnt = 0;
            for (int i = 10; i >= 0; -- i ) {
                if (h[i][u] == h[i][v]) {
                    u = st[i][u], v = st[i][v];
                    cnt += 1 << i;
                }
            }
            if (cnt >= 1e3) u = U;
            else if (h[0][u] < h[0][v]) {
                u = V;
            } else {
                u = V;
            }
            int tmp = u;
            const int T = id[hs({i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3})];
            v = T;
            cnt = 0;
            for (int i = 10; i >= 0; -- i ) {
                if (h[i][u] == h[i][v]) {
                    u = st[i][u], v = st[i][v];
                    cnt += 1 << i;
                }
            }
            if (cnt >= 1e3) u = tmp;
            else if (h[0][u] < h[0][v]) u = tmp;
            else u = T;
            st[0][now] = u;
        }
    } else {
        h[0][now] = q1 + 'a';
        int u, v;
        if (q3 < q2) {
            dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
            u = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})];
        } else if (q3 > q2) {
            dfs (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
            u = id[hs({i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3})];
        } else {
            dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
            dfs (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
            const int U = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})], V = id[hs({i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3})];
            u = U, v = V;
            int cnt = 0;
            for (int i = 10; i >= 0; -- i ) {
                if (h[i][u] == h[i][v]) {
                    u = st[i][u], v = st[i][v];
                    cnt += 1 << i;
                }
            }
            if (cnt >= 1e3) u = U;
            else if (h[0][u] < h[0][v]) u = U;
            else u = V;
        }
        if (i != n) {
            const int tmp = u;
            const int T = id[hs({i + 1, q2, s[i + 1] - 'a', q3, 2})];
            v = T;
            dfs (i + 1, q2, s[i + 1] - 'a', q3, 2);
            int cnt = 0;
            for (int i = 10; i >= 0; -- i ) {
                if (h[i][u] == h[i][v]) {
                    u = st[i][u], v = st[i][v];
                    cnt += 1 << i;
                }
            }
            if (cnt >= 1e3) u = tmp;
            else if (h[0][u] < h[0][v]) u = tmp;
            else u = T;
        }
        st[0][now] = u;
    }
    for (int j = 1; j <= 10; ++ j ) {
        st[j][now] = st[j - 1][st[j - 1][now]];
        h[j][now] = h[j - 1][now] * c[1 << (j - 1)] + h[j - 1][st[j - 1][now]];
    }
    return;
}

signed main() {
//  freopen("g.in","r",stdin);
//  freopen("g.out","w",stdout);
    c[0] = 1;
    for (int i = 1; i <= 1e6; ++ i ) c[i] = c[i - 1] * 33331;
    scanf("%d", &t);
    while (t -- ) {
        for (int i = 1; i <= idx; ++ i ) {
            for (int j = 0; j <= 10; ++ j ) {
                st[j][i] = h[j][i] = 0;
            }
        }
        idx = 0;
        scanf("%d%d%s", &n, &k, s + 1);
        s[n + 1] = 'z';
        Dfs (1, 0, 0, s[1] - 'a', 3);
        dfs (1, 0, 0, s[1] - 'a', 3);
        int u = id[hs({1, 0, 0, s[1] - 'a', 3})]; 
        for (int i = 1; i <= n + 2; ++ i ) {
            if (i > 2) printf("%c", (char)h[0][u]);
            u = st[0][u];
        }
        puts("");
        DFS (1, 0, 0, s[1] - 'a', 3);
    }
    return 0;
}