[atARC087E]Prefix-free Game

标签:one   ide   pac   ++   add   nbsp   其他   col   printf   

建一棵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 }

View Code

 

[atARC087E]Prefix-free Game

标签:one   ide   pac   ++   add   nbsp   其他   col   printf   

原文地址:https://www.cnblogs.com/PYWBKTDA/p/14117596.html

版权声明:完美者 发表于 2020-12-16 11:58:02。
转载请注明:[atARC087E]Prefix-free Game | 完美导航

暂无评论

暂无评论...