首页 > 代码库 > CodeForces 456D&455B--A Lot of Games（Trie+博弈）
CodeForces 456D&455B--A Lot of Games（Trie+博弈）
题意：给n个字符串。进行k次游戏。每局开始，字符串为空串，然后两人轮流在末尾追加字符，保证新的字符串为集合中某字符串的前缀，不能操作者输，新一轮由上一句输的人先手。
题解：
#看到此题毫无头绪，队友写了神(xiang)一样的sg函数，我在旁边默默说，不太对吧，应该求必输必赢什么的，然后……然后怎样？我也不知道了……
#应该好好想想的，不应该轻易放弃啊……
对于每个节点分成四种情况，必输，必赢，可输可赢，不可控制情况（即后手可输可赢）
当一个结点的子节点有一个必输的时候，该节点可以胜，当有一个子结点必赢，该节点可以败，当所有子节点都可输可赢，该节点不可控制。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int KIND = 26;const int MAXN = 100005;int cnt_node;struct node{ int cnt; node* nt[KIND]; void init(){ cnt = 0; memset(nt, 0, sizeof(nt)); }} Heap[MAXN];inline node* new_node(){ Heap[cnt_node].init(); return &Heap[cnt_node++];}void insert(node* root, char *str){ for(char *p = str; *p; ++p){ int ch = *p - ‘a‘; if(root->nt[ch] == NULL) root->nt[ch] = new_node(); root = root->nt[ch]; ++root->cnt; }}void solve(node* root, int &x, int &y) { bool fg = true; x = y = 0; int u, v; for (int i = 0; i < 26; ++i) { if (root->nt[i]) { fg = false; solve(root->nt[i], u, v); if (!u) x = 1; if (!v) y = 1; } } if (fg) x = 0, y = 1;}char word[MAXN];int main(){ int n, k; while(scanf("%d%d", &n, &k) != EOF) { cnt_node = 0; node *root = new_node(); for(int i = 0; i < n; i++) { scanf("%s", word); insert(root, word); } int x, y; solve(root, x, y); if (x && y) puts("First"); else if (k&1 && x) puts("First"); else puts("Second"); }}
CodeForces 456D&455B--A Lot of Games（Trie+博弈）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。