题解：P16790 [蓝桥杯 2026 国 A] 魔法前缀
lailai0916
·
·
题解
题意简述
给定若干个小写字符串。
取出它们所有不同的非空前缀。
每次可以选择一个现存前缀，
并删除所有以它为前缀的字符串。
两人轮流操作，无法操作的人失败。
判断先手是否必胜。
解题思路
所有不同前缀组成一棵字典树。
空串是树根，但不属于可选前缀。
选择前缀 P，
等价于删除对应节点及其整棵子树。
也可以理解为切断它与父节点之间的边。
下面求这种树上游戏的 SG 值。
先证明一个常用结论。
设游戏 G 的 SG 值为 x。
在它上方接一条可以直接切断的新边，
得到的新游戏记为 G'，则：
\operatorname{SG}(G')=x+1
切断新边后，SG 值为 0。
若不切新边，
则要在原游戏 G 内进行一步操作。
根据 x 的定义，
但不包含 $x$。
对规模更小的后继局面使用同一结论。
这些后继接上新边后，
SG 值分别在原值上加一。
因此，$G'$ 的后继包含 $0$ 到 $x$，
但不包含 $x+1$。
取 $operatorname{mex}$ 后恰好得到 $x+1$。
回到字典树。
根节点的每棵儿子子树互不影响，
它们是若干个独立的子游戏。
设 $f_u$ 表示保留节点 $u$，
只允许删除其下方子树时的 SG 值。
对每个儿子 $v$，
连接 $u,v$ 的边为它额外增加一层，故：
$$
f_u=\bigoplus_{v\in\operatorname{son}(u)}(f_v+1)
$$
整局游戏的 SG 值就是空串根节点的 $f$。
它非零时先手必胜，否则后手必胜。
代码没有按字符逐个查找字典树儿子。
先将所有原字符串按字典序排序。
相邻字符串的最长公共前缀已经建好。
当前字符串超出公共前缀的部分，
才会产生一条新的节点链。
用 $path_d$ 记录上一字符串长度为 $d$ 的前缀节点。
求出相邻字符串的最长公共前缀长度 $p$ 后，
保留 $path_0$ 到 $path_p$，
再从深度 $p+1$ 起建立新节点。
相同字符串不会新增节点。
某个字符串是另一字符串的前缀时，
对应节点也只会建立一次。
节点总是晚于父节点建立。
所以，无需保存儿子表。
按编号倒序枚举节点，
将 $f_i+1$ 异或到父节点即可。
设全部字符串的总长度为 $S$。
建树和计算 SG 值需要 $O(S)$ 时间。
排序复杂度为 $O(S\log N)$，
总空间复杂度为 $O(S)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
int fa[N],f[N],path[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<string> a(n);
for(auto &s:a)cin>>s;
sort(a.begin(),a.end());
int cnt=0;
f[0]=path[0]=0;
for(int i=0;i<n;i++)
{
int len=a[i].size(),p=0;
if(i)
{
int last=a[i-1].size();
int m=min(len,last);
while(p<m&&a[i][p]==a[i-1][p])p++;
}
for(int j=p;j<len;j++)
{
cnt++;
fa[cnt]=path[j];
f[cnt]=0;
path[j+1]=cnt;
}
}
for(int i=cnt;i;i--)f[fa[i]]^=f[i]+1;
cout<<(f[0]?"XiaoLan":"XiaoQiao")<<'\n';
}
return 0;
}
```