codeforces 456 D. A Lot of Games（字典数+博弈+思维+树形dp）

题目链接：http://codeforces.com/contest/456/problem/D

题意：给n个字符串。进行k次游戏。每局开始，字符串为空串，然后两人轮流在末尾追加字符，保证新的字符串为集合中某字符串的前缀，不能操作者输，新一轮由上一句输的人先手。

题解：先确定一下状态，如果是先手必定赢得话那么就喝k的奇偶性有关系。如果后手必赢那么肯定是后手赢。如果是先手决定输赢的话，那么只要先手的一开始一直让后手赢最后赢一把就行先手必胜，如果是后手决定输赢的话那么显然同理后手必胜。

那么在说一下这题的处理方法显然用字典数比较好处理。然后就是如何判断先手必胜，很明显只要是每一个分支都是奇数个点的话肯定是先手必胜，如果每一个分支都是偶数的话，那么显然后手必胜，如果既有奇数条又有偶数条那么就要判断以当前分支点为起点的必胜态再递推上去。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int M = 1e5 + 10;

struct TnT {

    TnT *next[27];

    int vis;

    TnT():vis(0) {memset(next , 0 , sizeof(next));}

};

void build(TnT *root , char s[]) {

    int len = strlen(s);

    TnT *p = root;

    for(int i = 0 ; i < len ; i++) {

        int id = s[i] - 'a';

        if(p->next[id] == NULL) {

            p->next[id] = new TnT();

        }

        p = p->next[id];

        p->vis++;

    }

}

void de(TnT *root) {

    if(root == NULL) return ;

    for(int i = 0 ; i < 26 ; i++) de(root->next[i]);

    delete root;

}

void find(TnT *root , int &x , int &y) {

    TnT *p = root;

    x = 0 , y = 0;

    //x=1表示先手必胜，y=1表示后手必胜x=1&&y=1表示先手决定胜负，x=0&&y=0表示后手决定状态，具体画一下图就知道了。

    int u , v;

    bool flag = true;

    for(int i = 0 ; i < 26 ; i++) {

        if(p->next[i]) {

            flag = false;

            find(root->next[i] , u , v);

            if(!u) x = 1;

            if(!v) y = 1;

            //奇偶变化一次x，y就取反，当然如果当前点是分支点的话那么他最终的胜负状态就要结合所有分支节点的状态。

        }

    }

    if(flag) x = 0 , y = 1;

}

char s[M];

int main() {

    int n , m;

    scanf("%d%d" , &n , &m);

    TnT *root = new TnT();

    for(int i = 0 ; i < n ; i++) {

        scanf("%s" , s);

        build(root , s);

    }

    int x , y;

    find(root , x , y);

    de(root);

    if(x && y) puts("First");

    else if((m & 1) && x) puts("First");

    else puts("Second");

    return 0;

}