BZOJ 1413: [ZJOI2009]取石子游戏博弈+Dp

2024-03-09 14:15:41

title

在研究过Nim游戏及各种变种之后，Orez又发现了一种全新的取石子游戏，这个游戏是这样的：有n堆石子，将这n堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。 Orez问：对于任意给出一个初始一个局面，是否存在先手必胜策略。

Input

文件的第一行为一个整数T，表示有 T组测试数据。对于每组测试数据，第一行为一个整数n，表示有n堆石子；第二行为n个整数ai，依次表示每堆石子的数目。

Output

对于每组测试数据仅输出一个整数0或1。其中1表示有先手必胜策略，0表示没有。

Sample Input

1
4
3 1 9 4

Sample Output

0
数据范围
对于30%的数据 n≤5 ai≤105
对于100%的数据 T≤10 n≤1000 每堆的石子数目≤109

analysis

首先我们令：
$L[i][j]$ L[i][j] 表示当前 $[i,j]$ [i,j] 区间左侧放置 $L[i,j]$ L[i,j] 数量的石子后先手必败；
$R[i][j]$ R[i][j] 表示当前 $[i,j]$ [i,j] 区间右侧放置 $R[i,j]$ R[i,j] 数量的石子后先手必败。
那么最后我们只要判断 $a[1]$ a[1] 是否等于 $L[2,n]$ L[2,n] 或者 $a[n]$ a[n] 是否等于 $R[1,n−1]$ R[1,n−1] 即可。

唯一性
考虑证明 $L[i][j]$ L[i][j] 和 $R[i][j]$ R[i][j] 的唯一性，发现我们只需要证明一个成立即可。

假设 $L[i][j]$ L[i][j] 存在两个，那么我们先让 $[i,j]$ [i,j] 左边放上大的 $L[i][j]$ L[i][j]，那么它可以一步转移到另一个小的 $L[i][j]$ L[i][j] ，仍旧是一个必败态，与定义矛盾，故 $L[i][j]$ L[i][j] 只存在一个合法值。

转移
然后我们分类讨论…
假设当前处理到了 $L[i][j]$ L[i][j] ，那么我们根据 $L[i][j−1],R[i][j−1],a[j]$ L[i][j−1],R[i][j−1],a[j] 来处理，我们令 $L=L[i][j−1],R=R[i][j−1],x=a[j]$ L=L[i][j−1],R=R[i][j−1],x=a[j]。

$x=R$ x=R
这种情况下，我们令 $L[i][j]=0$ L[i][j]=0 ，因为 $[i,j]$ [i,j] 已经是个必败态了，左边加上任意石子，先手都可以全部取完，然后后手面对必败态。
$x<L,x<R$ x<L,x<R
这种情况下，我们令 $L[i][j]=x$ L[i][j]=x ，这样先手不管从哪堆开始取，如果没有取完，后手只需要在另一堆取走相同数量的石子，就回到了原来的情况，
那么如果说先手把一堆取完了，另一堆的石子数量必然是小于 $L$ L 和 $R$ R 的，相当于是先手从数量为 $L$ L 或者 $R$ R 的堆中取走了一些石子，后手必胜。
$L\leq x<R$ L≤x<R
这种情况下，我们令 $L[i][j]=x+1$ L[i][j]=x+1 ，这样先手左边取左边取，取到 $L$ L 时，后手取光右边即可；
左边取到比 $L$ L 大的话，右边只要取走相同的石子就好了，这样可以变回同样的状态；
取到比 $L$ L 小的话，右边取到相同的石子数为止，这样两边的石子数都小于 $L$ L 和 $R$ R ，这样就回到了状态 2 ；
如果先手在右边取，如果取到比 $L$ L 大，我们维持状态即可，和上面一样；
如果比 $L$ L 小，那么我们左边取到和左边相等，这样还是回到了状态 2 ；
如果右边被先手取光了，那么我们把左边取到 $L$ L ，先手面临的就是必败态了。
$R<x<L$ R<x<L
同上，我们令 $L[i][j]=x−1$ L[i][j]=x−1 即可。
$[i,i]$ [i,i] 的边界情况
我们只需要让 $L[i][i]=a[i]$ L[i][i]=a[i] 即可…因为左边放上 $a[i]$ a[i] 就是先手必败的状态，考虑此时无论先手在哪里取，后手只要在另一堆里面取相同石子即可…

最后，yyb $Orz$ Orz。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;

char buf[1<<15],*fs,*ft;
inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
template<typename T>inline void read(T &x)
{
    x=0;
    T f=1, ch=getchar();
    while (!isdigit(ch) && ch^'-') ch=getchar();
    if (ch=='-') f=-1, ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}

char Out[1<<24],*fe=Out;
inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
template<typename T>inline void write(T x)
{
    if (!x) *fe++=48;
    if (x<0) *fe++='-', x=-x;
    T num=0, ch[20];
    while (x) ch[++num]=x%10+48, x/=10;
    while (num) *fe++=ch[num--];
    *fe++='\n';
}

int a[maxn],l[maxn][maxn],r[maxn][maxn];
int main()
{
	int T;read(T);
	while (T--)
	{
		int n;read(n);
		for (int i=1; i<=n; ++i) read(a[i]),l[i][i]=r[i][i]=a[i];
		for (int len=1; len<=n; ++len)
			for (int i=1; i+len<=n; ++i)
			{
				int j=i+len;
				int L=l[i][j-1],R=r[i][j-1],z=a[j];
				if (R==z) l[i][j]=0;
				else if (L>z && R>z) l[i][j]=z;
				else if (L<=z && R>z) l[i][j]=z+1;
				else if (L>z && R<z) l[i][j]=z-1;
				else l[i][j]=z;
				L=l[i+1][j],R=r[i+1][j],z=a[i];
				if (R==z) r[i][j]=0;
				else if (L>z && R>z) r[i][j]=z;
				else if (L<=z && R>z) r[i][j]=z+1;
				else if (L>z && R<z) r[i][j]=z-1;
				else r[i][j]=z;
			}
		write(a[1]==l[2][n]?0:1);
	}
	flush();
	return 0;
}

码农公寓

title

analysis

code

相关文章