【AtCoder Regular Contest 087 E】Prefix-free Game | Mrsrz's blog

博弈论。

题目大意：

对于两个字符串 $s,t$，如果它们互相不是对方的前缀，则称他们是 prefix-free 的。

对于一个字符串集合 $S$，如果满足下面两个条件，则称它是 good string set 。

• $S$ 中每个字符串的长度都在 $1\sim L$ 之间，且只包含字符 0 和 1。
• $S$ 中任意两个字符串都是 prefix-free 的。

现在给定 good string set 集合 $S$，两个人在玩游戏，每个人要往集合中加入一个字符串，并且保证加入以后仍为 good string set。不能操作者输。

假设两人都足够聪明，问最后哪方会赢。

题解：

我们把所有串建成 trie 树，则相当于每次可以标记一个点，并满足不存在一个标记的点是另一个标记的点的祖先。

通过打表找规律，可以发现，深度为 $L$ 的满二叉树的 sg 值为 $\mathrm{lowbit}(L)$。

那么可以在 trie 树上计算整棵树的 sg 值。

Code：

#include<cstdio>
#include<cstring>
const int N=2e5+6;
typedef long long LL;
int ch[N][2],nod,n;LL L,g;
char s[N];
inline LL lbt(LL x){return x&-x;}
void dfs(int now,int dep){
    if(dep==L)return;
    if(ch[now][0])dfs(ch[now][0],dep+1);else g^=lbt(L-dep);
    if(ch[now][1])dfs(ch[now][1],dep+1);else g^=lbt(L-dep);
}
int main(){
    scanf("%d%lld",&n,&L);
    if(!n)return puts("Bob"),0;
    while(n--){
        scanf("%s",s);
        int nw=0;
        for(int i=0;s[i];++i){
            int c=s[i]&15;
            if(!ch[nw][c])ch[nw][c]=++nod;
            nw=ch[nw][c];
        }
    }
    dfs(0,0);
    puts(g?"Alice":"Bob");
    return 0;
}