原题地址
题目描述
给定n个小写字母组成的字符串，有两个人用这些字符串玩游戏。游戏内容是轮流在一个空串末尾添加一个小写字母，使得它是n个字符串中某一个的前缀，直到一个人无法继续操作，TA就成为输家，下一轮游戏中输家先开始。
定义一次游戏为产生一次输家，问k次游戏后的胜者是先手还是后手？
样例
输入
|
1 2 3 |
2 3 a b |
输出
|
1 |
First |
思路
先把这些串直接加进空串，然后建字典树，在树上DP，从叶子回溯到根。
二进制状态有4种，00和11代表结果和k相关，10代表先手赢，01代表后手赢。
叶子对父亲的贡献异或10之后和父亲的状态或一下就好了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <bits/stdc++.h> #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<len;i++){ int temp=x[i]-'a'; if (!q[now][temp]) q[now][temp]=++top; now=q[now][temp]; } } int dfs(int now){ int flag=1,ans; for (int i=0;i<26;i++){ if (q[now][i]){ flag=0; ans|=dfs(q[now][i])^3; } } if (flag) ans=1; return ans; } int main(){ ios::sync_with_stdio(false); cin>>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"<<endl; else cout<<"Second"<<endl; } |