情况非常复杂,事实上题解我现在也没有完全理解
不过大致的意思就是
设两个数组lef[][],rig[][]表示对应区间左端加一堆数量为lef[][]的石子使得先手必败,rig同理
可以通过一堆证明证明求出来的值具有唯一性
所以最后需要判断lef[2][n]是不是等于a[1]。
对于一段区间[i,j]我们设L=lef[i][j-1],R=rig[i][j-1],X=a[j]
据说lef[i][j]只跟这三个数有关
情况大致分以下五种
1:R=X,此时lef[i][j]=0,因为此时[i,j]已经必败了,左边瞎搞就好
2:X<L&&X<R,此时lef[i][j]=X,因为这样左右两边就能对齐,然后后手占据主动,然后递归。
3:X<L&&X>R,此时lef[i][j]=X-1,因为这时候先手在左边拿,后手从右边xjb拿成同样结果就行;如果先手在右边拿,后手从左边拿完全可以绕回当前的局势来,如果先手把右边拿到R,后手直接把lef[][]加的那堆石子清空,先手就GG了
4:X>=L&&X<R,跟4完全相反
5:X>L&&X>R,lef[i][j]=x。
rig[][]求法跟lef[][]对称。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cctype>
#define maxn 2020
using namespace std;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} int lef[maxn][maxn];
int rig[maxn][maxn]; int main(){
int T=read();
while(T--){
int n=read();
for(int i=;i<=n;++i) lef[i][i]=rig[i][i]=read();
for(int len=;len<n;++len)
for(int i=;i+len-<=n;++i){
int j=i+len-;
int L=lef[i][j-],R=rig[i][j-],x=lef[j][j];
if(R==x) lef[i][j]=;
else if(x<L&&x<R) lef[i][j]=x;
else if(x<L&&x>R) lef[i][j]=x-;
else if(x<R&&x>=L) lef[i][j]=x+;
else if(x>L&&x>R) lef[i][j]=x; L=rig[i+][j],R=rig[i+][j],x=lef[i][i];
if(L==x) rig[i][j]=;
else if(x<L&&x<R) rig[i][j]=x;
else if(x>L&&x<R) rig[i][j]=x-;
else if(x<L&&x>=R) rig[i][j]=x+;
else if(x>L&&x>R) rig[i][j]=x;
}
if(lef[][n]==lef[][]) printf("0\n");
else printf("1\n");
}
return ;
}