[atARC087E]Prefix-free Game

建一棵trie树，考虑一个串，相当于限制了其子树内部+其到根的链

如果将所有点补全，那么这个问题可以看作每一个极浅（子树内没有其他满足条件）的到根路径以及子树内部没有其他结束点的子树的子问题

对于多个子问题博弈，很明显去求sg，由于是一颗满二叉树，因此只与深度$l$（指该子树深度，与全局的$L$无关）有关，以下记为$f_{l}$

初始$f_{0}=1$（虽然根本身是个空串，但这个点必然不是全局trie树的根，换言之其到该根的部分仍然存在），然后$f_{i}=mex_{j=0}^{i-1}(\bigoplus_{k=j}^{i-1}f_{k})$，复杂度为$o(L^{2})$，由于$L$过大，因此要优化

观察可得$f_{n}$为$n$二进制下末尾连续1数量的2的幂次（也可以表示为$2^{lowbit(n+1)}$），证明归纳即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 #define ll long long

 5 map<int,bool>mat;

 6 int V,n,ans,vis[N],ch[N][2];

 7 ll l;

 8 char s[N];

 9 void add(char *s,int l){

10     int k=1;

11     for(int i=0;i<l;i++){

12         if (!ch[k][s[i]-'0'])ch[k][s[i]-'0']=++V;

13         k=ch[k][s[i]-'0'];

14     }

15     vis[k]=1;

16 }

17 void dfs(int k,ll l){

18     if (vis[k])return;

19     if ((!k)||(!l)){

20         int s=0;

21         while (l&1){

22             s++;

23             l>>=1;

24         }

25         mat[s]^=1;

26         if (mat[s])ans++;

27         else ans--;

28         return;

29     }

30     dfs(ch[k][0],l-1);

31     dfs(ch[k][1],l-1);

32 }

33 int main(){

34     scanf("%d%lld",&n,&l);

35     V=1;

36     for(int i=1;i<=n;i++){

37         scanf("%s",s);

38         add(s,strlen(s));

39     }

40     dfs(1,l);

41     if (ans)printf("Alice");

42     else printf("Bob");

43 }

巴特西

[atARC087E]Prefix-free Game

最新文章

热门文章