大家好，又见面了，我是全栈君。
题目连接: Codeforces 455B A Lot of Games
题目大意：给定n。表示字符串集合。
给定k，表示进行了k次游戏，然后是n个字符串。每局開始。字符串为空串，然后两人轮流在末尾追加字符。保证新的字符串为集合中某字符串的前缀。不能操作者输，新一轮由上一句输的人先手。
解题思路：首先对字符集合建立字典树。然后依据博弈的必胜必败性质搜索出先手的决策状态，可决定胜败3，仅仅能胜利2，仅仅能失败1。不可掌控（即对手可决定胜败）0。
对于状态3，为必胜。能够採用前K-1场败，然后保证第K场自己先手，取必胜方案。
对于状态2，不管则们走都是赢的话，肯定是两个人轮流胜局，所以推断K的奇偶性。
对于状态1和0，必败。由于一直输，一直先手。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
struct node {
int val, arr[30];
node () {
val = 0;
memset(arr, 0, sizeof(arr));
}
}t[maxn*2];
int top = 1, len, n, k;
char str[maxn];
inline int get_node () {
return top++;
}
void insert (int x, int d) {
if (d == len)
return;
int mv = str[d] - 'a';
if (t[x].arr[mv] == 0)
t[x].arr[mv] = get_node();
insert(t[x].arr[mv], d+1);
}
int solve (int x) {
int& ans = t[x].val;
ans = 0;
bool flag = true;
for (int i = 0; i < 26; i++) {
if (t[x].arr[i]) {
flag = false;
ans |= solve(t[x].arr[i]);
}
}
if (flag)
ans = 1;
return 3-ans;
}
int main () {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%s", str);
len = strlen(str);
insert(0, 0);
}
solve(0);
int ans = t[0].val;
if (ans < 2)
printf("Second\n");
else if (ans == 2)
printf("%s\n", k&1 ? "First" : "Second");
else
printf("First\n");
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116051.html原文链接：https://javaforall.net
