CodeForces - 456D A Lot of Games(字典树+博弈)

98 阅读 0 评论 65 点赞

我是靠谱客的博主善良玫瑰，这篇文章主要介绍CodeForces - 456D A Lot of Games(字典树+博弈)，现在分享给大家，希望可以做个参考。

题目链接：点击查看

题目大意：给出n个字符串，现在有两个人玩一个游戏，游戏规则是两人轮流构造同一个字符串，每次可以向末尾添加一个字母，必须保证添加字母后的字符串是n个字符串其中之一的前缀，不能操作者算输，两个人需要进行k次游戏，第一次游戏由先手开始，之后输掉本局游戏的人为下一局游戏的先手，现在问谁能赢得最后一局的游戏

题目分析：考虑到需要对数量较大的前缀进行操作，我们可以使用字典树来维护，这样整个题目就变成了字典树上的博弈，我们可以从叶子结点的状态不断向上转移，最后转移到字典树的根节点，又因为字典树的根节点是一个不存在的结点，所以我们对每个节点定义为：接下来一步的状态，因为最后无法操作的人会输掉比赛，所以叶子结点就是必败态，要分清楚我们现在有四个状态：

必胜态
必败态
可胜可败态
不可胜也不可败态

显然状态一二互斥，状态三四互斥，这样一来将状态转移到根节点然后分类讨论就是答案了：

先手必胜：则进行轮次为奇数时，先手获胜，否则后手获胜
先手必败：则先手必败后下一局还是先手开始，会一直必败，显然后手获胜
可胜可败：先手会故意让自己一直输，一直先手，最后一局的时候胜利，所以先手获胜
不可胜也不可败：因为先手无论如何操作，下一次的操作权就交给后手了，此时后手就是可胜可败态，同上面的第三条，所以后手获胜

代码：

复制代码

#include<iostream>
#include<cstdio> 
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
#include<unordered_map>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e5+100;

char s[N];

int trie[N][26],cnt,val[N];

void insert()
{
	int pos=0;
	for(int i=0;s[i];i++)
	{
		int to=s[i]-'a';
		if(!trie[pos][to])
			trie[pos][to]=++cnt;
		pos=trie[pos][to];
	}
}

void dfs(int pos)//val 1:必败 2:必胜 3:可胜可败 4:不能确定 
{
	bool win=false;//必胜
	bool lose=false;//必败 
	bool flag=true;//是否为子节点 
	for(int i=0;i<26;i++)
		if(trie[pos][i])
		{
			dfs(trie[pos][i]);
			if(val[trie[pos][i]]==1||val[trie[pos][i]]==4)
				win=true;
			if(val[trie[pos][i]]==2||val[trie[pos][i]]==4)
				lose=true; 
			flag=false;
		}
	if(flag)
		val[pos]=1;
	else
	{
		if(win&&lose)
			val[pos]=3;
		else if(win)
			val[pos]=2;
		else if(lose)
		 	val[pos]=1;
		else
			val[pos]=4;
	}
}
 
int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int n,m;
	scanf("%d%d",&n,&m);
	while(n--)
	{
		scanf("%s",s);
		insert();
	}
	dfs(0);
	if(val[0]==1)
	{
		puts("Second");
	}
	else if(val[0]==2)
	{
		if(m&1)
			puts("First");
		else
			puts("Second");
	}
	else if(val[0]==3)
	{
		puts("First");
	}
	else
	{
		puts("Second");
	}
 
 
 
 
 
 
 
 
	
	
	
	
	
	
	
	
	
	return 0;
}

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<cstdio> 
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
#include<unordered_map>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e5+100;

char s[N];

int trie[N][26],cnt,val[N];

void insert()
{
	int pos=0;
	for(int i=0;s[i];i++)
	{
		int to=s[i]-'a';
		if(!trie[pos][to])
			trie[pos][to]=++cnt;
		pos=trie[pos][to];
	}
}

void dfs(int pos)//val 1:必败 2:必胜 3:可胜可败 4:不能确定 
{
	bool win=false;//必胜
	bool lose=false;//必败 
	bool flag=true;//是否为子节点 
	for(int i=0;i<26;i++)
		if(trie[pos][i])
		{
			dfs(trie[pos][i]);
			if(val[trie[pos][i]]==1||val[trie[pos][i]]==4)
				win=true;
			if(val[trie[pos][i]]==2||val[trie[pos][i]]==4)
				lose=true; 
			flag=false;
		}
	if(flag)
		val[pos]=1;
	else
	{
		if(win&&lose)
			val[pos]=3;
		else if(win)
			val[pos]=2;
		else if(lose)
		 	val[pos]=1;
		else
			val[pos]=4;
	}
}
 
int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int n,m;
	scanf("%d%d",&n,&m);
	while(n--)
	{
		scanf("%s",s);
		insert();
	}
	dfs(0);
	if(val[0]==1)
	{
		puts("Second");
	}
	else if(val[0]==2)
	{
		if(m&1)
			puts("First");
		else
			puts("Second");
	}
	else if(val[0]==3)
	{
		puts("First");
	}
	else
	{
		puts("Second");
	}
 
 
 
 
 
 
 
 
	
	
	
	
	
	
	
	
	
	return 0;
}