CF456D A Lot of Games (字典树+DP)

D - A Lot of Games

CF#260 Div2 D题

CF#260 Div1 B题

Codeforces Round #260

CF455B

D. A Lot of Games time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players. Given a group of n non-empty strings. During the game two players build the word together, initially the word is empty. The players move in turns. On his step player must add a single letter in the end of the word, the resulting word must be prefix of at least one string from the group. A player loses if he cannot move. Andrew and Alex decided to play this game k times. The player who is the loser of the i-th game makes the first move in the (i + 1)-th game. Guys decided that the winner of all games is the player who wins the last (k-th) game. Andrew and Alex already started the game. Fedor wants to know who wins the game if both players will play optimally. Help him. Input The first line contains two integers, n and k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109). Each of the next n lines contains a single non-empty string from the given group. The total length of all strings from the group doesn't exceed 105. Each string of the group consists only of lowercase English letters. Output If the player who moves first wins, print "First", otherwise print "Second" (without the quotes). Sample test(s) Input 2 3 a b Output First Input 3 1 a b c Output First Input 1 2 ab Output Second

题意：两个人玩游戏。游戏是拼单词，给出了一个含有n个单词的词库。当前单词初始为空，每个人轮流给它末尾加一个字母，要求当前单词是词库中任意一个词的前缀，当某个人不能加字母了他就输。这个游戏重复k局，一局输的人下一局先手，最后一局定胜负。两个人都不蠢，求第一局先手是否能保证最后能赢，能就输出First，不能则输出Second。

题解：

Trie树+树DP。

先把词典各词加入Trie树，则Trie树每个节点都为游戏中的某一步，游戏就变成从这棵树树根开始轮流向下走一步，看谁能走到叶子。

这样，每个节点可能有4种状态，分别是必赢、必输、能输能赢（想怎样就怎样）、不能输不能赢（走这步会让对面变得能输能赢）。

叶子节点都是必赢。只有一个必赢儿子的点必输，只有一个必输儿子的点必赢。接下来我们主要考察有多个儿子的特殊情况。

我们可以统计儿子有哪些种类，即统计儿子中是否有能输能赢点、不能输不能赢点、必输点、必赢点，

　　1.若儿子中有能输能赢点，则对手肯定怒走那个点，则当前这个点是不能输不能赢点。

　　2.若儿子中又有赢点又有输点，对手可以随便选，则当前这个点也是不能输不能赢点。

　　3.若儿子中只有不能输不能赢点，则对手只能走这个逗点，则当前这个点是能输能赢点。

　　4.若儿子只有赢点，当前点肯定是输点；若儿子只有输点，当前点肯定是赢点。

这样，我们一遍dfs就可以得到所有点的状态，简直树DP。

最后简单判断一下到底第一局先手能不能赢。

　　1.假如每局先手能输能赢，则第一局先手的人可以连输k-1场，保证先手权，最后一场赢。

　　2.假如每局先手必赢，则后手必输，先手想输也输不掉，这样两个人轮流赢，若k是奇数，则第一局先手的人最后一局赢。

　　3.除了这些情况之外，先手都不能必赢。

代码：

 //#pragma comment(linker, "/STACK:102400000,102400000")
 #include<cstdio>
 #include<cmath>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 #include<cmath>
 #include<map>
 #include<set>
 #include<stack>
 #include<queue>
 using namespace std;
 #define ll long long
 #define usint unsigned int
 #define mz(array) memset(array, 0, sizeof(array))
 #define minf(array) memset(array, 0x3f, sizeof(array))
 #define REP(i,n) for(i=0;i<(n);i++)
 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
 #define RD(x) scanf("%d",&x)
 #define RD2(x,y) scanf("%d%d",&x,&y)
 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
 #define WN(x) printf("%d\n",x);
 #define RE  freopen("D.in","r",stdin)
 #define WE  freopen("1biao.out","w",stdout)

 const int maxn=;
 int n,k;
 char s[maxn];
 int chd[maxn][];
 int canwin[maxn],canlose[maxn];
 int tn;
 int ID[];

 void insert(char *s) {
     int len=strlen(s),i;
     int now=;
     for(i=; i<len; i++) {
         if(!chd[now][ID[s[i]]]) chd[now][ID[s[i]]]=tn , now=tn++;
         else now=chd[now][ID[s[i]]];
     }
 }

 void dfs(int x) {
     int i;
     bool last=true;
     bool cwin=,close=,canwinlose=,cant=;
     for(i=; i<; i++) {
         if(chd[x][i]!=) {
             //printf("%c:",'a'+i);
             dfs(chd[x][i]);
             last=false;
             if(canwin[chd[x][i]]){///统计儿子有4种点中的哪些点
                 if(canlose[chd[x][i]])canwinlose=;
                 else cwin=;
             }
             else {
                 if(canlose[chd[x][i]]) close=;
                 else cant=;
             }
         }
     }
     canwin[x]=;canlose[x]=;///初始化为0,0
     if(last)canwin[x]=;
     else{
         if(canwinlose==){///如果儿子里有有能赢又能输的点，当前点肯定是0,0，没有这种点才继续看
             if(!(cwin && close)){///如果儿子里又有赢点又有输点，当前点肯定是0,0，不是这种情况才继续看
                 if(cant && !cwin && !close)///如果儿子只有0,0点，当前点肯定是1,1点
                     canwin[x]=,canlose[x]=;
                 else if(cwin)///如果儿子只有赢点，当前点肯定是输点
                     canlose[x]=;
                 else if(close)///儿子只有输点，当前点肯定是赢点
                     canwin[x]=;
             }
         }
     }
     //printf("(%d,%d)",canwin[x],canlose[x]);
 }

 int main() {
     int i,j;
     REP(i,) {
         ID[i+'a']=i;
     }
     while(scanf("%d%d",&n,&k)!=EOF) {
         mz(chd);
         tn=;
         for(i=; i<n; i++) {
             scanf("%s",s);
             insert(s);
         }
         canwin[]=;canlose[]=;
         for(i=; i<; i++) {///众起点中有赢点，走这个点就必赢；有输点，走这个点就必输。
             if(chd[][i]!=) {
                 dfs(chd[][i]);
                 if(canwin[chd[][i]])canwin[]=;
                 if(canlose[chd[][i]])canlose[]=;
                 //printf("%c,%d,%d\n",'a'+i,canwin[chd[0][i]],canlose[chd[0][i]]);
             }
         }
         //printf("%d,%d\n",canwin[0],canlose[0]);
         bool first=false;
         if(canwin[])
             if(canlose[]) first=true;///能输能赢，乃真正法器（连输，最后赢一局）
             else if((k&)==)first=true;///能赢不能输，则必轮流赢
         ///其他情况不能必赢
         if(first)puts("First");
         else puts("Second");
     }
     return ;
 }