专栏文章

题解：P11877 KMP 的馈赠

DDusker
P11877题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipydbx8
此快照首次捕获于
2025/12/03 19:57
3 个月前
此快照最后确认于
2025/12/03 19:57
3 个月前
查看原文

KMP 的馈赠

  • 预期难度：银（蓝+/紫-，可评紫）
  • 关键词：KMP、border tree、树上问题、点分治、dsu on tree
注意到题目中的 len(border) 即为 KMP 算法所求的 nxt 数组。
由 nxti→inxt_i \to i 建树，则两个集合 uu 和 vv 的合并过程等价于从树上找到 u→vu \to v 的路径。
题意转化为能否找到一条路径，使得点权和为 kk。
暴力是 O(mn2log⁡n)\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)]，我第一遍暴力也写错了（
事实上，这是点分治应用的经典问题，直接点分治即可通过。时间复杂度为 O(mnlog⁡n)\mathcal O(mn \log n)。
CPP
#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 做法，也放过去了。时间复杂度为 O(mnlog⁡2n)\mathcal O(mn \log^2 n)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...