首页 > 代码库 > codeforces 455B A Lot of Games (Trie + dfs)
codeforces 455B A Lot of Games (Trie + dfs)
题目大意:
两个人往一个空的字符串里填单词,每一次只能填一个,而且填完之后要是给出的N个字符串的前缀。
思路分析:
先用给出的所有单词建字典树。
然后从根节点开始dfs。
win [x] 表示踩在x节点上是否有必胜策略
lose [x] 表示踩在x节点上是否有必败策略。
然后是博弈的过程。
如果先手有必胜和必败的策略,那么他可以一直输到k-1
如果只有必胜策略。那么只有当k为奇数的时候它才能赢。
其他为后手赢。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define maxn 200005 using namespace std; struct node { node * next[26]; }; node trie[maxn],*root; int win[maxn],lose[maxn],tot=0; node *New() { node *t = &trie[tot++]; memset(t->next,NULL,sizeof(t->next)); return t; } void Insert(char *str,int len) { node *p=root; for(int i=0;i<len;i++) { int to=str[i]-'a'; if(p->next[to]==NULL)p->next[to]=New(); p=p->next[to]; } } void dfs(node *r) { int u=r-trie,cnt=0; win[u]=lose[u]=0; for(int i=0;i<26;i++) { if(r->next[i]!=NULL) { dfs(r->next[i]); cnt++; int v=r->next[i]-trie; if(!win[v])win[u]=1; if(!lose[v])lose[u]=1; } } if(!cnt)lose[u]=1; } char str[maxn]; int main() { int n,k; scanf("%d%d",&n,&k); root=New(); for(int i=0;i<n;i++) { scanf("%s",str); Insert(str,(int)strlen(str)); } dfs(root); if(win[0] && lose[0])puts("First"); else if(win[0] && (k&1))puts("First"); else puts("Second"); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。