HDU-4315 Climbing the Hill

r囧r小猫 2021-12-03 23:19 204阅读 0赞

[题目链接][Link 1]  
先回到阶梯博弈的裸题中，比如POJ-1704，所有的块只能向左移并且不能跨越，这个向左移的结果我们可以理解为将左边的宽度减少使得右边的宽度增加，等同于阶梯模型中将石子从高阶移动到低阶。那么最右边的一对相邻块之间的宽度就是第一阶的石子个数，从右到左依次为为第一阶第二阶......用变量来表示如下：

> 设块初始位置为\\(a\[1\],a\[2\]...a\[n\]\\)，那么在阶梯模型中第一阶的石子个数为\\(a\[n\]-a\[n-1\]-1\\)（想一想为什么减一）,第二阶为\\(a\[n-2\]-a\[n-3\]-1\\cdots\\) 以此类推如果n为偶数，那么最高的一阶为\\(a\[2\]-a\[1\]-1\\)，否则为\\(a\[1\]-1\\)

在阶梯博弈中，我们将奇数阶的石子转换为nim游戏中的一堆石子，原因是:

如果对奇数阶石子进行挪动，等同于在nim游戏中取走石子

如果对偶数阶石子挪动到奇数阶，我们总可以在下一步操作中将移过去的石子再转移到它现在的一下阶上，使得奇数阶石子并没有发生变化。

这样就可以保证这个游戏等价转换为nim游戏。

为什么要用奇数阶石子来代替？

因为1阶可以移动到0阶，而移动过去的石子再也没有办法移动了。

为什么要转换为nim游戏？因为游戏初始的那一刻，在保证双方都绝顶聪明的情况下胜负已分，一定会用等价于nim的游戏策略进行下去。

好了到此为止阶梯博弈基础重述完毕。

在这道题目中，我们要使得k这个位置上面的人先到达终点，既然这样，那么k-1位置上面的人必须先一步到达终点。所以我们要找一个局面，使得对手不得不把k-1位置上面的人移动过去。

首先 k = 1的话先手必胜

然后我们把这个模型转换为阶梯模型，从右向左开始组队

n为奇数时：\\((a\_0,a\_1),(a\_2,a\_3),\\cdots (a\_\{n-1\},a\_n)\\)  
n为偶数时：\\((a\_1,a\_2),(a\_3,a\_4),\\cdots(a\_\{n-1\},a\_n)\\)

我们之前提到，改变这些对中两个数的差完全等同于nim游戏。

假设现在他们所有的差异或起来是0，那么先手只可能移动奇数位上面的数字（例如\\(a\_3\\))，那么后手就会跟进（例如\\(a\_4\\)），保持这个局面一直不变。

设一对数中第一个数是\\(fi\\) （例如n为奇数时的\\(a\_2\\)),第二个数是\\(se\\)(例如n为偶数时的\\(a\_3\\))。

k 是\\(se\\) 时很好理解，先手迟早会移动k-1，后手只需要跟着移动总能赢。

若k在\\(fi\\) 时，我们设想，先手总会把 k-2 这个位置移动到终点，我们只需要在下一步将第k-1个位置移动到终点前就好了（这是为了逼迫先手在之后无路可走时，移动k-1），然后只需等待先手挪动了k-1，我们就可以挪动k到终点了。

一般情况下n为奇数时，\\(a\_0 = -1\\)，\\(a\_1-a\_0-1\\)即为\\((a\_0,a\_1)\\)之间的宽度，因为\\(a\_1\\)可以挪动到终点即0位置，但是k如果为2，那么\\(a\_0=0\\)，即不能挪动到终点位置（挪动到终点则破坏了局面之间的转换，直接使得下一步操作的人获胜）

#include <bits/stdc++.h> using namespace std; int n,k; int a[1010]; int main(){ while(cin>>n>>k){ for(int i=1;i<=n;i++)scanf("%d",&a[i]); if(k == 1){ puts("Alice");continue; } sort(a+1,a+1+n); int sum = 0; k == 2 ? a[0] = 0 : a[0] = -1; for(int i=n;i>=1;i-=2){ sum ^= a[i]-a[i-1]-1; } sum ? puts("Alice") : puts("Bob"); } return 0; }

转载于:https://www.cnblogs.com/1625--H/p/11200442.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=4315