【刷题】BZOJ 1413 [ZJOI2009]取石子游戏

2023-10-21 21:09:58

Description

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

Input

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

Output

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

Sample Input

Sample Output

数据范围

对于30%的数据 n≤5 ai≤105

对于100%的数据 T≤10 n≤1000 每堆的石子数目≤109

Solution

重要性质：

对于一段区间 $[L,R]$ ，若 $L+1$ 到 $R$ 的石子固定，那么让当前先手在这段区间上必败的 $a_L$ 有且只有一个。 \pause

证明唯一：如果有两个必败态，那么由于其中一个必败态可以转移到另一个必败态，与定义矛盾，所以只会有一个必败态

证明存在：如果左边没有必败态，那么左边所有的必胜态都由右边的必败态转移过来。由于左边的石子可以有任意多个，但右边的石子是固定的，所以会有石子对应多个必败态，这与唯一性矛盾

根据这两条性质，得出一个做法

设 $L[i][j]$ 代表区间 $[i,j]$ 左边加上一堆数量为 $L[i][j]$ 的石子后先手必败；$R[i][j]$ 定义相似，代表右边

最后只要判断 $L[2][n]$ 是否等于 $a[1]$ 就知道先手是否有必胜策略

考虑计算这两个数组：发现 $L[i][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[i][i]=R[i][i]=a[i]$
$r=x$ ，已经确定先手必败，$L[i][j]=0$
$x \le l$ 且 $x \le r$ ，$L[i][j]=x$ 。后手要做的就是在另一边取与先手一样数量的石子，这样先手一定先取完一堆。假设先手取完的是右边一堆，那么根据我们的 $l=L[i][j-1]$ ，含义是区间 $[i,j-1]$ 左边加上数量为 $l$ 的石子先手必败，可以把当前局面等价于先手已经把数量为 $l$ 的这堆石子取了一些了，所以先手必败
$r \le x \leq l$ ，$L[i][j]=x-1$ 。假设先手拿的左边一堆，拿到 $y$ 个。若 $y \le r$ ，那么后手在右边一堆也拿到 $y$ 个，变成上面一种情况；若 $y > r$ ，那么后手拿到 $y+1$ ，变成当前情况递归。假设先手拿右边一堆，拿到 $y$ 个。若 $ y \le r$ 那么后手在左边一堆也拿到 $y$ 个，变成上面一种情况；若 $y=r$ ，后手直接取完左边一堆，由于 $R[i][j-1]=r$ ，所以先手必败；若 $y > r$ ，那么后手将左边一堆取到 $y-1$ ，变成这种情况递归。无论何种走向，最后只能是先手必败
$l \le x \leq r$ ，$L[i][j]=x+1$ 。类似于上面一种情况
$x > l$ 且 $x > r$ ，$L[i][j]=x$ 。假设先手取其中一堆到 $y$ 个。若 $y > l,r$ ，那么变成这种情况递归；若 $y \le l,r$ ，那么变成第二种情况；剩下的情况后手相应取到 $y+1$ 或 $y-1$ ，变成上面两种情况中的一种就好了

$L[i][j]$ 的所有情况都讨论完了，$R[i][j]$ 的求法类似。

复杂度 $O(Tn^2)$

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

#define ft first

#define sd second

#define pb(a) push_back(a)

#define PII std::pair<int,int>

#define PLL std::pair<ll,ll>

#define mp(a,b) std::make_pair(a,b)

#define ITR(a,b) for(auto a:b)

#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)

#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)

const int MAXN=1000+10;

int n,a[MAXN],L[MAXN][MAXN],R[MAXN][MAXN];

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char ch='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(ch!='\0')putchar(ch);

}

template<typename T> inline bool chkmin(T &x,T y){return y<x?(x=y,true):false;}

template<typename T> inline bool chkmax(T &x,T y){return y>x?(x=y,true):false;}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

int main()

{

	int T;read(T);

	while(T--)

	{

		int n;read(n);

		REP(i,1,n)read(a[i]),L[i][i]=R[i][i]=a[i];

		REP(len,2,n)REP(i,1,n-len+1)

		{

			int j=i+len-1,l,r,x;

			l=L[i][j-1],r=R[i][j-1],x=a[j];

			if(r==x)L[i][j]=0;

			else if(r<x&&x<=l)L[i][j]=x-1;

			else if(l<x&&x<=r)L[i][j]=x+1;

			else L[i][j]=x;

			l=L[i+1][j],r=R[i+1][j],x=a[i];

			if(l==x)R[i][j]=0;

			else if(l<x&&x<=r)R[i][j]=x-1;

			else if(r<x&&x<=l)R[i][j]=x+1;

			else R[i][j]=x;

		}

		puts(L[2][n]==a[1]?"0":"1");

	}

	return 0;

}

码农公寓