高僧斗法

标签：opt 博弈 Nim 高僧 斗法 异或 position 石堆

https://www.luogu.com.cn/problem/P8606

思路

这个游戏和Nim博弈类似，但又不完全是。如果我们把小和尚之间的台阶看作石堆的话，那石堆中的石子不仅会变少，也会变多。

比如说，某个小和尚向上了移动了一个台阶，那么他前面的空间会变少，而后面的空间会变大，相当于把一个石堆的石子移动到另一个石堆，这其实是阶梯博弈（Staircase Nim）。

阶梯博弈

阶梯博弈：博弈在一列阶梯上进行，每个阶梯上放着自然数个点，两个人进行阶梯博弈，每一步则是将一个集体上的若干个点( >=1 )移到前面去，最后没有点可以移动的人输。

阶梯博弈的也可以进一步看作普通的Nim博弈：把所有奇数阶梯看成N堆石子

详细的解释可以看这篇文章

Nim博弈

而在Nim博弈中，判断是否可以获胜的方法为：现将所有石堆的数量进行异或运算，如果结果为0，无法获胜；如果结果不为0，可以取胜，只需要保证操作之后所有石堆的数量进行异或运算变成0。

比如，有三个石堆，石子的数量分别为3，4，2，对他们异或运算的结果是3⁴2=5，不为0，说明可以获胜，需要把第二堆石子，拿走三个，让石堆变为3，1，2，因为3¹2=0。

如果石堆刚开始就是3，1，2的话，那么无法获胜，因为无论怎么操作，最终的异或运算都不会是0了。

详细的解释可以看这篇文章

---

所以这道题可以这么做：

1. 转换为阶梯博弈
2. 转换为Nim博弈
3. 计算获胜的操作，无法获胜直接输出-1
4. 将Nim博弈的操作转为小和尚的移动

如图

代码如下：

position = [int(n) for n in input().split()]
# 等效的 奇数位置的 石堆
piles = [str(position[i] - position[i - 1] - 1) for i in range(1, len(position), 2)]
# 异或运算后的到0，说明无法获胜
if eval('^'.join(piles)) == 0:
    print(-1)
else:
    for i in range(len(piles)):
        # 计算除去当前石堆的异或
        equation = ['^'.join(piles[:i]), '^'.join(piles[i + 1:])]
        equation = '^'.join([item for item in equation if item])
        advantage_score = eval(equation) if equation else 0
        # 计算该石堆如何操作可以让整体的异或和为0
        opt = int(piles[i]) - advantage_score
        if opt > 0:
            # print(f'第{i}堆：拿走{opt}个')
            print(position[2 * i], position[2 * i] + opt)
            break
        if opt < 0 and position[2 * i + 1] - opt < position[2 * i + 2]:
            # print(f'第{i}堆：增加{-opt}个')
            print(position[2 * i + 1], position[2 * i + 1] - opt)
            break

标签：opt,博弈,Nim,高僧,斗法,异或,position,石堆
From： https://www.cnblogs.com/mengzhuo/p/17601529.html