codeforces 455B A Lot of Games（博弈，字典树）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn=1000010;
 8 
 9 struct Trie //字典树查询字符串
10 {
11     int ch[maxn][26];
12     int sz; //结点总数
13     void clear(){sz=1;memset(ch[0],-1,sizeof(ch[0]));}
14     int Num(char ch){ return ch-‘a‘;}
15     void insert(char *s)
16     {
17         int len=strlen(s),u=0;
18         for(int i=0;i<len;i++)
19         {
20             int c=Num(s[i]);
21             if(ch[u][c]==-1)
22             {
23                 memset(ch[sz],-1,sizeof(ch[sz]));
24                 ch[u][c]=sz++;
25             }
26             u=ch[u][c];
27         }
28     }
29 }trie;
30 
31 int solve(int d)
32 {
33     int ans=0;
34     int flag=1;
35     for(int i=0;i<26;i++)
36     {
37         if(trie.ch[d][i] != -1)
38         {
39             flag=0;
40             ans|=solve(trie.ch[d][i]);
41         }
42     }
43     if(flag)
44         ans=1;
45     return 3-ans;
46 }
47 
48 int main()
49 {
50     int n,m;char s[maxn];
51     while(~scanf("%d%d",&n,&m))
52     {
53         trie.clear();
54         while(n--)
55         {
56             scanf("%s",s);trie.insert(s);
57         }
58         int ans = 3 - solve(0);
59         if(ans==3) printf("First\n");
60         else if(ans==1||ans==0) printf("Second\n");
61         else 
62         {
63             if(m&1) printf("First\n");
64             else printf("Second\n");
65         }
66     }
67     return 0;
68 }