「Codeforces Round 460 div2」F. A Game With Numbers - 博弈论+NP点+拓扑排序 | Bill Yang's Blog

「Codeforces Round 460 div2」F. A Game With Numbers - 博弈论+NP点+拓扑排序

题目大意

    Alice与Bob在玩一个游戏,两人各有$8$张牌,每个牌的点数在$0\sim4$之间,两人的牌双方均可见。
    双方轮流进行如下步骤:

  1. 选出自己的一张点数为$a$牌与对方的一张牌$b$,其中$a\cdot b\neq0$。
  2. 使用点数$c=(a+b)\bmod5$替换自己的点数为$a$的牌。

    当有一方的$8$张牌全为$0$,则该玩家胜利。
    给出$T(1\le T\le10^5)$种初始状态,并指出先手玩家,询问他们是否有必胜策略。
    若Alice必胜则输出Alice,Bob必胜则输出Bob,若平局输出Deal


题目分析

这是一个博弈论的问题,尝试将牌面记作状态。
注意状态数并不是$(5^8)^2$种,因为牌的先后顺序并不影响状态。
对于每个玩家,有用的卡牌状态仅有$\binom{5+8-1}{8}$种。
原因是,我们将每种点数的卡牌数目记作$x_i$,可列出方程:

其非负整数解个数即为$\binom{5+8-1}{8}$,可以在组合数学处找到证明。

因此总状态数只有$\binom{5+8-1}{8}^2=245\,025$种。

不妨将状态用结点表示出来,将状态的转移用边表示出来。
这样我们可以得到一个有向图。

对于每个状态,我们可以进行选择:

  • 若后继状态中包含至少一个败态,该状态为胜态。
  • 若后继状态中不存在败态,但包含至少一个平局状态,则该状态为平局状态。
  • 若后继状态中全是胜态,则该状态为败态。

这是一个NP点的问题,可以递推解决。
但是状态的转移可能有环。
有环即存在平局的状态,关于这里的处理还有点小问题。
标解采用了拓扑排序的方法,若一个结点没有被标记任何状态,则其为平局状态。
个人觉得这里有点问题,我在官方题解blog里提出了这个问题,等待得到答复中。

因此可以在$O(k^2\binom{5+8-1}{8}^2)$的时间内完成预处理,然后可以$O(1)$询问了。
时间复杂度$O(k^2\binom{5+8-1}{8}^2+T)$。


代码

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
119
120
121
122
123
124
125
126
127
128
129
130
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int BASE=9,maxs=505;
int Hash(const vector<int> &a) {
int ans=0;
for(int i=4; i>=0; i--)ans=ans*BASE+a[i];
return ans;
}
vector<int> now;
vector<pii> fedges[maxs][maxs];
vector<vector<int> > S;
int Pow[5],step=0,M[60005],ans[maxs][maxs],InDegree[maxs][maxs];
void Dfs(int n,int k) {
if(k==1) {
now.push_back(n);
M[Hash(now)]=step++;
S.push_back(now);
now.pop_back();
return;
}
for(int j=0; j<=n; j++) {
now.push_back(j);
Dfs(n-j,k-1);
now.pop_back();
}
}
queue<pii>Q;
void Top_Sort() {
while(!Q.empty()) {
int s1=Q.front().first,s2=Q.front().second;
Q.pop();
for(auto Next:fedges[s1][s2]) {
if(ans[Next.first][Next.second])continue;
if(ans[s1][s2]==2) {
ans[Next.first][Next.second]=1;
Q.push(Next);
continue;
}
InDegree[Next.first][Next.second]--;
if(InDegree[Next.first][Next.second]==0) {
ans[Next.first][Next.second]=2;
Q.push(Next);
continue;
}
}
}
}
int main() {
Pow[0]=1;
for(int i=1; i<5; i++)Pow[i]=Pow[i-1]*BASE;
Dfs(8,5);
for(int id1=0; id1<S.size(); id1++) {
auto s1=S[id1];
int sum=Hash(s1);
bool flag1=1;
for(int id2=0; id2<S.size(); id2++) {
auto s2=S[id2];
bool flag2=1;
for(int i=1; i<5; i++)
if(s1[i]) {
flag1=0;
for(int j=1; j<5; j++)
if(s2[j]) {
flag2=0;
int tmp=sum-Pow[i]+Pow[(i+j)%5];
fedges[id2][M[tmp]].push_back(mp(id1,id2));
InDegree[id1][id2]++;
}
}
if(flag1) {
ans[id1][id2]=1; //win
Q.push(mp(id1,id2));
} else if(flag2) {
ans[id1][id2]=2; //lose
Q.push(mp(id1,id2));
}
}
}
Top_Sort();
int t=Get_Int();
while(t--) {
int f=Get_Int(),sum1=0,sum2=0;
for(int i=1; i<=8; i++)sum1+=Pow[Get_Int()];
for(int i=1; i<=8; i++)sum2+=Pow[Get_Int()];
int s1=M[sum1],s2=M[sum2];
if(f==0) {
if(ans[s1][s2]==1)puts("Alice");
else if(ans[s1][s2]==2)puts("Bob");
else puts("Deal");
} else {
if(ans[s2][s1]==1)puts("Bob");
else if(ans[s2][s1]==2)puts("Alice");
else puts("Deal");
}
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%