题解——2023年码谷提高组模拟赛1016
一套被各种转来转去的题；参考：https://blog.csdn.net/liuziha/article/details/127353981、https://www.luogu.com.cn/blog/Chen5201314/xiao-nei-bi-sai-1025-zong-jie-ti-xie 和 https://www.cnblogs.com/Clyfort/articles/0927-test-solution.html 这三篇题解。
A. 小 O 的珠子（bead）
网址：https://www.luogu.com.cn/problem/U372849。
题意
给定 \(n\) 个字符串 \(s_i\)，求这些字符串的一种排列，使得拼接之后的字符串字典序最小。
正解
第一反应是按字典序排列，但是有 Hack 数据：
2
aba
ab
按照字典序排列是 ababa，而正解是 abaab。
问题出在哪里？本人一开始想着特判，但是足以把人绕懵。
于是考虑重新设计排序方式，重新定义字符串比较 \((<)\) 为（其中 \(s_1,s_2\) 表示字符串，\(+\) 表示字符串连接）：
\(\boxed{s_1(<)s_2=s_1+s_2<s_2+s_1}\)
证明：要证什么？怎么证明？为什么要证？打表就完了。
实在要证明的话要考虑：严格弱序／Strict weak orderings。
代码
#include <bits/stdc++.h>
using namespace std;
inline bool cmp(const string a, const string b) {
return a + b < b + a;
} signed main() {
vector<string> str; str.clear();
int n; string tmp; cin >> n;
for (int i = 1; i <= n; ++i) cin >> tmp, str.push_back(tmp);
sort(str.begin(), str.end(), cmp);
string res; for (string i : str) res += i;
cout << res << endl;
return 0;
}
B. 王国的传送门（gate）
网址：https://www.luogu.com.cn/problem/U372850。
题意
有 \(n\) 个节点，\(n\) 条边单向边的连通图，现可以改变一些边的目的地，求最小的更改次数，使得节点 \(\forall u\in[1,n]\) 经过 \(k\) 步可以到达节点 \(1\)。
部分分
有 \(15\%\) 的数据，\(k=1\)。
只能走一步，所以只要没连到节点 \(1\) 的边都得改，枚举即可。
正解
可以分两种情况讨论：
0x01
有边 \((1,1)\)，即 \(1\) 的自环；剩下 \(n-1\) 边，\(n\) 个点还是联通的，因此这是一个树（排除 \(1\) 的自环的话）。
从 \(1\) 开始，一定可以走 \(k\) 步回到 \(1\)，也就是一直转圈就可以。
从其他点 \(x\) 出发，如果它到 \(1\) 的距离 \(\le k\)，也一定能在 \(k\) 步到达 \(1\)，即先走 \(\text{dis}(x,1)\) 步到达 \(1\)，然后再在 \(1\) 号点绕 \(k-\text{dis}(x,1)\) 步。
因此问题转换为，求最少改几个点，使得节点 \(\forall x\in[2,n],\text{dis}(x,1)\le k\)。
因此可以一遍 DFS，对于每个节点 \(x\)，如果它的子树中到它的最大距离 \(\ge k\)，就连一条边 \((x,1)\)。
特别的，如果 \(x=1\)，则一定不能加边，因为已经有自环了；如果 \(f_x=1\)，也不能加边，因为已经有一条边 \((x,1)\) 了。
0x02
没有边 \((1,1)\)，即原图是一个基环树（如果不是就不连通了）。
可以大胆猜测，一定需要一条边 \((1,1)\)，为什么呢？（感性理解）
假设我们已经通过若干次操作，使得现在的图 \(\mathrm{G}'\) 满足条件，且没有 \((1,1)\) 的自环，即 \(f_1\neq1\)。
那么此时一定有 \(\text{dis}(f_1,1)=k\)，且 \(1\) 要回到 \(1\) 只能经过图中的环 \(1\rightarrow f_1\rightarrow f_{f_1}\rightarrow\cdots\rightarrow t\rightarrow1\)，则一定有 \(x\in[f_{f_1},t],\text{dis}(x,1)<k\)，而这些点一定有点无法在 \(k-\text{dis}(x,1)\) 步恰好回到点 \(1\)。
因此，必须要有边 \((1,1)\)，即 \(1\) 的自环。
问题转换为上一个情况，当然，为了补充自环 \((1,1)\)，这一种情况还要再 \(+1\)。
代码
#include <bits/stdc++.h>
using namespace std;
int pos1, n, k, v, dp[100010], ans;
vector<int> g[100010];
void dfs(int u, int fa) {
dp[u] = 1; for (int v : g[u]) dfs(v, u), dp[u] = max(dp[u], dp[v] + 1);
if ((u != 1) && (dp[u] > k || (dp[u] == k && fa != 1))) ++ans, dp[u] = 0;
} signed main() {
cin >> n >> k >> pos1;
for (int i = 2; i <= n; ++i) cin >> v, g[v].push_back(i);
dfs(1, -1); printf("%d\n", ans + (pos1 != 1));
return 0;
}
C. 黑白树（bwtree）
网址：https://www.luogu.com.cn/problem/U372853。
题意
一棵 \(n\) 个节点的树，初始所有边都是黑色的。每次可以选择一条全黑的路径，删掉其中一条边，然后在路径的两个端点之间连一条白色的边；求最后能否得到目标形态（全白的边）的树。
部分分
正解
《正难则反》——忘了是我的哪个网课老师了
D. 反复横跳（jump）
网址：https://www.luogu.com.cn/problem/U372866。
题意
给定 \(m\) 个字符串 \(S_1,S_2,\cdots,S_m\)，令 \(n = \sum_{i\in[1,m]}|S_i|\)，以及一个序列 \(a_1,a_2,\cdots,a_n\)。
你需要维护一个关于任意字符串的 \(f\) 函数，初始时 \(f\) 值全为 \(0\)。
进行 \(q\) 次操作，每次操作有以下两种：
- 给定 \(x\)，对于任意 \(S_k\)，若其等于 \(S_x\) 的一个后缀 \(S_x[i,|S_x|]\)，则令 \(f(S_k)\) 加上 \(a_i\)（本质相同的 \(S_k\) 只加一次）；
- 给定 \(x\) ，询问 \(f(S_x)\)。
其中，\(S[l,r]\) 表示将 \(S\) 从左往右数第 \(l\) 到第 \(r\) 个字符顺次连接得到的字符串。
分析
我在读懂题的边缘反复横跳。
PS
《我分类讨论到最后，发现第一类属于第二类，第三类包含第二类，第四类不存在》
