Codeforces Round #260 (Div. 2) D. A Lot of Games(树上博弈)
程序员文章站
2022-06-26 10:12:57
...
题目链接
思路:此题的关键是判断k先手的时候状态是赢还是输。不过有些细节还是没搞清楚,留坑。
#include<bits/stdc++.h>
using namespace std;
const int maxn =1e6+1;
int cnt=0,trie[maxn][26];
void insert(string s){
int u = 0;
for(int i = 0; i < s.size(); i++){
if(!trie[u][s[i]-'a']) trie[u][s[i]-'a'] = ++cnt;
u = trie[u][s[i]-'a'];
}
}
bool dfs1(int id){
for(int i = 0; i < 26; i++){
if(trie[id][i]!=0){
if(!dfs1(trie[id][i])){//儿子只要有一个输态,父亲就是胜态
return 1;
}
}
}
return 0;//儿子若是全是胜态,则父亲自己就是输态
}
bool dfs2(int id){
int ans = 0,flag = 1;
for(int i = 0; i < 26; i++){
if(trie[id][i] != 0){
flag = 0;
if(!dfs2(trie[id][i]))
return 1;
}
}
if(flag) return 1;
return 0;
}
int main(){
string s;
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
cin>>s,insert(s);
int a=dfs1(0),b=dfs2(0);
if(a==0) printf("Second\n");
else if(a==1&&b==1) printf("First\n");
else printf("%s\n",(k&1)?"First":"Second");
return 0;
}