【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"<