题意:两个人进行k场比赛，开始有一个空串,每场比赛两个人轮流加字符使得字符串至少是原来n个串的1个串的前缀，每场比赛输的人下一次比赛先手
题解:可以发现是前缀，可以想到用字典树判断其中一场的胜负。。。但是这里有坑，假如先手可胜可负k为偶数，那么他可以在倒数第二场故意输给你，这样最后一场就是先手决定
这里我们考虑先手输的话无论多少场都是输， 先手必胜的话就要看奇偶，先手可胜可负先手可以故意输使得他获胜，那么我们对每一个节点可以有4种状态（必胜，必败，可胜可败，未知）
所有子节点必胜那么父节点必败，所有子节点必败那么父节点必胜，子节点有胜有负那么就是父节点就是有胜有负
#include <bits/stdc++.h> #define maxn 101000 #define INF 0x3f3f3f3f typedef long long ll; using namespace std; struct Tire{ int ch[maxn][30],sz; Tire(){sz = 1;memset(ch, 0, sizeof(ch));} int idx(char c){return c-'a';} void insert(char *s){ int u = 0,n = strlen(s); for(int i=0;i<n;i++){ int c = idx(s[i]); if(!ch[u][c]){ memset(ch[sz], 0, sizeof(ch[sz])); ch[u][c] = sz++; } u = ch[u][c]; } } void dfs(int x,int &a,int &b){ int flag = 1, c, d; a = b = 0;//默认未知 for(int i=0;i<26;i++){ int u = ch[x][i]; if(u){ flag = 0; dfs(u, c, d); if(c == 0) a = 1; if(d == 0) b = 1; //必胜与可胜可败 } } if(flag) a = 0, b = 1;//叶子节点必败 } }Tir; char s[maxn]; int main(){ int n, k, a=0, b=0; scanf("%d%d", &n, &k); for(int i=0;i<n;i++){ scanf("%s", s); Tir.insert(s); } Tir.dfs(0, a, b); if(a&&b) printf("First "); else if(k&1&&a) printf("First "); else printf("Second "); return 0; }