T1:

本题其实不算太简单

xor前缀差分，转化为[l,r]中选择两个数xor最大（边界的l-1再考虑一下）

按位贪心显然，区间取trie可持久化即可

考虑到一个区间的取法，是从左边答案，右边答案，和左右各拿一个。

线段树可能区间合并长度过长，复杂度无法保证

分块？复杂度有保证！

n，q范围也比较有趣

mx[i][j]记录块i到块j的答案，可以O(nsqrt(n))暴力处理

然后查询的时候边角处理一下即可。

 

#include
      
       #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=12000+5;const int blo=115;struct trie{    int ch[2];    int sz;}t[N*32+N+N];int rt[N];int tot;int n,m;int a[N],b[N];//b is presumint mx[blo][blo];int L[N],R[N];int be[N];void ins(int x,int y,int c){    rt[x]=++tot;    t[rt[x]].sz=t[rt[y]].sz+1;    x=rt[x],y=rt[y];    for(reg i=30;i>=0;--i){        ++tot;        if(c&(1<
       
        =0;--i){        if(c&(1<
       
      

 

 

 

本题不错！

看似一个AC自动机，，，

诶，字符集太大？暴力跳fail直接扫帚图卡飞

考虑一般的AC自动机怎么做？

有儿子的找fail[x]即可

没有儿子进行ch[x][i]=ch[fail[x]][i]路径压缩！

这个路径压缩保证了第一步找儿子的复杂度是O(1)的

或者说，这里把fail的边继承了下来！

什么东西可以路径压缩，继承之前的信息呢？

可持久化！！

更新完儿子的fail之后，对自己在fail[x]根的基础上，建造自己的线段树即可。

注意：

先把rt[x]变成rt[fail[x]]直接继承，然后再建造

否则trie的叶子没有儿子，就没有根了。。。

#include
      
       #define reg register int#define il inline#define mid ((l+r)>>1)#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=200000+5;const int M=200000;struct node{    int nxt,to,v;}e[2*N];int hd[N],tot;void add(int x,int y,int z){    e[++tot].nxt=hd[x];    e[tot].v=z;    e[tot].to=y;    hd[x]=tot;}int fa[N];int fail[N];int n;queue
       
        q;struct po{    int id;    int ls,rs;}t[N*20];int rt[N];int cnt;void upda(int &x,int y,int l,int r,int c,int d){    if(!x) x=++cnt;    if(l==r){        t[x].id=d;return;    }    if(c<=mid) {        t[x].rs=t[y].rs;        upda(t[x].ls,t[y].ls,l,mid,c,d);    }else{        t[x].ls=t[y].ls;        upda(t[x].rs,t[y].rs,mid+1,r,c,d);    }}int query(int x,int l,int r,int c){    if(!x) return 1;    if(l==r) return t[x].id;    if(c<=mid) return query(t[x].ls,l,mid,c);    return query(t[x].rs,mid+1,r,c);}void AC(){        for(reg i=hd[1];i;i=e[i].nxt){        int y=e[i].to;        int tmp=rt[1];rt[1]=0;        upda(rt[1],tmp,1,M,e[i].v,y);        //cout<<" st "<
        
         <
        
       
      

本题利用了可持久化的继承和路径压缩的特点，可以算是可持久化的另外一个用途！

（可持久化还可以建线段树省空间，以及查询历史版本）

T3：

本题其实并不难

但是看到博弈论不熟悉就吓到了。。。然后考试也没有留足时间

博弈论的操作是一个树形结构。

决策必须是一些字符串的前缀？trie树就是博弈树！

必然要处理先手必胜还是先手必败，trie的叶子为0，dp一遍即可。

但是为了眼光长远，必须该输就输，所以考虑能否想输就输（这个时候目标刚好相反）

这个时候，对方一定会想让你赢。

所以本质相同，trie的叶子为1，再dp一遍就可以知道一个位置能否输掉了。

然后讨论

1.必胜，可以输掉：先手无敌，可以直接狂输，然后赢即可。

2.必胜，不能想输就输，即先手赢且只能赢。K为奇数，先手必胜，偶数，先手必败

3.必输，先手必输

这样一定考虑了所有情况。

#include
      
       #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=1e5+5;int ch[N][26];char s[N];int t;int cnt;void ins(char *s,int l){    int now=1;    for(reg i=1;i<=l;++i){        int x=s[i]-'a';        if(ch[now][x]==0) ch[now][x]=++cnt;        now=ch[now][x];    }}int dfs1(int x){    int ret=0;    for(reg i=0;i<26;++i){        if(ch[x][i]){            int tmp=dfs1(ch[x][i]);            if(tmp==0) ret=1;        }    }    return ret;}int dfs2(int x){    int ret=0;    int has=0;    for(reg i=0;i<26;++i){        if(ch[x][i]) {            ++has;            int tmp=dfs2(ch[x][i]);            if(tmp==0) ret=1;        }    }    if(has) return ret;    return 1;}void clear(){    cnt=1;    memset(ch,0,sizeof ch);}int main(){    rd(t);    while(t--){        clear();        int n;        int k;        rd(n);rd(k);        for(reg i=1;i<=n;++i){            scanf("%s",s+1);            int len=strlen(s+1);            ins(s,len);        }        int bs=dfs1(1);        int kb=dfs2(1);        if(bs){            if(kb) puts("Pure");            else{                if(k&1) puts("Pure");                else puts("Dirty");            }        }else{            puts("Dirty");        }    }    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2018/12/28 15:11:22*/
      

 

还可以简单粗暴一些：

连续K轮，每轮换一个先手，相当于叶子作为下一层的根节点

即：

跑两遍dp之后，

可以倍增处理

也可以发现其实叶子颜色相同，会0/1重复，（本质和第一个方法就一致了）

讨论即可。

 

根据本题，博弈论的一个总结是：

考虑必胜必败，后继状态，从边界开始处理

还可以考虑可以输，不能输另外两种关系。