欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #260 (Div. 2) D. A Lot of Games(树上博弈)

程序员文章站 2022-06-26 10:12:57
...

题目链接
Codeforces Round #260 (Div. 2) D. A Lot of Games(树上博弈)
Codeforces Round #260 (Div. 2) D. A Lot of Games(树上博弈)
思路:此题的关键是判断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;
}