codeforcesRound#260(div2)D解题报告

解法：

首先存这些字符，用trie来存，通过trie就很容易联想到树型DP，这里的DP就不是取最优值之类的了，而是用来弄到达某个节点的胜负情况。

我们首先设节点v，win[v]代表已经组装好的字符刚好匹配到v了，然后需要进行下一步匹配时，先手是否可以赢，lose[v]则代表先手是否会输。

叶节点，win[v] = false, lose[v] = true.

其他节点 win[v] = win[v] | !win[child], lose[v] = lose[v] | !lose[child]. (因为每次赢的人，下一个就不是先手，所以结果肯定是跟下一个节点的赢成对立关系)。

如若win[0] = true , lose[0] = true则意味着第一局的人可以操控结果，否则按照k的次数来判断是否可以赢。

代码：

#include 
#include 
#define N_max 123456
#define sigma_size 26

using namespace std;

bool win[N_max], lose[N_max];
int n, k;
char st1[N_max];

class Trie{
public:
	int ch[N_max][sigma_size];
	int sz;

	Trie() {
	sz=0;
	memset(ch[0], 0, sizeof(ch[0]));
	}

	int idx(char c) {
	return c-'a';
	}

	void insert(char *s) {
	int l = strlen(s), u = 0;

	for (int i = 0; i < l; i++) {
	int c = idx(s[i]);

	if (!ch[u][c]) {
	ch[u][c] = ++sz;
	memset(ch[sz], 0, sizeof(ch[sz]));
	}

	u = ch[u][c];
	}
	}
};

Trie T;

void init() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
	scanf("%s", st1);
	T.insert(st1);
	}
}

void dfs(int v) {
	bool is_leaf = true;

	win[v] = false;
	lose[v] = false;

	for (int i = 0; i < sigma_size; i++) {
	int tmp = T.ch[v][i];

	if (tmp) {
	is_leaf = false;
	dfs(T.ch[v][i]);
	win[v] |= !win[T.ch[v][i]];
	lose[v] |= !lose[T.ch[v][i]];
	}
	}

	if (is_leaf) {
	win[v] = false;
	lose[v] = true;
	}
}

void ans(bool res) {
	puts(res? "First":"Second");
}

void solve() {
	dfs(0);

	if (win[0] && lose[0])
	ans(true);
	else if (win[0])
	ans(k&1);
	else
	ans(0);
}

int main() {
	init();
	solve();
}