CF455B A Lot of Games

一道trie树上博弈好题，考察了对于博弈状态的设计

我是从这篇题解得到启示的

题解：

先只考虑其中一场博弈

对于n个单词建出它们的trie树

对于trie树上的每个节点设计四种状态：必胜，必败，胜败主动（由自己决定），胜败被动（由对手决定）

由题意可得，叶子结点都是必胜态的，然后就会有四种转移：

1. 若儿子中有主动点，那么对手肯定会走那个点，所以当前点是被动点

2. 若儿子中必胜必败两种点都有，那么对手可以随便选，所以当前点是被动点

3. 若儿子中只有被动点，那么对手是真的被动，所以当前点是主动点

4. 若儿子只有必胜点，当前点肯定是必败点；若儿子只有必败点，当前点肯定是必胜点

由下往上处理出每个点的博弈态后，我们对于trie的根节点（可以看成是把对手当成已经决策过的先手）的状态再次进行分类讨论：

先手必败会有三种情况：

1. 根节点是个主动点

那么对手可以先故意输k-1局保证主动然后再赢一局

1. 根节点是个必胜点

那么无论怎么玩都是对手赢

1. 根节点是个必败点但是k是个偶数

那么两人交替着当先手，偶数局后正好轮到对手获胜

其余情况都是先手必胜

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int cnt,n,k;
char s[N];

struct node{
    int nxt[26],s;
       /*
    s表示该节点的博弈状态=0/1/2/3
    =0:必败
    =1:必胜 
    =2:主动胜败 
    =3:被动胜败 
    */
}a[N];

void ins(char *s){
    int x=0;
    for(int i=0;s[i];i++){
        int k=s[i]-'a';
        if(!a[x].nxt[k]) a[x].nxt[k]=++cnt;
        x=a[x].nxt[k];
    }
}

void dfs(int x){
    int son=0,cnt[4]={0};
    for(int i=0;i<26;i++) if(a[x].nxt[i]){
        dfs(a[x].nxt[i]);
        son++;
        cnt[a[a[x].nxt[i]].s]++;
    }
    if(!son){
        a[x].s=1;
        return ;
    } 
    if(cnt[0]) a[x].s=1;
    if(cnt[1]) a[x].s=0;
    if(cnt[0]&&cnt[1]) a[x].s=3;
    if(cnt[3]==son) a[x].s=2;
    if(cnt[2]) a[x].s=3;
}

signed main(){
    read(n);read(k);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        ins(s);
    }
    dfs(0);
    if(a[0].s==2){
        puts("Second");
        return 0;
    }
    if(a[0].s==0&&!(k&1)){
        puts("Second");
        return 0;
    }
    if(a[0].s==1){
        puts("Second");
        return 0;
    }
    puts("First");
}