题目链接

  情况非常复杂,事实上题解我现在也没有完全理解

  不过大致的意思就是

  设两个数组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 ;
}
05-11 22:23