http://codeforces.com/problemset/problem/456/d
Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players.
http://kugwzk.info/index.php/archives/2307
https://zepto.page/post/codeforces-456d
https://bartholomew.cf/2018/07/07/codeforces-455b-a-lot-of-games/
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).
Examples
input
Copy
2 3 a b
output
Copy
First
input
Copy
3 1 a b c
output
Copy
First
input
Copy
1 2 ab
output
Copy
Second
http://kugwzk.info/index.php/archives/2307
题意：给出n个字符串，要求两人轮流对一个空串进行操作，每次在末尾添加一个字符要求添加完后字符串必须是这n个字符串中的某个字符串的前缀。当某个人无法操作视为输。假如某个人在第i轮输掉，那么它在第i+1轮就是先手，那么问在第k轮的时候是第一轮的先手还是后手胜利。
假如只有一轮，我们只需要建立字典树，然后dfs推出来必胜必败态就可以了。但是现在是第k轮的胜败。所以我们必须要考虑在这一轮赢是否是真正优的决策。
假如先手只能输的话，那么他将会一直输，所以导致第k轮也是输。即第一轮的先手必败。
假如先手只能赢的话，那么他们有任何可以选择的余地，所以第k轮的胜负和k的奇偶性有关。
假如先手可以自己决定胜利还是输的话，那么他可以输掉前k-1轮，保证第k轮自己的先手然后获胜就行了。所以是还是第一轮先手必胜。
假如先手无法决定自己胜利还是输的话，那么就相当于后手可以决定胜负，那么先手必败。因为后手一定可以做出对自己有利的决策。
现在考虑状态如何转移：假如一个状态的后继都是只能输的状态，那么这个就是只能赢的状态。
假如一个状态的后继都是只能赢的状态，那么这个就是只能输的状态。
假如一个状态的后继中存在只能输和只能赢的后继，或者是他的后继中有无法自己决策输赢的情况，那么他就是可以自己决定胜负的状态。
同理自己无法决定胜负的状态一定是后继中只有可以自己决定胜负的状态。
然后dfs一下，可以求出字典树root的状态，然后讨论一下就好了。
typedef long long ll;
int n,k;
int root,tot,Next[maxn+10][SIGMA],dp[maxn+10];
inline int newnode(){
REP(i,0,SIGMA) Next[tot][i]=-1;
tot++;
return tot-1;
}
inline int get_idx(char c){
return c-'a';
}
inline void Insert(char s[]){
int len=strlen(s);
int now=root;
REP(i,0,len){
int tmp=get_idx(s[i]);
if(Next[now][tmp]==-1)
Next[now][tmp]=newnode();
now=Next[now][tmp];
}
}
int dfs(int rt){
dp[rt]=0;int cnt=0;
int flag1=0,flag2=0,flag3=0,flag4=0;
REP(i,0,SIGMA){
if(Next[rt][i]==-1) continue;
cnt++;
int tmp=dfs(Next[rt][i]);
if(tmp==1) flag1=1; //后继有只能败
else if(tmp==2) flag2=1; //后继有只能胜
else if(tmp==3) flag3=1; //后继有可以自我决定
else if(tmp==4) flag4=1; //后继无法自我决定
}
if(!cnt) return dp[rt]=1; //只能败
if(flag2==1&&flag1==0&&flag3==0&&flag4==0) return dp[rt]=1;
if(flag1==1&&flag2==0&&flag3==0&&flag4==0) return dp[rt]=2;
if(flag1==1&&flag2==1||(flag4==1)) return dp[rt]=3;
if(flag3==1&&flag1==0&&flag2==0&&flag4==0) return dp[rt]=4;
return dp[rt];
}
int main()
{
scanf("%d %d",&n,&k);
root=newnode();
REP(i,1,n+1){
char s[maxn];scanf(" %s",s);
Insert(s);
}
dfs(root);
if(dp[root]==1) puts("Second");
else if(dp[root]==2){
if(k&1) puts("First");
else puts("Second");
}
else if(dp[root]==3) puts("First");
else puts("Second");
}
https://zepto.page/post/codeforces-456d
int n,k,root,top,q[maxn][26];
char x[maxn];
void insert(){
int len=strlen(x);
int now=root;
for (int i=0;i<len;i++){
int temp=x[i]-'a';
if (!q[now][temp]) q[now][temp]=++top;
now=q[now][temp];
}
}
int dfs(int now){
int flag=1,ans;
for (int i=0;i<26;i++){
if (q[now][i]){
flag=0;
ans|=dfs(q[now][i])^3;
}
}
if (flag) ans=1;
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
for (int i=1;i<=n;i++)
cin>>x,insert();
int ans=dfs(root);
if (ans==3||ans==2&&k&1) cout<<"First"<<endl;
else cout<<"Second"<<endl;
}
https://bartholomew.cf/2018/07/07/codeforces-455b-a-lot-of-games/
易得如果此人能够有该局必胜的把握与必输的把握, 那么他必赢, 因为可以一直输再最后赢, 如果必输的就是必输局, 而如果一直赢的话就可以看 K 的奇偶性来判断, 奇数局先手赢, 偶数局后手赢!
那么我们知道先手与后手的目的都是一致的, 即那么都希望赢, 要么都希望输. 当然不会出现一个人想赢一个人想输的局面, 因为这样胜负已定, 就不是最优策略了!
我们的两遍dfs:
- 必胜点的条件是周围有一个必输点, 必输点的条件是周围都是必胜点
- 必胜点的条件是周围都是必输点, 必输点的条件是周围有一个必胜点
