P2599 [ZJOI2009]取石子游戏
斯德哥尔摩
2018-07-28 22:52:35
[P2599 [ZJOI2009]取石子游戏](https://www.luogu.org/problemnew/show/P2599)
博弈论的$Nim$游戏中比较难的题。
首先，讲个性质：
取石子时，当先手使得左右两边的石子相等时，可以保证先手必胜。
因为当先手取到左右石子相等的局面时，则后手无论在哪一堆取石子，接下来先手都可以有相同的方法取另一堆石子。
这样又回到了原来的状态（左右石子相等），则无论如何先手都有办法应对后手的取法。
设在区间$[i,j]$左边放$Left[i][j]$（可以为0）个石子后（区间内石子保持原状），产生的局面为**先手必败局面**，$Right[i][j]$就是在右边放，定义类似。
设$val[i]$为第i堆石子个数。
最后我们只用看$Left[2][n]$是否等于$val[1]$就可以了。（如果等于就说明这个情况先手必败，否则先手必胜）
这一题可以注意到对于一段区间$[L,R]$, 若$L+1$到$R$的石子数固定, 那么使得在这段区间上先手必败的$val[L]$有且仅有一个。
接下来证明$Left[i][j]$是唯一的：
1. 若存在两或以上个$Left[i][j]$，则从某一个必定可一步转移到另一个，矛盾，故最多只有一个。
2. 若没有$Left[i][j]$，那么必胜态只可能通过拿右边的石子转移到某个必败态。
由于此时左边石子可以是任意个，右边石子数固定，于是必有右边的某一个石子数对应了多种必败态。
这些必败态只有左边的石子数不同，与1矛盾，舍去。
最后我们考虑$Left[i][j]$的求法，分类讨论：
设$l=Left[i][j-1],r=Right[i][j-1],w=val[j]$。通过下面的分析我们可以发现#Left[i][j]#只和$l,r,w$三个数有关.
1. 边界条件：$Left[i][i]=Right[i][i]=val[i]$.
两堆一样的，后手照着先手拿的数量在另一堆拿即可。
2. 首先，最容易想到的是$r==w$的情况，这时$[i,j]$这段区间已经先手必败，那么$Left[i][j]==0$。
3. 若$w<l,w<r$，则$Left[i][j]=w$。
因为此时当两堆石子相同时，后手照着先手取，这样先手一定会先拿完某一堆，后手占据主动。
这之后又会出现某一种我们分类讨论中的情况，相当于一种递归，直到后手获胜。
4. 若$w<l,w>r$，则$Left[i][j]=w-1$。
此时如果先手在左边拿使其个数变为y，若$y<r$，则后手在右边也拿到y即可变为情况3；
若$y>=r$，则后手在右边拿到$y + 1$，于是回到了相同的情况。
若先手在右边拿到$y$，若$y<r$，同样可到情况3；
若$y==r$, 直接把左边的堆拿完，先手便面临败局；
若$y>r$，则在左边拿到$y-1$，回到相同情况。
5. 若$w<r,w>=l$，则$Left[i][j]=w+1$，与情况4恰好相反。
6. 若$w>l,w>r$，则$left[i][j]=w$。
若先手将某一堆拿到了$y$，且$y>r$, 跟着先手拿即可回到相同情况；
若$y<l$，回到情况3；
若在在左边拿到$l$或在右边拿到$r$，后手拿掉另一堆即可；
否则根据情况在另一堆拿到$y-1$或是$y+1$，分别对应情况4和5。
$Right[i][j]$的求法与$Left[i][j]$完全对称，照搬即可。
最后只需判断$val[1]==Left[2][n]$。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 1010
using namespace std;
int n;
int val[MAXN],Left[MAXN][MAXN],Right[MAXN][MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
if(val[1]==Left[2][n])printf("0\n");
else printf("1\n");
}
void init(){
n=read();
for(int i=1;i<=n;i++)Left[i][i]=Right[i][i]=val[i]=read();
for(int k=1;k<=n;k++)
for(int i=1;i+k<=n;i++){
int j=i+k,l=Left[i][j-1],r=Right[i][j-1],w=val[j];
if(r==w)Left[i][j]=0;
else if(l>w&&r>w)Left[i][j]=w;
else if(l<=w&&r>w)Left[i][j]=w+1;
else if(l>w&&r<w)Left[i][j]=w-1;
else Left[i][j]=w;
l=Left[i+1][j];r=Right[i+1][j],w=val[i];
if(r==w)Right[i][j]=0;
else if(l>w&&r>w)Right[i][j]=w;
else if(l<=w&&r>w)Right[i][j]=w+1;
else if(l>w&&r<w)Right[i][j]=w-1;
else Right[i][j]=w;
}
}
int main(){
int t=read();
while(t--){
init();
work();
}
return 0;
}
```