CF36D New Game with a Chess Piece 题解

发布时间 2023-08-24 15:15:41作者: mcDinic

前言:

都大半年没在洛谷上提交过题解了。

SPOJ 上有双倍经验,题号为 SP7602。

我看题解区的大佬们有的正经用博弈论做,有的打表,但是感觉没有讲得很形象,这篇题解将生动讲述打表做法,同时为了让大家在感性理解后,还可以理性理解,会附上证明(这部分参考了别的题解)。

正文:

Step 1:打表找规律

\(b_{i,j}\) 表示从第 \(i\) 行第 \(j\) 列出发,是胜还是败。如果胜,\(b_{i,j}=1\),否则 \(b_{i,j}=0\)

我们先不考虑越界的问题,如果 \(b_{i+1,j},b_{i,j+1},b_{i+k,j+k}\) 中至少有一个为零(具体意义就是,从第 \(i\) 行第 \(j\) 列出发可以走到一个对手会败的位置),那么 \(b_{i,j}=1\),否则 \(b_{i,j}=0\)

也就是说,\(b_{i,j}=\lnot(b_{i+1,j} \bigwedge b_{i,j+1} \bigwedge b_{i+k,j+k})\)

状态转移时,如果越界的话,那么那个越界的值就不参与运算,所以为了方便起见,可以设它为 1.

附上打表程序

为了直观,我先搞一张表来给大家解释:

0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0