D. A Lot of Games
time limit per test 1 second
memory limit per test 256 megabytes
input standard input
output standard output

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个字符串，然后这两个人就在一个空的字符串中填字母，填字母的规则是：保证添加字母后的字符串为n个字符串中某个字符串的前缀。二人每次轮流填一个字母，直到某人无法填入字母来满足规则。这个人就输了。然后开始下一局游戏。下一局的先手为上一局输的人。求在第k局的时候，是先手赢还是后手赢（这里说的先手为第一局的先手）。
若先手赢则输出”First”否则输出”Second”

在这里，对于先手（这里的先手为本局的先手）来说有四种情况，先手必输、先手必赢、先手可以控制自己的输赢、先手不可控自己的输赢（由后手控制）。

我们用(xx)来表示这四种情况，第一位表示是否可以赢，第二位表示是否可以输。

(01) 对于先手必输，那么下一局他还是先手(因为上一局他输了),然后一直输到k局，先手还是输，则输出”Second”。
(10) 对于先手必赢，那么下一局他为后手，再下一局他又为先手，根据奇偶判断，当为奇数的时候先手赢，为偶数的时候后手赢。
(11) 对于先手可控输赢，那么他可以使自己前k-1局都输，最后一局赢。
(00) 对于先手不可控，那么对手可以让他前k-1局一直赢，最后一局输。
接下来就要开始思考，怎样来判断这四种情况。
我们知道，当游戏结束的条件是，无法再往字符串中添加字母，也就是说，这个字符串已经和某个字符串相等了。因为是依次添加，所以只要知道这个字符串的长度的奇偶，就可以判断出先手的输赢。但是前缀可能不止一个串，例如：
abcde abcedf
这两个串，当填到abc的时候，就会发生分支，因为两个串的长度差1,所以会造成输赢的差异。当下一个填d的时候，先手赢，但是当c后面填e的时候，后手赢。所以本局游戏的胜负掌握在填第四个字母的人手里，4为偶，所以是后手掌握了输赢，所以用我们的数字表示即为(00)先手不可控输赢。但如果两个字符串的长度一样则会产生(10)或(01)的情况，因为不管选哪个，长度是一样的。

所以我们需要保存每一次(xx)的情况。

首先建立一颗字典树。数据结构如下

struct Trie;  
typedef struct Trie *PTrie;  
struct Trie{  
    int info;   //字典值(0~25)  
    int num;    //下节点数量  
    PTrie next[M];  //下节点数;  
    int aut;    //裁决人-下次选择的人  
    //int val;  //返回值 (00 均不可控、01 输可控 10 赢可控 11 输赢均可控)  
    Trie(int x, int y){  
        info = x;  
        num = 0;  
        aut = y;  
        for(int i=0;i<26;i++){  
            next[i] = NULL;  
        }  
    }  
};  

这不是一颗正常的字典树，info 值 在本程序里没有用上，不过不影响大局，只是内存多一点。
首先根据叶子节点的aut值，来判断(xx)为多少，若aut == 1 那么 val = 2 (10)，若 aut == 0 那么 val = 1 (01) 。
然后沿着字典树向上回溯，若他的上一个节点只有一个分支，那么就不需要判断，继续进行回溯，直到遇到有多个分支的节点。
当如到有多个分支的节点，每个分支都有一个val值，如果这个节点的裁决人(aut)是先手，那么他便用有这些分支的所有情况，所以用’或’运算来统计该节点的val值，即 val |= next[i]->val
同理，当该节点的裁决人是后手，那么，先手就无法控制这些情况，但是下属分支的val都一样，那么后手同样无法控制，则代表后手在这个节点的选择权无效，那么先手仍然有控制权，所以为了保证所有的情况都是一样的，进行与运算 val &= next[i]->val
说的有点不清楚，自己举个例子就明白了。例如：abcde abcee 后手是有选择权的，但是结果最后还是(01)。
基本上的思路有了，那么就进行回溯的操作。

int solo(PTrie pt){  
    if(pt->num == 0){  
        return pt->aut+1;    //1(01)为输,2(10)为赢  
    }  
    int i,va;  
    if(pt->aut){  
        va = 3;  
        for(i=0;i<26;i++){  
            if(pt->next[i]!=NULL){  
                va &= solo(pt->next[i]);  
            }  
        }  
    }else{  
        va = 0;  
        for(i=0;i<26;i++){  
            if(pt->next[i]!=NULL){  
                va |= solo(pt->next[i]);  
            }  
        }  
    }  
    return va;  
}  

获得最后返回的va 然后根据va的值 转换成二进制 进行判断。

int x = solo(pt);  
    //cout<<"val = "<<x<<endl;  
    if(x == 1){  
        cout<<"Second"<<endl;  
    }else if(x == 3){  
        cout<<"First"<<endl;  
    }else if(x == 0){  
        cout<<"Second"<<endl;  
    }else if(k%2){  
        cout<<"First"<<endl;  
    }else{  
        cout<<"Second"<<endl;  
    }  

最后贴完整代码，提示：内存可以优化，时间可以降低。因为这个递归进行了许多不必要的操作。
因为不会用二维数组形式的字典树，只能用数据结构来写了

///Time     Memory  
///46 ms    12220 KB  
///codeforces content#260 D A Lot of Games  

#include <iostream>  
#include <string>  
using namespace std;  
const int M = 26;  
struct Trie;  
typedef struct Trie *PTrie;  
struct Trie{  
    int info;   //字典值(0~25)  
    int num;    //下节点数量  
    PTrie next[M];  //下节点数;  
    int aut;    //裁决人-下次选择的人  
    int val;    //返回值 (00 均不可控一般不存在、01 输可控 10 赢可控 11 输赢均可控)  
    Trie(int x, int y){  
        info = x;  
        num = 0;  
        aut = y;  
        for(int i=0;i<26;i++){  
            next[i] = NULL;  
        }  
    }  
};  
int toi(char c){  
        return c-'a';  
}  
PTrie new_t(int num,int aut){  
    PTrie pt = new Trie(num,aut);  
}  
void insert(string s,PTrie pt){  
    int n = s.length();  
    int i,c;  
    for(i=0;i<n;i++){  
        c = toi(s[i]);  
        if(pt->next[c]!=NULL){  
            pt = pt->next[c];  
            continue;  
        }else{  
            pt->next[c] = new Trie(c,(i+1)%2);  
            pt->num++;  
            pt = pt->next[c];  
        }  
    }  
}  
void output(PTrie pt){  
    if(pt == NULL)return;  
    cout<<"=========="<<endl;  
    cout<<"info= "<<pt->info<<endl;  
    cout<<"num = "<<pt->num<<endl;  
    cout<<"auto= "<<pt->aut<<endl;  
    if(pt->num == 0)return;  
    int i;  
    for(i=0;i<26;i++){  
        if(pt->next[i]!=NULL)output(pt->next[i]);  
    }  
}  
int solo(PTrie pt){  
    if(pt->num == 0){  
        return pt->aut+1;    //1(01)为输,2(10)为赢  
    }  
    int i,va;  
    if(pt->aut){  
        va = 3;  
        for(i=0;i<26;i++){  
            if(pt->next[i]!=NULL){  
                va &= solo(pt->next[i]);  
            }  
        }  
    }else{  
        va = 0;  
        for(i=0;i<26;i++){  
            if(pt->next[i]!=NULL){  
                va |= solo(pt->next[i]);  
            }  
        }  
    }  
    return va;  
}  
void test(){  
    int y = 3&2;  
    cout<<"11&10 = "<<y<<endl;  
    y = 2|1;  
    cout<<"10|01 = "<<y<<endl;  
}  
int main(){  
    int n;  
    long k;  
    cin>>n>>k;  
    string s;  
    PTrie pt = new Trie(-1,0);  
    for (int i = 0; i < n; ++i)  
    {  
        cin>>s;  
        insert(s,pt);  
    }  
    //output(pt);  
    int x = solo(pt);  
    //cout<<"val = "<<x<<endl;  
    if(x == 1){  
        cout<<"Second"<<endl;  
    }else if(x == 3){  
        cout<<"First"<<endl;  
    }else if(x == 0){  
        cout<<"Second"<<endl;  
    }else if(k%2){  
        cout<<"First"<<endl;  
    }else{  
        cout<<"Second"<<endl;  
    }  
    return 0;  
}