[Xmas Contest 2024] Game Pack 题解 | 【模板】十二重对称博弈法
MatrixGroup · · 算法·理论
题目链接
本题解中，「必胜」是「存在必胜策略」的缩写。
题面
题目背景
黑兔「今年也来玩游戏吧！」
白兔「好啊！」
黑兔「我带了
白兔「里面有些无聊的游戏吧」
黑兔「欢迎只玩自己喜欢的游戏！」
题目描述
黑兔和白兔在玩某游戏。这个游戏的状态用「有一些盘子，每个盘子上有一些糖果」表示。
这个游戏的规则将会由给定的
给定
操作
对于一个有
- 若
A=0 ，取出不少于一个糖果吃掉。 - 若
A=1 ，取出1\sim 3 个糖果吃掉。 - 若
A=2 ，取出1\sim \left\lfloor\dfrac x2\right\rfloor 个糖果吃掉。 - 若
A=3 ，- 若
x 为17 的倍数，取出恰好一个糖果吃掉。 - 若
x 不为17 的倍数，取出1\sim 2 个糖果吃掉。
- 若
- 若
A=4 ，取出1\sim x-1 个糖果，新拿一个空盘子，放到这个盘子里。
行动
行动定义如下。
- 若
B=0 ，选择恰好一个盘子操作。（不能选无法操作的盘子操作。） - 若
B=1 ，选择至少一个盘子操作。（不能选无法操作的盘子操作。） - 若
B=2 ，选择所有可以操作的盘子操作。
终局
终局定义如下。
- 若
C=0 ，当且仅当所有盘子都无法操作，游戏结束。 - 若
C=1 ，当且仅当存在盘子无法操作，游戏结束。
胜负
根据游戏结束时下一个轮到谁行动，胜负判定如下。
- 若
D=0 ，下一个要行动的一方输，即做出最后一个行动的人赢。 - 若
D=1 ，下一个要行动的一方赢，即做出最后一个行动的人输。
数据范围
保证
题解
十二重博弈法
其实
为了方便描述，我们给每个组合都取个名词。我们称
对于
接下来我们将按照 Conway 书中的顺序，逐一分析如何判定这些规则下游戏的和的胜负。
值得一提的是，以下分析中，不仅求出了游戏的和的胜负，也分析出了游戏的和的对应值，因此一个状态可以分裂成多个状态时（例如，
正常可选和
先手有必胜策略当且仅当存在某个游戏先手有（正常）必胜策略。
这是因为先手的行动只要在先手有必胜策略的所有游戏中操作即可。
反常可选和
如果所有游戏都结束了，依定义先手胜。如果恰有一个游戏没有结束，直接看先手在此游戏中是否有（反常）必胜策略即可。否则，先手有必胜策略，当且仅当在正常可选和中，这组游戏有必胜策略。
前两句话是显然的。最后一句归纳，在边界情况只需要注意你可以对那个关键游戏选择操作或不操作就得到了证明。
正常快速可选和
如果某个游戏结束了，依定义后手胜。否则先手胜当且仅当至少有一个游戏（正常）先手胜。
前半句显然。否则还是在先手有必胜策略的所有游戏中操作即可。
反常快速可选和
先手胜当且仅当至少有一个游戏（反常）先手胜。
先手有必胜策略的所有游戏中操作即可。
正常合取和
显然，一个游戏结束了整体就结束了，所以合取和取决于最快的一个游戏。因此，胜者会想要让游戏尽可能短，而败者会想要让游戏尽可能长，企图在别的游戏中先取胜。因此我们定义正常持久度（remoteness）为这种情况下游戏进行的长度：
- 如果可以走到一个偶持久度的游戏，其持久度为其可以走到的最小的偶持久度
+1 。 - 否则，如果可以走到一个奇持久度的游戏，其持久度为其可以走到的最大奇持久度
+1 。 - 否则，这个游戏已经结束了，其持久度为
0 。
那么，不难得出：
一些游戏的正常合取和的持久度为所有游戏正常持久度中的最小值。先手必胜当且仅当正常持久度是奇数。
反常合取和
类似地，我们定义反常持久度：
- 如果可以走到一个奇持久度的游戏，其持久度为其可以走到的最小的奇持久度
+1 。 - 否则，如果可以走到一个偶持久度的游戏，其持久度为其可以走到的最大偶持久度
+1 。 - 否则，这个游戏已经结束了，其持久度为
0 。
那么，不难得出：
一些游戏的反常合取和的持久度为所有反常正常持久度中的最小值。先手必胜当且仅当反常持久度是偶数。
正常恒久合取和
此时，游戏的胜负反而取决于最慢的一个游戏。因此我们定义正常悬念值（suspense number）：
- 如果可以走到一个偶悬念值的游戏，其悬念值为其可以走到的最大的偶悬念值
+1 。 - 否则，如果可以走到一个奇悬念值的游戏，其悬念值为其可以走到的最小奇悬念值
+1 。 - 否则，这个游戏已经结束了，其悬念值为
0 。
那么，不难得出：
一些游戏的正常恒久合取和的悬念值为所有游戏正常悬念值中的最大值。先手必胜当且仅当正常悬念值是奇数。
反常恒久合取和
类似地，我们定义反常悬念值：
- 如果可以走到一个奇悬念值的游戏，其悬念值为其可以走到的最大的奇悬念值
+1 。 - 否则，如果可以走到一个偶悬念值的游戏，其悬念值为其可以走到的最小偶悬念值
+1 。 - 否则，这个游戏已经结束了，其悬念值为
0 。
那么，不难得出：
一些游戏的反常恒久合取和的悬念值为所有游戏反悬念值中的最大值。先手必胜当且仅当反常悬念值是偶数。
正常析取和
大家都知道，定义一个游戏的（正常）SG 值为
- 所有其可以走到的游戏的 SG 值的
\operatorname{mex} 。
特别地，
- 一个结束了的游戏的 SG 值为
0 。
那么，我们有：
一些游戏的正常析取和的 SG 值为其所有游戏的正常 SG 值的异或和。先手必胜当且仅当游戏的正常 SG 值不为
反常析取和
类似地，我们定义一个游戏的反常 SG 值为：
- 所有其可以走到的游戏的 SG 值的
\operatorname{mex} 。
但是，
- 一个结束了的游戏的 SG 值为
1 。
那么直接判断反常 SG 值是否为
不过，可喜的是，对于 Nim 堆而言，这是较为容易的。具体的，我们称一个游戏是平淡（tame）的，当且仅当要么它的正常 SG 值和反常 SG 值相等，要么这二者一个为
一些平淡游戏的析取和也是平淡游戏。其反常 SG 值等于正常 SG 值当且仅当存在一个这样的子游戏。先手（反常）必胜当且仅当其反常 SG 值不为
正常消失析取和
考虑如果有一个游戏走一步就结束了，那就先手直接赢了。因此要避免走到这样的局面。考虑定义（正常）提前终止 SG 值为把所有结束了的和走一步可以结束的局面标记为不合法的后的正常 SG 值。那么显然有：
如果任意一个子游戏结束了，该游戏后手必胜。否则若任何一个子游戏可以走一步结束，该游戏先手必胜。否则，一些游戏的正常消失析取和的提前终止 SG 值为所有子游戏的提前终止 SG 值的异或和，先手必胜当且仅当提前终止 SG 值不为
（例题：P10501 Cutting Game）
反常消失析取和
类似地，定义反常提前终止 SG 值为把所有结束了的局面标记为不合法的后的正常 SG 值。那么显然有：
如果任意一个子游戏结束了，该游戏先手必胜。否则，一些游戏的反常消失析取和的提前终止 SG 值为所有子游戏的反常提前终止 SG 值的异或和，先手必胜当且仅当反常提前终止 SG 值不为
快速求解
首先，可以归纳地证明
对于
否则，逐一考虑每种情况：（只考虑单堆，多堆按照上述方法加即可）
- 正常可选和：偶数必胜，奇数必败。
- 反常可选和：
1,3,5 和\ge 6 的偶数必胜，否则必败。（6 必胜了是因为可以拆成3+3 ，因为有多堆没结束的因此等于正常可选和。而2,4 必然拆出1 ，不能归为正常可选和。） - 正常快速可选和：
1 结束了，必败。如果不是1 显然可以直接一步走到1 ，必胜。 - 反常快速可选和：模
5 余0,1,4 必胜，余2,3 必败。 - 正常合取和：
1 是结束状态，持久度为0 ，否则先手直接分出一个1 ，持久度为1 。（换言之，有1 先手直接输，否则必胜） - 反常合取和：
1 的持久度为0 ，2,3 是必输的持久度为1 ，否则先手直接分出一个2 ，持久度为2 。（换言之，有1 先手直接胜，否则若没有2,3 则必胜） - 正常恒久合取和：悬念值为
2k 的数是2^{k+1}-1 ，为2k+1 的区间是[2^{k+1},2^{k+2}-2] 。 - 反常恒久合取和：悬念值为
2k+1 的数是3\times 2^k-1 ，为2k+2 的区间是[3\times 2^k,3\times 2^{k+1}-2] ，为0 的数是1 。 - 正常析取和/反常析取和：偶数/奇数的正常 Nim 值是
1/0 ，反常 Nim 值是0/1 。其实要走的步数是固定的（\sum (X_i-1) ），直接判断即可。 - 正常消失析取和：
1 是终止局面，其它都是走一步能终止的局面。 - 反常消失析取和。换言之只能拆成
\ge 2 的堆，平移一下就是拿走一个拆成两个非空堆。诶这不是我们的 SG 函数有34 的循环节吗？
以上结论不难打表猜出归纳证明。直接计算即可。
代码
写的有点丑，见谅。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define rep1(i,n) for(int i=1,parano##i##a=int(n);i<=parano##i##a;++i)
using namespace std;
int t;
int n,N,cur;
int l[500005],r[500005];
int ret[500005];
int ret2[500005];
set<int> S,T;int cnt[500005];
void solve_selective_normal()
{
for(int i=0;i<=N;++i)
{
if(l[i]>r[i])
{
S.clear();
ret[i]=0;
}
else
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0) S.insert(ret[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0) S.erase(ret[j]);
}
if(S.count(0)) ret[i]=1;
else ret[i]=0;
}
}
while(t--)
{
cin>>n;
int result=0;
rep1(i,n)
{
cin>>cur;
result|=ret[cur];
}
if(result) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_selective_misere()
{
for(int i=0;i<=N;++i)
{
if(l[i]>r[i])
{
S.clear();
ret[i]=0;
}
else
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0) S.insert(ret[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0) S.erase(ret[j]);
}
if(S.count(0)) ret[i]=1;
else ret[i]=0;
}
}
S.clear();memset(cnt,0,sizeof(cnt));
for(int i=0;i<=N;++i)
{
if(l[i]>r[i])
{
S.clear();
ret2[i]=1;
}
else
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret2[j]]++)==0) S.insert(ret2[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret2[j]])==0) S.erase(ret2[j]);
}
if(S.count(0)) ret2[i]=1;
else ret2[i]=0;
}
}
while(t--)
{
cin>>n;
int result=0,result2=0;
int qcnt=0;
rep1(i,n)
{
cin>>cur;
result|=ret[cur];
if(l[cur]<=r[cur])
{
result2+=ret2[cur];
++qcnt;
}
}
int answer=(qcnt>=2)?result:((qcnt==0)?1:result2);
if(answer) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_short_selective_normal()
{
for(int i=0;i<=N;++i)
{
if(l[i]>r[i])
{
S.clear();
ret[i]=0;
}
else
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0) S.insert(ret[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0) S.erase(ret[j]);
}
if(S.count(0)) ret[i]=1;
else ret[i]=0;
}
}
while(t--)
{
cin>>n;
int result=0;
bool end=false;
rep1(i,n)
{
cin>>cur;
result|=ret[cur];
if(l[cur]>r[cur]) end=true;
}
if(end) result=0;
if(result) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_short_selective_misere()
{
for(int i=0;i<=N;++i)
{
if(l[i]>r[i])
{
S.clear();
ret[i]=1;
}
else
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0) S.insert(ret[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0) S.erase(ret[j]);
}
if(S.count(0)) ret[i]=1;
else ret[i]=0;
}
}
while(t--)
{
cin>>n;
int result=0;
rep1(i,n)
{
cin>>cur;
result|=ret[cur];
}
if(result) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_conjunctive_normal()
{
ret[0]=0;
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0)
{
if(ret[j]&1)
T.insert(ret[j]);
else
S.insert(ret[j]);
}
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0)
{
if(ret[j]&1)
T.erase(ret[j]);
else
S.erase(ret[j]);
}
}
if(!S.empty()) ret[i]=(*S.begin())+1;
else if(!T.empty()) ret[i]=(*prev(T.end()))+1;
else ret[i]=0;
}
while(t--)
{
cin>>n;
int result=114514191;
rep1(i,n)
{
cin>>cur;
result=min(result,ret[cur]);
}
if(result&1) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_conjunctive_misere()
{
ret[0]=0;
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0)
{
if(ret[j]&1)
T.insert(ret[j]);
else
S.insert(ret[j]);
}
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0)
{
if(ret[j]&1)
T.erase(ret[j]);
else
S.erase(ret[j]);
}
}
if(!T.empty()) ret[i]=(*T.begin())+1;
else if(!S.empty()) ret[i]=(*prev(S.end()))+1;
else ret[i]=0;
}
while(t--)
{
cin>>n;
int result=114514191;
rep1(i,n)
{
cin>>cur;
result=min(result,ret[cur]);
}
if(!(result&1)) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_continue_conjunctive_normal()
{
ret[0]=0;
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0)
{
if(ret[j]&1)
T.insert(ret[j]);
else
S.insert(ret[j]);
}
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0)
{
if(ret[j]&1)
T.erase(ret[j]);
else
S.erase(ret[j]);
}
}
if(!S.empty()) ret[i]=(*prev(S.end()))+1;
else if(!T.empty()) ret[i]=(*T.begin())+1;
else ret[i]=0;
}
while(t--)
{
cin>>n;
int result=0;
rep1(i,n)
{
cin>>cur;
result=max(result,ret[cur]);
}
if(result&1) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_continue_conjunctive_misere()
{
ret[0]=0;
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0)
{
if(ret[j]&1)
T.insert(ret[j]);
else
S.insert(ret[j]);
}
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0)
{
if(ret[j]&1)
T.erase(ret[j]);
else
S.erase(ret[j]);
}
}
if(!T.empty()) ret[i]=(*prev(T.end()))+1;
else if(!S.empty()) ret[i]=(*S.begin())+1;
else ret[i]=0;
}
while(t--)
{
cin>>n;
int result=0;
rep1(i,n)
{
cin>>cur;
result=max(result,ret[cur]);
}
if(!(result&1)) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_disjunctive_normal()
{
for(int i=0;i<=N;++i) S.insert(i);
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0) S.erase(ret[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0) S.insert(ret[j]);
}
if(l[i]>r[i]) ret[i]=0;
else ret[i]=*S.begin();
}
while(t--)
{
cin>>n;
int result=0;
rep1(i,n)
{
cin>>cur;
result^=ret[cur];
}
if(result) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_disjunctive_misere()
{
for(int i=0;i<=N;++i) S.insert(i);
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0) S.erase(ret[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0) S.insert(ret[j]);
}
if(l[i]>r[i]) ret[i]=0;
else ret[i]=*S.begin();
}
for(int i=0;i<=N;++i) S.insert(i);
ret2[0]=1;memset(cnt,0,sizeof(cnt));
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret2[j]]++)==0) S.erase(ret2[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret2[j]])==0) S.insert(ret2[j]);
}
if(l[i]>r[i]) ret2[i]=1;
else ret2[i]=*S.begin();
}
while(t--)
{
cin>>n;
bool flip=true;
int result=0;
rep1(i,n)
{
cin>>cur;
result^=ret[cur];
flip&=(ret[cur]!=ret2[cur]);
}
if(flip) result^=1;
if(result) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_diminish_disjunctive_normal()
{
for(int i=0;i<=N;++i) S.insert(i);
S.insert(N+1);S.insert(N+2);
ret[0]=N+2;
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0) S.erase(ret[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0) S.insert(ret[j]);
}
if(l[i]>r[i]) ret[i]=N+2;
else if((*prev(S.end()))!=N+2) ret[i]=N+1;
else ret[i]=*S.begin();
}
while(t--)
{
cin>>n;
bool f1=false,f2=false;
int result=0;
rep1(i,n)
{
cin>>cur;
if(ret[cur]==N+2) f1=true;
else if(ret[cur]==N+1) f2=true;
else result^=ret[cur];
}
if(f1) result=N+2;
else if(f2) result=N+1;
if(result&&result!=N+2) cout<<"Black\n";
else cout<<"White\n";
}
}
void solve_diminish_disjunctive_misere()
{
for(int i=0;i<=N;++i) S.insert(i);
S.insert(N+1);
ret[0]=N+1;
for(int i=1;i<=N;++i)
{
for(int j=r[i-1]+1;j<=r[i];++j)
{
if((cnt[ret[j]]++)==0) S.erase(ret[j]);
}
for(int j=l[i-1];j<l[i];++j)
{
if((--cnt[ret[j]])==0) S.insert(ret[j]);
}
if(l[i]>r[i]) ret[i]=N+1;
else ret[i]=*S.begin();
}
while(t--)
{
cin>>n;
int result=0;
bool fl=false;
rep1(i,n)
{
cin>>cur;
if(ret[cur]==N+1) fl=true;
else result^=ret[cur];
}
if(fl) result=N+1;
if(result) cout<<"Black\n";
else cout<<"White\n";
}
}
int a,b,c,d;
void solvea4()
{
if(b==0)
{
if(c==0)
{
if(d==0)
{
while(t--)
{
cin>>n;
int er=0;
rep1(i,n)
{
cin>>cur;
er^=!(cur&1);
}
if(er) cout<<"Black\n";
else cout<<"White\n";
}
}
else
{
while(t--)
{
cin>>n;
int er=0;
rep1(i,n)
{
cin>>cur;
er^=!(cur&1);
}
if(!er) cout<<"Black\n";
else cout<<"White\n";
}
}
}
else
{
if(d==0)
{
while(t--)
{
cin>>n;
bool have1=false;
rep1(i,n)
{
cin>>cur;
if(cur==1) have1=true;
}
if(have1) cout<<"White\n";
else cout<<"Black\n";
}
}
else
{
ret[2]=ret[3]=0;
for(int i=4;i<=200;++i)
{
memset(cnt,0,sizeof(int)*(i+2));
for(int j=2;j<=i/2;++j)
cnt[ret[j]^ret[i-j]]=1;
while(cnt[ret[i]]) ++ret[i];
}
for(int i=201;i<=N;++i) ret[i]=ret[i-34];
while(t--)
{
cin>>n;
bool have1=false;
int res=0;
rep1(i,n)
{
cin>>cur;
if(cur==1) have1=true;
else res^=ret[cur];
}
if(have1||res) cout<<"Black\n";
else cout<<"White\n";
}
}
}
}
else if(b==2)
{
if(c==0)
{
if(d==0)
{
ret2[0]=-1;
for(int i=1;i<=N;++i) ret2[i]=ret2[i>>1]+1;
for(int i=1;i<=N;++i)
{
if(((i+1)&i)==0) ret[i]=ret2[i]*2;
else ret[i]=ret2[i]*2-1;
}
while(t--)
{
cin>>n;
int result=0;
rep1(i,n)
{
cin>>cur;
result=max(result,ret[cur]);
}
if(result&1) cout<<"Black\n";
else cout<<"White\n";
}
}
else
{
ret2[0]=-1;
for(int i=1;i<=N;++i) ret2[i]=ret2[i>>1]+1;
ret[1]=0;ret[2]=1;
for(int i=3;i<=N;++i)
{
ret[i]=2*(1+ret2[i/3]);
if((i%3==2)&&((i/3)&(i/3+1))==0) ++ret[i];
}
while(t--)
{
cin>>n;
int result=0;
rep1(i,n)
{
cin>>cur;
result=max(result,ret[cur]);
}
if(!(result&1)) cout<<"Black\n";
else cout<<"White\n";
}
}
}
else
{
if(d==0)
{
while(t--)
{
cin>>n;
bool have1=false;
rep1(i,n)
{
cin>>cur;
if(cur==1) have1=true;
}
if(!have1) cout<<"Black\n";
else cout<<"White\n";
}
}
else
{
while(t--)
{
cin>>n;
bool have1=false,have23=false;
rep1(i,n)
{
cin>>cur;
if(cur==1) have1=true;
else if(cur==2||cur==3) have23=true;
}
if(have1||!have23) cout<<"Black\n";
else cout<<"White\n";
}
}
}
}
else
{
if(c==0)
{
if(d==0)
{
while(t--)
{
cin>>n;
bool haveeven=false;
rep1(i,n)
{
cin>>cur;
if(cur%2==0) haveeven=true;
}
if(haveeven) cout<<"Black\n";
else cout<<"White\n";
}
}
else
{
while(t--)
{
cin>>n;
bool haveeven=false;
int rem=1;
int qcnt=0;
rep1(i,n)
{
cin>>cur;
if(cur%2==0) haveeven=true;
if(cur>=2)
{
++qcnt;
rem=cur;
}
}
if(qcnt<=1)
{
if((rem%2==0)!=(rem<=5)) cout<<"Black\n";
else cout<<"White\n";
}
else
{
if(haveeven) cout<<"Black\n";
else cout<<"White\n";
}
}
}
}
else
{
if(d==0)
{
while(t--)
{
cin>>n;
bool end=false;
rep1(i,n)
{
cin>>cur;
if(cur==1) end=true;
}
if(!end) cout<<"Black\n";
else cout<<"White\n";
}
}
else
{
while(t--)
{
cin>>n;
bool haven=false;
rep1(i,n)
{
cin>>cur;
if(cur%5==1||cur%5==4||cur%5==0) haven=true;
}
if(haven) cout<<"Black\n";
else cout<<"White\n";
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>a>>b>>c>>d>>t;
N=500000;
if(a==4)
{
solvea4();
return 0;
}
l[0]=0;r[0]=-1;
if(a==0)
{
rep1(i,N) l[i]=0,r[i]=i-1;
}
else if(a==1)
{
rep1(i,N) l[i]=max(i-3,0),r[i]=i-1;
}
else if(a==2)
{
rep1(i,N) l[i]=i-i/2,r[i]=i-1;
}
else
{
rep1(i,N) l[i]=max(0,i-1-bool(i%17)),r[i]=i-1;
}
if(b==0)
{
if(c==0)
{
if(d==0) solve_disjunctive_normal();
else solve_disjunctive_misere();
}
else
{
if(d==0) solve_diminish_disjunctive_normal();
else solve_diminish_disjunctive_misere();
}
}
else if(b==1)
{
if(c==0)
{
if(d==0) solve_selective_normal();
else solve_selective_misere();
}
else
{
if(d==0) solve_short_selective_normal();
else solve_short_selective_misere();
}
}
else
{
if(c==1)
{
if(d==0) solve_conjunctive_normal();
else solve_conjunctive_misere();
}
else
{
if(d==0) solve_continue_conjunctive_normal();
else solve_continue_conjunctive_misere();
}
}
return 0;
}参考文献
John Conway, On Numbers And Games, 1976.
注释
[^1]: 译注：Conway 的原文中，每两个词首字母相同（diminished disjunctive，shortened selective，continued conjunctive），可以方便记忆。翻译时采用了拼音首字母相同来反映这点。