问题描述

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