题意：

　　A和B轮流在建造一个字，每次添加一个字符，要求是给定的n个串的某一个的前缀，不能添加字符的人输掉游戏，输掉的人先手下一轮的游戏。问A先手，经过k轮游戏，最后胜利的人是谁。

思路：

　　很显然先将n个字符串插入到字典树上，因为字典树上有分叉，不能仅仅判断字符串长度奇偶性来判断。字典树看成无环的状态图，如果按照拓扑排序逆序进行排序，在判断每个节点的时候，它的后继都已经判断过了。定义两个数组can_win[u], can_lose[u]，表示u节点走下去“可能赢吗？”以及u节点走下去”可能输吗？“，那么取反就是必胜和必败态了，“可能赢”<-对手下一步不可能赢，”可能输“<-对手下一步不可能输。

代码：

#include 
     
      const int N = 1e5 + 5;char str[N];int ch[N][26];int sz;bool can_win[N], can_lose[N];void init() {    memset (ch[0], 0, sizeof (ch[0]));    sz = 1;}void insert(char *s) {    int u = 0, c;    for (int i=0; s[i]; ++i) {        c = s[i] - 'a';        if (!ch[u][c]) {            memset (ch[sz], 0, sizeof (ch[sz]));            ch[u][c] = sz++;        }        u = ch[u][c];    }}void DFS(int u) {    can_win[u] = can_lose[u] = false;    bool is_leaf = true;    for (int c=0; c<26; ++c) {        int v = ch[u][c];        if (v) {            is_leaf = false;            DFS (v);            can_win[u] |= !can_win[v];            can_lose[u] |= !can_lose[v];        }    }    if (is_leaf) {        can_lose[u] = true;    }}int main() {    int n, k;    scanf ("%d%d", &n, &k);    init ();    for (int i=0; i