题解：P11877 KMP 的馈赠

· · 题解

KMP 的馈赠

注意到题目中的 len(border) 即为 KMP 算法所求的 nxt 数组。

由 nxt_i \to i 建树，则两个集合 u 和 v 的合并过程等价于从树上找到 u \to v 的路径。

题意转化为能否找到一条路径，使得点权和为 k。

暴力是 \mathcal O(mn^2 \log n) 的，无法接受。

暴力写法是 dis[u] + dis[v] - 2 * dis[lca(u, v)] + val[lca(u, v)]，而不是 dis[u] + dis[v] - dis[lca(u, v)]，我第一遍暴力也写错了（

事实上，这是点分治应用的经典问题，直接点分治即可通过。时间复杂度为 \mathcal O(mn \log n)。

#include<bits/stdc++.h>
#define endl '\n'
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);

constexpr int inf = 0x3f3f3f3f;

std::vector<int> judge(1E7 + 10);

void solve()
{
    int n, m;
    std::string s;
    std::cin >> n >> m >> s;
    s = '#' + s;
    std::vector<int> nxt(n + 1);
    for(int i = 2, p = 0; i <= n; i++)
    {
        while(p && (s[p + 1] != s[i]))
            p = nxt[p];
        p = nxt[i] = p + (s[p + 1] == s[i]);
    }
    std::vector<int> v(n + 1);
    for(int i = 1; i <= n; i++)
        v[i] = i ^ nxt[i];
    std::vector<std::vector<int>> edge(n + 1);
    auto add = [&](int u, int v)
    {
        edge[u].push_back(v);
    };
    for(int i = 1; i <= n; i++)
    {
        add(nxt[i], i);
        add(i, nxt[i]);
    } 
    std::vector<int> siz(n + 1), maxp(n + 1), vis(n + 1), dis(n + 1), rem(n + 1), q(n + 1);
    std::vector<int> query(m + 1), ok(m + 1);
    int rt = 0, sum = n;
    maxp[rt] = n;
    auto getrt = [&](auto &&self, int u, int fa) -> void
    {
        siz[u] = 1;
        maxp[u] = 0;
        for(auto vv: edge[u])
        {
            if(vis[vv] || vv == fa)
                continue;
            self(self, vv, u);
            siz[u] += siz[vv];
            maxp[u] = std::max(maxp[u], siz[vv]);
        }
        maxp[u] = std::max(maxp[u], sum - siz[u]);
        if(maxp[u] < maxp[rt])
            rt = u;
    };

    auto getdis = [&](auto &&self, int u, int fa) -> void
    {
        if(dis[u] > 1E7)
            return;
        rem[++rem[0]] = dis[u];
        for(auto vv: edge[u])
        {
            if(vis[vv] || vv == fa)
                continue;
            dis[vv] = dis[u] + v[vv];
            self(self, vv, u);
        }
    };

    auto calc = [&](int u)
    {
        int p = 0;
        for(auto vv: edge[u])
        {
            if(vis[vv])
                continue;
            rem[0] = 0;
            dis[vv] = v[vv];
            getdis(getdis, vv, u);
            for(int j = rem[0]; j; j--)
                for(int k = 1; k <= m; k++)
                    if(query[k] >= rem[j] + v[u])
                        ok[k] |= judge[query[k] - rem[j] - v[u]];
            for(int j = rem[0]; j; j--)
                q[++p] = rem[j], judge[rem[j]] = 1;
        }
        for(int i = 1; i <= p; i++)
            judge[q[i]] = 0;
    };

    auto solv = [&](auto &&self, int u) -> void
    {
        vis[u] = judge[0] = 1;
        calc(u);
        for(auto vv: edge[u])
        {
            if(vis[vv])
                continue;
            sum = siz[vv];
            maxp[rt = 0] = inf;
            getrt(getrt, vv, -1);
            self(self, rt);
        }
    };

    for(int i = 1; i <= m; i++)
        std::cin >> query[i];
    maxp[rt] = sum = n;
    getrt(getrt, 0, -1);
    solv(solv, rt);

    for(int i = 1; i <= m; i++)
        std::cout << (ok[i] ? "Yes" : "No") << endl;

}

int main()
{
    #ifdef ONLINE_JUDGE
    ioclear;
    #endif

    int t = 1;
    // std::cin >> t;
    while(t--)
        solve();
}

验题队写了 dsu on tree 做法，也放过去了。时间复杂度为 \mathcal O(mn \log^2 n)。

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vint;

const int N = 50005;

int nxt[N];
int n, m, d[N];
vint e[N];
int qr[505], as[505], val[N];

set<int> b[N];

void dfs(int u, int pa) {
    d[u] += val[u];
    b[u].insert(d[u]);
    for (int v : e[u]) {
        d[v] = d[u];
        dfs(v, u);
        if (b[u].size() < b[v].size()) b[v].swap(b[u]);
        for (int i : b[v]) {
            for (int j = 1; j <= m; ++j)
                if (!as[j] && b[u].find(qr[j] + d[u] + d[pa] - i) != b[u].end()) as[j] = 1;
        }
        b[u].merge(b[v]);
    }
   // for (int i : b[u]) cout << i << ' '; cout << ": " << u << '\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    string s; cin >> s; s = '#' + s;
    for (int i = 2,p = 0; i <= n; ++i) {
        while(p && s[i] != s[p + 1]) p = nxt[p];
        if(s[i] == s[p + 1]) p ++;
        nxt[i] = p;
    }
    for (int i = 1; i <= n; ++i) e[nxt[i]].push_back(i), val[i] = i ^ nxt[i];
    for (int i = 1; i <= m; ++i) cin >> qr[i];
    dfs(0, 0);
    for (int i = 1; i <= m; ++i) cout << (as[i] ? "Yes" : "No") << '\n';
    return 0;
}