2020年的多校赛结束了，不知是否还有来年？
# 题面
> HDU 6886
点击展开/折叠 题面翻译
在 $3\times3$ 的棋盘中，每个格子上有一堆石子，第 $i$ 行第 $j$ 列的位置的石子有 $a_{i,j}$ （$a_{i,j}>0$）颗。先后手轮流取石子。
两个人的第一次操作都必须将一堆石子全部取完；然后每次选择一堆取若干石子，不能不取。
当一个人操作后棋盘上有一行或一列上没有石子，则获胜。问先手有多少种第一步的取法能够必胜。
# 解析
先枚举先后手的第一步怎么走，若先手第一步取了之后，后手无论如何取都是先手必胜，则先手这样的第一步是必胜的。
首先后手第一步一定不会取先手第一步的同行同列的石子，否则该行/列只剩一堆石子，先手可以直接取空获胜。
则先后手走了第一步后的每个局面都等价于下面这样的局面，因为我们可以随意交换两行两列；把格子分成两类：
对于A类格子，一旦有个人把它取空，则会有一行或一列只剩一堆石子，所以对手就赢了。因此没有人会想把A类格子取空，我们可以认为A类格子的中石子的下限为 $1$。
对于B类格子，它就像一个普通格子一样。而且因为A类格子在最优策略下并不会取空，所以B类格子取空是没有关系的，不会让对手直接获胜。可以认为B类格子的下限是 $0$。
现在的问题就相当于，取AB类格子，第一个把A类格子取到 $0$（下限以下）的人输。于是 A 类格子相当于只有 $a_{i,j}-1$ 颗石子可取，B 类格子有 $a_{i,j}$ 颗石子可取。这 $7$ 堆可取的石子，把它们取空的人获胜，因为下一个人就必须取 A 类格子中剩下的 $1$ 颗石子然后输掉。
于是只需要求 A 类格子中的 $6$ 堆大小为 $a_{i,j}-1$ 的石子以及 B 类格子中的一堆大小为 $a_{i,j}$ 的石子的 NIM 游戏即可。
# 源代码
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int Read(){
register int r=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
return r;
}
int cas;
int maz[5][5];
bool Check(int x1,int y1,int x2,int y2){
bool del[5][5]={},delx[5]={},dely[5]={};
delx[x1]=delx[x2]=true,dely[y2]=dely[y1]=true;
int x3,y3;
for(int i=1;i<=3;i++){
if(!delx[i]) x3=i;
if(!dely[i]) y3=i;
}
int tmp=0;
del[x1][y1]=del[x2][y2]=del[x3][y3]=true;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
if(!del[i][j])
tmp^=maz[i][j]-1;
bool win=(tmp^maz[x3][y3]);
return win;
}
int main(){
cas=Read();
while(cas--){
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
maz[i][j]=Read();
int ans=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++){
bool win=true;
for(int p=1;p<=3 && win;p++)
for(int q=1;q<=3 && win;q++)
if(i!=p && j!=q && !Check(i,j,p,q))
win=false;
if(win) ans++;
}
printf("%d\n",ans);
}
return 0;
}
|
THE END
Thanks for reading!
> Linked OI Diary-Madia Lemon-Bilibili