问题描述

思路（Nim博弈）

Nim博弈在这篇文章写的很好：

https://blog.csdn.net/qq_41923622/article/details/86707861

因为数学功底不扎实，所以我在这边只说结论：

以题目给出案例为例：

将两个和尚之间的距离分别拿出来生成一个新的列表

也即是：3 （由 5 - 1 - 1,得到）；3 （由9 - 5 - 1 得到）

首先将其转换成二进制再异或比较得到结果

异或用符号^，例如2 ^ 3 = 1，即分别求出2和3的二进制，再进行比较，相同为0，不相同为1

如果结果是0，那就是后手必赢，如果结果非0，那先手必赢

所以此处先手必赢，那为了使后手输，就得把移动和尚来使得相加的结果为0

注：为什么进行异或计算时，每两个和尚组成一堆，所以每两个堆一个组：

在原文作者石头的例子中，直接就是按照石头堆的数量进行计算。而在我们题目中，首先计算间隔来等效替代各堆石头的数量，但是本题中移动一个的位置会影响两堆的数量，因此采用两堆组成一组的形式，所以在异或计算时也是采用步长为2.

总结就是改变一个，多少会随之而改变，就利用这个作为一组

代码

# main
# 输入数据，并将位置信息转换成间隔信息，也即是Nim转换
pos = input().split()
heap = [0 for _ in range(len(pos) - 1)]
for i in range(len(pos)):pos[i] = int(pos[i])
# Nim转换
for i in range(len(pos) - 1):heap[i] = pos[i + 1] - pos[i] - 1
# 进行异或计算
temp_sum = 0
for i in range(0, len(pos) - 1, 2):temp_sum ^= heap[i]
# 进行判断
if sum == 0:print(-1)
else:temp_j = 1000for i in range(len(pos) - 1):for j in range(1, temp_j):if(pos[i] +j >= pos[i + 1]):breakelse:heap[i] -= jif(i != 0):heap[i - 1] += jsum = 0for k in range(0, len(pos) - 1, 2):sum ^= heap[k]if(sum == 0):print(pos[i], pos[i] + j)heap[i] += jif i != 0:heap[i - 1] -= jj += 1continueelse:heap[i] += jif i != 0:heap[i - 1] -= jj += 1

文字描述：

预处理得到min转换后的列表，和位置信息

判断过程：

如果异或得到0，那就返回-1

不然，以位置为循环，然后遍历往前走的步数

如果超过前面一位了，那就break，不然的话，将前后的heap和pos的列表信息进行更改，并且需要注意在i == 0的情况下，需要进行更改

然后在再计算其异或值，如果为0那就输出，如果不是，那就回溯，将值变换回原来的值。

疑问：

最初我看的是c语言网上一个同学的代码，然后我发现了一个问题（这是他的代码）

k=list(map(int,input().strip().split()))
kl=len(k)
b=[0 for _ in range(kl-1)]#堆的数量是和尚数-1
for i in range(1,kl): #放堆b[i-1]=k[i]-k[i-1]-1
sum=0
for i in range(0,kl-1,2):#进行异或，每两个和尚组成一堆，所以每两个堆一组，所以步数为2sum^=b[i]
if sum==0: #若开始局面为0 则必输print(-1)
else:#若非0 则必赢，因此 需要找到第一步 将局面变为0 的步骤for i in range(kl-1):#枚举移动第i堆  使得剩下的局面异或等于0，j=1while True:#枚举可以移动的步数  保证 前项移动j 步后 不会超过后项# print(k)if k[i]+j>=k[i+1]:breakb[i] -= j #拿走 j个 ，这里代表 前一个向上移动j步if(i!=0):b[i-1] += j #它的后一堆b[i]向取走了j个，那莫前一堆 b[i-1] 则要增加j个 第一堆除外sum=0for s in range(0,kl-1,2):#进行异或,重新计算局面sum^=b[s]if sum==0:print(k[i],k[i]+j)#若变成0  则后手必败，先手必赢。跳出即可；breakb[i] += j #回溯 这不是必赢的操作if i!=0:b[i-1] -= jj+=1

如果对于一个小和尚来说，不止一种移动方式，例如小和尚a往前走5步可以，往前走12步也可以达到要求，那这种回溯方法其实会省略后一种走法，所以我进行了更改，在break改成continue后重复一段回溯过程

然后应该是大于等于，不然可能导致两个小和尚站在一个台阶上的情况