2026-10-26 hetao1733837 的刷题记录

LGP17164 [CEOI 2026] DFS

原题链接：[CEOI 2026] DFS

分析

这个 d 应该就是点 $w$ 到 $n-1$ 的最小距离。那么，可以按照这个建一棵最短路树，然后，是不是答案就出来了？
除了知道这个以外，我们似乎还知道某些点一定是另外一些点的儿子或父亲，因为我们知道在 dfs 序上，某一点的子树是一段连续的序列。那么，是不是真的做完了……但是，我会求吗？估计不会……所以，我没有想清楚……

---

没关系，有巨人的肩膀——就是大概 $2^m$ 的样子……但是，我没看懂……说实在地……思考一下……诶？
哦，这个是 dfs 树！那个 d 就是相当于深度！那不是好做很多了？
那么，具体怎么做呢？
哦，那么，我们可以“向下”连边……对吗？也不对啊？应该是子树同深度之间连边吧 ……那更不对了啊……别急……思考一下……
如果这一深度有 $cnt$ 个，那么，答案就是 $2^{cnt}$？所有的深度加和即可……那也不对啊？
对于一个点，可以和非父亲的所有点连？
然而，如果继续按照最短路树的思路走下去，会有：
$$ans=2^m,m=\sum _{d\ge 0}{C}_{cn{t}_d}^2+\sum _{d\ge 1}cn{t}_d\times (cn{t}_{d-1}-1)$$
其中，$C$ 表示组合数。

但是，最短路是 bfs！

所以说，我们还是需要在 dfs 上考虑……我们发现，其实，我们可以将一个点向其不相邻且序号小于他的点连边……这个不会是什么单调栈状物吧……
那不如我找一个题解看看……
好的，你的最后一句话已经把所有的东西说出来了，我们拿一个树状数组维护一下即可……

正解

#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N = 200005;
int n, de[N];
int buc[N], fa[N];
vector<int> e[N];
int ans = 1;
int qpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
int c[N];
void add(int x, int val){
	for (int i = x; i < N; i += i & (-i))
		c[i] += val;
}
int query(int x){
	int res = 0;
	for (int i = x; i; i -= i & (-i)){
		res += c[i];
	}
	return res;
}
void dfs(int u, int pa){
	add(u, 1);
	ans = ans * qpow(2, query(u - 1)) % mod;
	for (auto v : e[u]){
		if (v != pa)
			dfs(v, u);
	}
	add(u, -1);
}
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	n = 1; 
	for (int cs = 1, d, v; cs <= n; cs++){
		scanf("%lld/%lld", &d, &v);
		v++;
		if (cs == 1){
			n = v;		
		}
		de[v] = d;
		buc[cs] = v;
	}
	int u = n;
	for (int i = 2; i <= n; i++){
		while (de[u] != de[buc[i]] - 1)
			u = fa[u];
		fa[buc[i]] = u;
		e[u].push_back(buc[i]);
		u = buc[i];
	}
	dfs(n, 0);
	printf("%lld", ans);
}

LGP16359 [BalticOI 2026] Tourist’s Journey

原题链接：[BalticOI 2026] Tourist’s Journey

分析

显然，我们要在图的一颗生成树上考虑……

---

我们相当于设 $d{p}_{i,k}$ 表示我们经过了 $i$ 步，最后位于 $j$ 的方案数。然后转移就可以了……还是……这是啥啊，我不想多说了，写一下吧……起到了复习板子的作用。我打算回寝室睡觉了。感觉一直睡不够，而且睡得很浅，梦很多……晕😵和懵😵竟然一样吗？

---

打模拟赛发现：对于没有返回值的函数，如果没有返回，本地可能 AC，但是，交上去可能 RE!

---

呃……就是这样的……感觉理解了，实则没有理解……

正解

#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N = 200005, M = 22;
int n, m, k;
vector<int> e[N];
vector<pair<int, int>> ntt; //not tree edge
int fa[N], sz[N], de[N], f[N][M];
int dis[M][M], dp[N][M];
int find(int x){
	return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
} 
void merge(int x, int y){
	int fx = find(x), fy = find(y);
	if (fx == fy)
		return ;
	if (sz[fx] < sz[fy])
		swap(fx, fy);
	sz[fx] += sz[fy];
	fa[fy] = fx;
}
void dfs(int u, int pa){
	f[u][0] = pa;
	de[u] = de[pa] + 1;
	for (auto v : e[u]){
		if (v == pa)
			continue;
		dfs(v, u);
	}
}
int LCA(int x, int y){
	if (de[x] < de[y])
		swap(x, y);
	int delta = de[x] - de[y];
	for (int i = 20; i >= 0; i--){
		if (delta & (1 << i)){
			x = f[x][i];
		}
	}
	if (x == y)
		return y;
	for (int i = 20; i >= 0; i--){
		if (f[x][i] != f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int get_dis(int x, int y){
	return de[x] + de[y] - 2 * de[LCA(x, y)];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++){
		fa[i] = i;
		sz[i] = 1;
	}
	for (int i = 1, u, v; i <= m; i++){
		cin >> u >> v;
		if (find(u) == find(v)){
			ntt.push_back({u, v});
			ntt.push_back({v, u});
		}
		else{
			e[u].push_back(v);
			e[v].push_back(u);
			merge(u, v);
		}
	}
	dfs(1, 0);
	for (int i = 1; i <= 20; i++){
		for (int u = 1; u <= n; u++){
			f[u][i] = f[f[u][i - 1]][i - 1];
		}
	}
	for (int i = 0; i < (int)ntt.size(); i++){
		dis[0][i + 1] = get_dis(1, ntt[i].first);
		for (int j = 0; j < (int)ntt.size(); j++){
			dis[i + 1][j + 1] = get_dis(ntt[i].second, ntt[j].first);
		}
	}
	for (int i = 1; i <= k; i++){
		for (int j = 0; j < (int)ntt.size(); j++){
			if (dis[0][j + 1] == i - 1){
				dp[i][j + 1] = 1;
			}
			for (int l = 0; l < (int)ntt.size(); l++){
				if (dis[l + 1][j + 1] < i && (j ^ 1) != l){
					dp[i][j + 1] = (dp[i][j + 1] + dp[i - dis[l + 1][j + 1] - 1][l + 1]) % mod;
				}
			}
		}
	}
	int ans = 0;
	if (get_dis(1, n) == k)
		ans = 1;
	for (int i = 0; i < (int)ntt.size(); i++){
		if (get_dis(ntt[i].second, n) < k){
			ans = (ans + dp[k - get_dis(ntt[i].second, n)][i + 1]) % mod;
		}
	}
	cout << ans;
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/hetao1733837/article/details/169130369