CodeForces 455B A Lot of Games （博弈论）

A Lot of Games

题目链接：

http://acm.hust.edu.cn/vjudge/contest/121334#problem/J

Description

Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players.

Given a group of n non-empty strings. During the game two players build the word together, initially the word is empty. The players move in turns. On his step player must add a single letter in the end of the word, the resulting word must be prefix of at least one string from the group. A player loses if he cannot move.

Andrew and Alex decided to play this game k times. The player who is the loser of the i-th game makes the first move in the (i + 1)-th game. Guys decided that the winner of all games is the player who wins the last (k-th) game. Andrew and Alex already started the game. Fedor wants to know who wins the game if both players will play optimally. Help him.

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 Input

Input
2 3
a
b
Output
First
Input
3 1
a
b
c
Output
First
Input
1 2
ab
Output
Second

##题意：给出n个字符串(总长度不超过10^5); A B两人轮流进行如下操作： 1. 初始时目标串为空 2. 当前玩家在目标串末尾添加一个字符 3. 要求每次添加后的目标串是给出的任一字符串的前缀 4. 不能操作者输 (游戏共进行k轮，每轮输者在下一轮为先手)
##题解：首先这是一个博弈论问题. 要求每次目标串都是给定串的前缀，很自然想到用字典树来建模. 这个游戏有一个特别的地方：本局的赢家在下局是后手. 这意味着玩家可能会选择输掉当前局来获取最后的胜利. 我们只用处理单局的情况： 1. 如果先手在单局中处于必输状态，那么他一定会输掉最后的比赛(一直输). 2. 如果先手在单局中有必胜的走法，那么他不一定会选择在所有情况下都赢. 1. 如果先手可以控制自己必输或必赢，那么他一定会赢得最后的比赛(一直输,最后一场选择胜利). 2. 如果先手只能赢无法输(比如只有一个字符)，那么他的结果取决与k的奇偶性(奇胜偶败).

综上，只需要处理出单局中先手是必输/必胜/可输可赢，这里采用两次dfs来完成判断：
1. 再搜索是否有必败的走法(叶结点必输，可到必胜的点为必输，只能到必输的点为必胜).

##代码： ``` cpp #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 101000 #define mod 100000007 #define inf 0x3f3f3f3f #define IN freopen("in.txt","r",stdin); using namespace std;

struct Trie
{
bool isStr;
int next;
Trie(){isStr=false;next=-1;}
}trie[maxn][26];
int cnt;
void insert(char s)
{
int len=strlen(s),cur=0;
for(int i=0;i<len;i++)
{
if(trie[cur][s[i]-'a'].next==-1)
trie[cur][s[i]-'a'].next=++cnt; / from 1; 0 is root /
if(i==len-1)
trie[cur][s[i]-'a'].isStr=true;
cur=trie[cur][s[i]-'a'].next;
}
}
/以上为字典树模版*/

int n,m;
char str[maxn];

/*
1表示当前局面存在必胜走法; 0表示只有必败.
子节点中有0则1，全1则0.
*/
int dfs(int cur) {
int ans = 0;
int cnt = 0;
for(int i=0; i<26; i++) {
if(trie[cur][i].next != -1)
cnt+=1, ans += dfs(trie[cur][i].next);
}
if(cnt == ans) return 0;
else return 1;
}

/*
1表示当前局面存在必输走法; 0表示只有必赢.
子节点中有0则1，全1则0.
*/
int dfs2(int cur) {
int ans = 0;
int cnt = 0;
for(int i=0; i<26; i++) {
if(trie[cur][i].next != -1)
cnt+=1, ans += dfs2(trie[cur][i].next);
}
if(!cnt) return 1;
if(cnt == ans) return 0;
else return 1;
}

void init() {
for(int i=0; i<maxn; i++) {
for(int j=0; j<26; j++) {
trie[i][j].isStr = 0;
trie[i][j].next = -1;
}
}
}

int main(int argc, char const *argv[])
{
//IN;

while(scanf("%d %d", &n,&m) != EOF)
{
    init();
    while(n--) {
        scanf("%s", str);
        insert(str);
    }

    int ans1 = dfs(0);
    if(!ans1) {
        puts("Second"); continue;
    }

    int ans2 = dfs2(0);
    if(!ans2) {
        if(m&1) puts("First");
        else puts("Second");
    } else {
        puts("First");
    }
}

return 0;

}