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

[浮游小黑兔]

16 小时前，reflectK说道:

如果要找胜利方法确实是dp

不过这里只需要证明解的存在性 所以有更简单的方法

dp？我怎么感觉是SG啊……这不是决策DAG上的多个子问题吗

问题1，有一个十分简单的解法：

首先当N=1时，显然先手胜

当N>=2时有：

由于1是任何数的因数，所以选取[2,N]的任何一个数，1都会被选走，那么提取 subproblem X：同原问题，在区间[2,N]上做博弈

对于 subproblem X 有两种结果：先手必胜，先手必败。

1. 若 X 为先手必胜，那么先手按照X的方法选取，博弈结果同原问题（[1,N]上的博弈），即先手必胜（因选取任何一个数a \in [2, N]，1必被选走）。

2. 若 X 为先手必败，那么对于原问题，先手第一步选1，此时问题归约为X，后手必败，即先手必胜。

综上，对于任意的N>=1，问题1存在先手必胜策略。

问题2（1，1）跟（n，m）位置没指明，即（1，1）是在左下还是左上？

问题3不清楚国际象棋具体规则，不做评论。

二月 1, 2023，由浮游小黑兔修改

[浮游小黑兔]

3 小时前，l1ll5说道:

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

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

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

 

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

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

 

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

 

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

 

1 小时前，reflectK说道:

正确的ww

所以说打了引号嘛w

不过可能引入的还是不太好w 下次再加油（？）

为什么问题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)来交换先后手呢？

[浮游小黑兔]

20 分钟前，reflectK说道:

不过主楼的那个变种先手有比较显然的必胜策略（）

这个显然吗，我看不出，求教