题目连接: 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;
}
分享到:
相关推荐
Codeforces 185A - Plant 全测试点49个
[codeforces 1304A] Two Rabbits 整除+模 总目录详见https://blog.csdn.net/mrcrack/article/details/103564004 在线测评地址https://codeforces.ml/contest/1304/problem/A Problem Lang Verdict Time Memory ...
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
接受串子-接受字符串相等-接受Codeforces回合#684(Div.2) 2/6 1440A-购买琴弦-接受1440B -中位数的总和-已接受1440C1-二进制表(简易版)-已接受1440C2-二进制表(硬版)-已接受 Codeforces回合#683(分区2) 1/...
解决问题(문제해결) ACM-ICPC凭证,BOJ,CodeForces,Codewars,SCPC,摇动,TopCoder凭证
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Some of the Codeforces problems codes
题目分析:如果暴力的话显然时间复杂度是 n * n 的,我们应该想办法去优化,比赛的时候想用线段树,但是不会在维护异或的前提下区间加法,也想过用矩阵维护,但丝毫没什么用呀,队友想到了可以按位维护,也就是维护...
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
codeforces每日一练。 题意: 给一棵树,每个点有一个点权,每条边有一个边权,求一条链使得点权和-边权和最大。 思路: 由于我没看清楚题意,以为是求联通子图的点权和-边权和最大,用link-cut-tree写换根,wa10了两...
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces扩展包 是否曾经想让Codeforce拥有方便的快捷键,自动更新排行榜,可以按需隐藏/显示的问题标签,更好的站点导航,深色主题或以上所有功能? 这些和更多功能可以在Codeforces ++中获得! 该扩展是开源的,...
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...