51nod 1490 多重游戏(树上博弈)

1.0 秒 131,072.0 KB 40 分 4级题
有一个两人游戏,游戏是这样的,有n个非空串。在游戏的过程是,两个玩家轮流向一个字符串后面加字母,刚开始字符串是空的。每一次操作是向当前字符串后面添加字符,形成的新字符串一定要是这n个串中某一个或几个的前缀,如果无法做到,就输了。

这样的游戏似乎过于简单了,现在对这个游戏进行一下改进,让玩家玩K次这样的游戏,第i次的败者,将会作为第i+1次的先手进行这个游戏。第k次游戏的赢家就是整个游戏的赢家。

现在给定n个字符串和k,问是先手胜还是后手胜。


不会写,看了别人的代码,厉害厉害

首先建个trie树

局面可以分为四种情况:先手必胜10/先手必败01/可胜可败11/不能控制00

一开始所有叶节点都是必败,因为没有机会再加字符当前缀了。如果一个节点的所有儿子都是必败01,那么这个节点就是必胜10;如果一个节点所有儿子就是必胜10,那么这个节点就是必败01;如果一个节点的儿子有必胜有必败(可胜可败不影响),那么这个节点是可胜可败11;如果一个节点的儿子都是可胜可败,那么这个节点是不能控制00

树dp,这样状态转移方程就是dp[x]|=dp[ch[x][i]]^3,或上所有儿子取反的结果

如果先手必胜,那么看k的奇偶性;如果先手必败,那下一轮败者还是先手所以First就只能一直败;如果先手可胜可败,那机智的First可以控制局面让最后自己胜;如果先手不能控制,那没办法了最后Second赢

代码:

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<vector>
using namespace std;

const int N=100005;
string s[N];
int n,k,ch[N][30],ji=1,dp[N];
void insert(string ss){
int len=ss.length(),u=0;
for(int i=0;i<len;i++){
int c=(int)(ss[i]-'a');
if(!ch[u][c]){
ch[u][c]=ji++;
}
u=ch[u][c];
}
}
void dfs(int x){
int flag=0;
for(int i=0;i<26;i++){
if(ch[x][i]){
flag=1;
dfs(ch[x][i]);
dp[x]|=dp[ch[x][i]]^3;
}
}
if(!flag)dp[x]=1;//叶节点必败
}
int main(){
scanf("%d%d",&n,&k);
memset(ch,0,sizeof(ch));
for(int i=0;i<n;i++){
cin>>s[i];
insert(s[i]);
}
dfs(0);
if(dp[0]==2){
if(k&1)puts("First");
else puts("Second");
}
else if(dp[0]==1){
puts("Second");
}
else if(dp[0]==3){
puts("First");
}
else{
puts("Second");
}
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信