3.2 KiB
HDU4315 Climbing the Hill
https://blog.csdn.net/weixin_43596048/article/details/102726258
一、题意
在山上有$n$个人，每个人编号是$1$~$n$，这些位置只能同时被一个人占据，但是山顶可以同时被多个人占据，距离山顶第$k$近的是$King$，现在$Alice$和$Bob$开始向上送人，条件是不能跨越前面最近的人，问在$Alice$先手，双方最优的条件下谁能把$King$送到山顶获胜。
二、解析过程
尼姆博弈变形。
$n$为偶数时：问题简化一下，假设全都是黄球，谁把最后一个球移出谁就赢
$(a_1,a_2) (a_3,a_4) …… (a_{2i-1},a_{2i}) ……(a_{n-1},a_n)$其中第$i$个球与第 $i+1$个球是相邻的，$i$为奇数，谁面对这个状态谁就必输。
理由很简单:先手移动第$i$个球，后手移动第 i+1 个球，使之仍然保持必赢状态。
黄海理解：按上面的说法，两两一组，组内视为奇数层台阶，$i+1-i-1$，也就是空格个数视为石子个数，这里都是$0$；组与组之间视为偶数层台阶，偶数层台阶的石子个数没有意义。
$$ \LARGE 组内 \Leftrightarrow 奇数阶 \ 组间 \Leftrightarrow 偶数阶$$
回到原问题谁先移出红球谁就赢:
- 假设红球是第一个球:$Alice$直接就赢了
- 假设红球不是第一个球: 很显然,如果红球在偶数位置后手必赢，如果在奇数$i$位置，则只需将第$i-1$个球移到第一个位置就$ok$了。 所以与红球位置无关。
至于产生这个状态$\large (a_1,a_2) (a_3,a_4) …… (a_{2i-1},a_{2i}) ……(a_{n-1},a_n)$，那么就是简单的$Nim$问题了
n 为奇数时，这里再分成两种情况。
当k！=2时把a1到最前边当成一个堆，剩下两两之间成堆，当k=2时，把a1-1当成一个堆，就是说第一个球移动到第一个位置(不是最前边)，剩下的不变，。谁先面对这种状态就输了。
题意：在山上有n个人，每个人编号是1~n，这些位置只能同时被一个人占据，但是山顶可以同时被多个人占据，距离山顶第k近的是King，现在Alice和Bob开始向上送人，条件是不能跨越前面最近的人，问在Alice先手，双方最优的条件下谁能把King送到山顶。
这题分两种情况：
1，King在第一位的时候，Alice获胜 ， 因为Alice先手可直接将King送到山顶。
2，King在第二位且人数n为奇数时，从后往前两两配对，那么第一个人最多只能停在a[1]上 ， 因为如果第一个人爬到山顶，那么king就可以直接上山顶了，所以这题可以转化为 ， 谁必须移动第一个人谁必败。
此时a[0] = 0; 例如 ， a[1] = 2, a[0]=0 ,a[1]只能移动到1的位置 所以这个堆是a[0]-1,而如果King不在第二位的话 ， 那么a[1]就可以直接移动到山顶了 ， 这个时候就比King在第二位时的情况多出一个 ， 因此令a[0] = -1 ， 因为-（-1) 等于 +1.
TODO https://www.cnblogs.com/Ritchie/p/5624945.html https://www.cnblogs.com/AWCXV/p/7626724.html