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

题目

参考自博客：http://blog.csdn.net/keshuai19940722/article/details/38455269

//字典树，博弈

根据当前节点的后续来确定当前节点的状态，0是由对手决定，1是只有可能输，2是只有可能赢，3是可以决定自己的胜负。这些状态是要综合所有后续情况确定的。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
int pos=0;
string s;

struct tt
{
    int val,arr[30];
    tt(){memset(arr,-1,sizeof(arr));val=0;}
}a[1000010];

void insert(int id,int d)
{
    if(d==s.length())return ;

    int t=s[d]-'a';
    if(a[id].arr[t]==-1)
        a[id].arr[t]=++pos;
    insert(a[id].arr[t],d+1);
}

int solve(int d)
{
    int ans=0;
    int flag=1;
    for(int i=0;i<26;i++)
    {
        if(a[d].arr[i]!=-1)
        {
            flag=0;
            ans|=solve(a[d].arr[i]);
        }
    }

    if(flag)
        ans=1;
    return 3-ans;
}
int main()
{
    int n,m;
    cin>> n>>m;
    pos=0;
    while(n--)
    {
        cin>>s;
        insert(0, 0);
    }
    int ans = 3 - solve(0);

    if(ans==3)cout <<"First"<<endl;
    else if(ans==1||ans==0)cout <<"Second"<<endl;
    else 
    {
        if(m&1)cout <<"First"<<endl;
        else cout <<"Second"<<endl;
    }
    return 0;
}