题外话
给大家讲个笑话，这四题写一起是因为别人送了一场校内模拟赛，结果赛后发现 Subtask 还要自己加，T3 的 SPJ RE 了，T4 的数据包还和 T3 发重了
COCI 2019-2020 #6 Trener
题目里有一个关键条件：前一个字符串必须是后一个字符串的子串。
这意味着，只要后一个字符串确定了，那么前一个字符串至多只有两种可能。
所以我们有一个初步的想法：确定后面的即可缩小前面的范围。于是有一个暴力的想法，就是枚举最后的选谁，然后往前搜索，逐层确定。
这个东西的复杂度我不会分析（想了一下，暴力是指数复杂度，记搜和下面的 DP 似乎是一个做法），考场上实现了一下也不大好写（因为我比较菜）。但是我们能从这个想法里感觉出来两个点：
- 往前搜索的过程中每个点只能从长的字符串往短的字符串走，也就是不能形成环
- 一个合法的方案就是把搜索过程中经过的点倒序输出
发现了什么？如果我们把搜索图画出来，那么这就是一个反向的 DAG，求答案的过程实际上就是在求路径的条数！
于是本题的做法就呼之欲出了：考虑两个长度差为 (1) 的字符串 (a,b(|a| < |b|))，如果 (a) 是 (b) 的子串，那么就在图中加一条 (a) 的编号到 (b) 的编号的点，最终形成一个 DAG，在 DAG 上跑 DP 求所有起点（长度为 (1) 的串代表的点）到每个点的路径条数，把所有终点（长度为 (n) 的串代表的点）的答案加起来即可。
复杂度分析？
我也不大会分析这个复杂度，但是有两点是知道的：
- 总点数为 (NK)
- 每个点至多会连进来两条入边，比如
abcde这个字符串，两个可能的子串是abcd和bcde，从这两个点连边到这个字符串
实现起来跑得飞快，截止到发表时最优解第二名。
const int MAXN = 50 + 10;
const int MAXK = 1500 + 10;
const int MAXNODE = MAXN * MAXK;
const int HA = 1e9 + 7;
std::map<std::string, int> mp[MAXNODE], idx[MAXNODE];
int n, k;
struct E {int v, w;};
int cnt = 0;
std::vector<E> G[MAXNODE];
int ind[MAXNODE];
void addEdge(int u, int v, int w) {
// DEBUG(u); DEBUG(v); DEBUG(w);
G[u].push_back({v, w});
++ind[v];
}
lli dp[MAXNODE];
void DP() {
std::queue<int> q;
// for (int i = 1; i <= cnt; ++i) {
// if (!ind[i]) {
// dp[i] = 1; q.push(i);
// }
// }
for (auto ids : idx[1]) {
dp[ids.second] = 1; q.push(ids.second);
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto e : G[u]) {
int v = e.v; lli w = e.w;
dp[v] += dp[u] * w % HA;
dp[v] %= HA;
--ind[v];
if (!ind[v]) q.push(v);
}
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
rep (i, 1, n) rep (j, 1, k) {
std::string ss; cin >> ss;
mp[i][ss]++;
idx[i][ss] = 0;
}
rep (i, 1, n) {
for (auto it = idx[i].begin(); it != idx[i].end(); it++) {
it->second = ++cnt;
// DEBUG(it->first); DEBUG(cnt);
}
}
for (int len = 2; len <= n; ++len) {
for (auto strp : mp[len]) {
// DEBUG(strp.first);
std::string sub = strp.first.substr(0, len - 1);
if (mp[len - 1].count(sub)) {
// DEBUG(sub);
// DEBUG(mp[len - 1][sub]);
addEdge(idx[len - 1][sub], idx[len][strp.first], mp[len - 1][sub]);
}
if (sub == strp.first.substr(1, len - 1)) continue;
sub = strp.first.substr(1, len - 1);
if (mp[len - 1].count(sub)) {
// DEBUG(sub);
// DEBUG(mp[len - 1][sub]);
// G[idx[len - 1][sub]].push_back({idx[len][strp.first], mp[len - 1][sub]});
addEdge(idx[len - 1][sub], idx[len][strp.first], mp[len - 1][sub]);
}
}
}
DP();
lli ans = 0;
for (auto strp: mp[n]) {
ans += dp[idx[n][strp.first]] * 1ll * strp.second;
ans %= HA;
}
cout << ans << endl;
return 0;
}
COI 2020 Pastiri 题解翻译
前言
定义点集为 (V)。
首先可以观察到这个问题相当于是在大量集合里选一些集合，使得它们并起来是全集。要选的集合记为 (S_v) 表示将一个牧羊人放在 (v) 点能保护哪些羊。这个问题是 NPC 的，但是本题的树形结构有一些特殊性质可以帮助解题。
Task 1
链的情况很简单，从左到右贪心，如果当前的羊和下一只羊可以被同一个牧羊人管就放一个，否则就只在当前点放牧羊人，下一只羊和再下只羊一起考虑，重复这个过程。
Task 2
在羊很少的情况下我们可以使用 BFS 来计算 (S_v)，然后考虑状压 DP：设 (f(mask)) 表示至少（不是恰好）覆盖 (mask) 这个集合所需要的最少牧羊人数。
转移很显然，枚举子集 $submask = $ 某个 (S_v) 然后 (f(mask) leftarrow f(mask oplus submask) + 1) 即可。为了完成转移，我们还要让所有满足 (submask subseteq mask) 的 (f(submask) leftarrow f(mask))。
空间复杂度 (O(N+2^K))，时间复杂度 (O(NK+3^K))，因为要枚举子集。
Task 3
首先随便找一个点提起来当根。
接下来我们考虑反过来做，刚刚是对每个点处理出覆盖的羊，这次是对所有羊处理出 (T_v) 表示对于一个在 (v) 点的羊，在哪些点放置牧羊人能覆盖到它，我们称之为它的领地。
想法很简单，贪心地放置一个牧羊人使得它能尽可能多地覆盖羊，显然这样的位置存在于一堆 (T) 集合的交集，我们再定义两只羊 (u,v) 是朋友当且仅当 (T_u igcap T_v eq varnothing)。于是这个想法可以描述成，每次贪心地针对某个羊放置一个牧羊人，使得这个牧羊人可以管住该羊和其他所有（未被保护的）朋友。
有一条性质：
对于某只羊 (x)，令 (a(x)) 表示在 (x) 领地里的深度最浅的祖先，那么 (S_{a(x)}) 包含了 (x) 的朋友中所有深度不比 (x) 更深的。
证明：考虑任意一个不比 (x) 更深的 (x) 的朋友 (y)。如果 (y) 在 (a(x)) 的子树里则结论显然（不比 (x) 更深保证了它不超出 (a(x)) 的覆盖范围），考虑不在子树中的情况。
任意选取一个在 (x) 和 (y) 领地外的点 (z)，取 (x longleftrightarrow y) 的路径中点 (w)，可以证明对于任意羊 (t)
显然 (w in S_x igcup S_y)，又因为 (x) 的深度不小于 (y) 所以 (w) 即是 (x) 的一个祖先，夹在 (x longleftrightarrow a(x)) 的路径之间。因为 (y) 不在 (a(x)) 子树中，所以有
得证。
所以我们有一个贪心策略：不断选取最深的没有被保护的羊 (x)，在 (a(x)) 上放一个牧羊人，直到所有羊都被保护。
时间复杂度 (O(N(N+K)))。
满分做法
考虑优化这个想法。
快速求出 (a(x))
记 (dep(v)) 表示节点的深度，(ds(v)) 表示节点到最近羊的距离，这个东西可以靠一次 BFS 预处理出来（初始时把所有羊加入队列）。
可以发现另一个性质：
如果 (v) 是 (x) 的祖先，那么 (ds(v) leq dep(x) - dep(v))，等号成立当且仅当 (v in T_x)。
这个东西比较显然，实际上就是 (T_x) 的定义。
从这里我们可以看出，(a(x)) 就是在 (x) 到根的路径上第一个 (dep(v) + ds(v)) 最大的点。这个东西一遍 DFS 搞定。
快速维护没被保护的最深的羊
按深度降序排序，问题转化成维护哪些羊被保护了。
然后考虑建一棵完全相同的树，在这个新图上给边定向，边 ((u, v)) 定向成 ((u ightarrow v)) 当且仅当 (ds(v) = ds(u) + 1)。
这个图有一个性质：
对于任意点 (v)，一只羊 (x) 属于 (S_v) 当且仅当从 (x) 到 (v) 是联通的。
所以我们可以在添加牧羊人的时候从牧羊人的点开始做反图的 DFS，能遍历到的所有点就是 (S_v)。注意到已经被访问过的点可以直接忽略，这样每个点至多会被访问一次，时间复杂度 (O(N))。
到此，整道题就解决了。时间复杂度 (O(N + K log K))，(log) 来源于排序，但如果你使用桶排则可以做到 (O(N + K))。