娱乐 一种存在性证明的思路和三道类似的“算法挑战”

[l1ll5]

1和2的思路本质上是一样的：用一个“无影响”的操作交换先后手从而实现先手必胜。

对于1来说这个无影响的操作是取1，对于2来说这个无影响的操作是取右上角的1*1块。

这两个操作都满足它包含于任何其他有效操作，所以可以用来交换先后手。

 

这两个问题比较关键或者说有趣的地方其实在于先手可以任意选择先后手，并且在博弈论中证明这两个游戏中存在先/后手必胜策略是平凡的。

从这个思路解决问题的话其实和引入的题目的解题思路没什么关系...

 

从这个角度考虑3的话也很容易有一个思路，就是通过一个兵连续走两次一步来替代一次走两步，从而实现交换先后手。但具体分析会复杂一些。没有马应该是为了限制第一步必须走兵。但我不会国象，所以摸了。

 

顺便... 感觉都不算算法题。

二月 1, 2023，由l1ll5修改
补充

[l1ll5]

16 小时前，浮游小黑兔说道:

 

为什么问题2 任意步能包含(n,m)点？题目不是从right-up corner开始选一个矩形吗？除了第一步，之后操作不一定包含(n,m)。

例如一个4*3的矩阵，用X表示没选的块，O表示选过的块

那么对于选了(n,m)状态为：

XXXO

XXXX

XXXX

后手可以选left-down(2, 2), right-up(3,3)的矩形，结果为：

XOOO

XOOX

XXXX

此时，后手操作不一定包含(4,3)点

先手如何选取(n,m)来交换先后手呢？

我对题设的理解是此时

XOOO

XOOX

XXXX

红色位置不满足右边和上方均无未选点，所以这个操作不合法。