[CF 455B] A Lot of Games

作法：

首先當然是決定如果$k=1$時誰有必勝策略，這可以先建出所有字串的 trie 後DP得到。這樣解決了$k=1$的問題，但$k=2$時可能第一局先手故意輸掉，下一局再用必勝策略獲勝之類的（因為下一場的先手會給輸方），因此我們還需知道誰有必敗策略，這和必勝策略的求法幾乎一樣。有了這兩個之後就只要討論四種情形就好了：能夠必勝的是先手還後手，能夠必敗的是先手還後手（這個必敗指的是他可以強迫自己輸，而不是他的對手有必勝策略）。如果後手能夠必勝，那麼他就一路贏到底就好了。否則當先手必勝時，討論一下即可知道當先手可以必敗時必定先手贏，後手可以必敗時則是當$k$是奇數時先手贏了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
int ch[maxn][26],ccnt ;
bool leaf[maxn] ;
void insert(char *t)
{
    for(int i=0,u=0;t[i];i++)
    {
        int c=t[i]-'a' ;
        if(!ch[u][c]) ch[u][c]=++ccnt ;
        u=ch[u][c] ;
    }
}
 
int dp1[maxn],dp2[maxn] ;
void DP(int x)
{
    if(leaf[x]){dp1[x]=0 ; dp2[x]=1 ; return ;}
    for(int i=0;i<26;i++) if(ch[x][i])
    {
        int to=ch[x][i] ;
        DP(to) ;
        if(!dp1[to]) dp1[x]=1 ;
        if(!dp2[to]) dp2[x]=1 ;
    }
}
 
char s[maxn] ;
main()
{
    int n,k ; scanf("%d%d",&n,&k) ;
    while(n--) scanf("%s",s) , insert(s) ;
    for(int i=1;i<=ccnt;i++)
    {
        leaf[i]=1 ;
        for(int j=0;j<26;j++) if(ch[i][j])
            {leaf[i]=0 ; break ;}
    }
    DP(0) ;
    if(!dp1[0] || (dp1[0] && !dp2[0] && k%2==0)) printf("Second\n") ;
    else printf("First\n") ;
}