【CodeForces 456D】A Lot of Games / 题解

【CodeForces 456D】A Lot of Games / 题解

原题地址

题目描述

给定n个小写字母组成的字符串,有两个人用这些字符串玩游戏。游戏内容是轮流在一个空串末尾添加一个小写字母,使得它是n个字符串中某一个的前缀,直到一个人无法继续操作,TA就成为输家,下一轮游戏中输家先开始。

定义一次游戏为产生一次输家,问k次游戏后的胜者是先手还是后手?

样例

输入
2 3
a
b
输出
First

思路

先把这些串直接加进空串,然后建字典树,在树上DP,从叶子回溯到根。

二进制状态有4种,00和11代表结果和k相关,10代表先手赢,01代表后手赢。

叶子对父亲的贡献异或10之后和父亲的状态或一下就好了。

代码

#include 
#define maxn 100050
using namespace std;
int n,k,root,top,q[maxn][26];
char x[maxn];
void insert(){
    int len=strlen(x);
    int now=root;
    for (int i=0;i>n>>k;
    for (int i=1;i<=n;i++)
        cin>>x,insert();
    int ans=dfs(root);
    if (ans==3||ans==2&&k&1) cout<<"First"<
Show Comments