题目链接：http://codeforces.com/problemset/problem/455/B
题意：
给你n个字符串，然后进行k局游戏。
每局游戏开始有一个空串，然后双方轮流给这个串的末尾添加字符，并保证新字符串是n个字符串中至少一个串的前缀。
当一方不能添加字符时，这一方输，游戏结束。
每场游戏结束后，这场游戏输的人会成为下一句游戏的先手。
谁赢得了最后一场比赛，谁才会真正赢得比赛。
问你最终真正赢得比赛的人，是第一局游戏的先手还是后手（分别称为First和Second）。
题解：
先考虑单局游戏。
先对原来的n个串，建立一棵trie树。
那么原游戏就变成了：
最初有一个棋子在根节点，双方轮流将棋子向下移一格，不能移动的一方输。
因为每场游戏都是一模一样的，所以每场游戏先手必胜还是必败也是确定的。
所以游戏的最终赢家取决于，谁能够拿到最后一场游戏的必胜方。
所以要求的也就不单单是先手是必胜还是必败了。
而是要分别求：先手能否必胜，和先手能否必败。
一遍dfs就能解决。
然后分情况讨论：
（1）先手只能必胜，不能必败：
则奇数局的先手是First，First必胜。
偶数局的先手是Second，Second必胜。
（2）先手可以必胜，也可以必败：
那么First会一直让自己输，一直让自己是先手，直到最后一局再赢。
所以此时First必胜。
（3）先手不能必胜，只能必败：
也就是无论怎样操作，First一直都是先手，所以Second必胜。
（4）先手不能必胜，也不能必败：
也就是后手既可以必胜，也可以必败。
所以后手会一直让自己赢，一直让自己是后手，所以Second必胜。
AC Code:
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #define MAX_N 100005 5 #define MAX_L 100005 6 #define MAX_A 30 7 8 using namespace std; 9 10 struct Node 11 { 12 int nex[MAX_A]; 13 Node() 14 { 15 memset(nex,0,sizeof(nex)); 16 } 17 }; 18 19 int n,k; 20 int cnt=1; 21 bool win[MAX_L]; 22 bool lose[MAX_L]; 23 string s[MAX_N]; 24 Node node[MAX_L]; 25 26 void read() 27 { 28 cin>>n>>k; 29 for(int i=1;i<=n;i++) 30 { 31 cin>>s[i]; 32 } 33 } 34 35 void init_trie() 36 { 37 for(int i=1;i<=n;i++) 38 { 39 int now=1; 40 for(int j=0;j<s[i].size();j++) 41 { 42 if(!node[now].nex[s[i][j]-'a']) 43 { 44 node[now].nex[s[i][j]-'a']=++cnt; 45 } 46 now=node[now].nex[s[i][j]-'a']; 47 } 48 } 49 } 50 51 void dfs(int now) 52 { 53 win[now]=lose[now]=false; 54 bool flag=true; 55 for(int i=0;i<26;i++) 56 { 57 if(node[now].nex[i]) 58 { 59 dfs(node[now].nex[i]); 60 win[now]|=(!win[node[now].nex[i]]); 61 lose[now]|=(!lose[node[now].nex[i]]); 62 flag=false; 63 } 64 } 65 if(flag) lose[now]=true; 66 } 67 68 void work() 69 { 70 init_trie(); 71 dfs(1); 72 if(win[1] && !lose[1]) cout<<((k&1)?"First":"Second")<<endl; 73 else if(win[1] && lose[1]) cout<<"First"<<endl; 74 else cout<<"Second"<<endl; 75 } 76 77 int main() 78 { 79 read(); 80 work(); 81 }