ZJOI是什么神仙出题组，能想到这道题目，不看题解一辈子写不出来

---

这道题不可做，不看题解连思路都没有（我还是太蒟蒻了）

首先设立状态转移数组$L[l][r]$，表示在$[l,r]$的左边放上一段大小为$L[l][r]$的石子的情况下必败，同理可以定义$R[l][r]$

然后也可以很快的得到边界情况，就是$L[i][i]=R[i][i]=w[i]$，这个也很好理解对于两堆相同的石子，后手一定可以进行和先手对称的操作

再然后好像大概是没有思路了（我就止步于此），然后呢，很简单（很简单在哪里），暴力分讨就行了

我们在此先分讨$L[l][r]$，$R[l][r]$也可以同理得到

首先令$L=L[l][r-1]，R=R[l][r-1]，x=w[r]$

---

$Case1$

$R=x$时由定义可得此时$[l,r]$是必败局面，$L[l][r]=0$

---

$Case2$

$x\lt min(L,R)$时$L[l][r]=x$，即证状态$(x,a_l,a_{l+1}...a_{r-1},x)$是必败态

因为左右两端相等，所以后手一定能进行和先手对称的操作，直到产生形如

$(a_l,a_{l+1}...a_{r-1},y)$或$(y,a_l,a_{l+1}...a_{r-1})$的状态

因为$0\lt y\le x\lt min(L,R)$，由数组定义可得此时$L\not= R\not= y$一定是必胜态，即先手必败

注意这里我们规定了$x\not= 0$，因此后面如果要直接使用$Case2$需要满足$x\not= 0$这个条件

---

$Case3$

$L\le x\lt R$时$L[l][r]=x+1$，即证状态$(x+1,a_l,a_{l+1}...a_{r-1},x)$是必败态

这里继续分讨

A.若先手拿左边的那堆，设拿完后还剩$z$个

1.若$z\gt L$，后手可以将右边那堆拿成$z-1$个，因为$z-1\ge L\gt 0$，回到$Case3$本身

2.若$z=L$，后手不妨直接将右边那堆拿完，由$L[l][r-1]$定义可知目前是必败局面

3.若$0\lt z\lt L$，后手可以将右边那堆拿成$z$个，就回到$Case2$是必败局面

4.若$z=0$，此时右边那堆的个数$L\le k\lt R$，由定义可得目前是必败局面

B.若先手拿右边的那堆，设拿完后还剩$z$个

1.若$z\gt L$，后手可以将左边那堆拿成$z+1$个，回到$Case3$本身

2.若$0\lt z\le L$，后手可以将最左边那堆拿成$z$个，回到$Case2$的必败局面

3.若$z=0$，后手可以将最左边那堆拿成$L$个，由定义可得目前是必败局面

---

$Case4$

$R\lt x\le L$时$L[l][r]=x-1$，即证状态$(x-1,a_l,a_{l+1}...a_{r-1},x)$是必败态

证明同$Case3$

A.若先手拿左边的那堆，设拿完后还剩$z$个

1.若$z\ge L$，后手可以将右边那堆拿成$z+1$个，回到$Case4$本身

2.若$0\lt z\lt L$，后手可以将最右边那堆拿成$z$个，回到$Case2$的必败局面

3.若$z=0$，后手可以将最右边那堆拿成$R$个，由定义可得目前是必败局面

B.若先手拿右边的那堆，设拿完后还剩$z$个

1.若$z\ge R$，后手可以将左边那堆拿成$z-1$个，回到$Case4$本身

2.若$z=R$，后手不妨直接将左边那堆拿完，由$R[l][r-1]$定义可知目前是必败局面

3.若$0\lt z\lt R$，后手可以将左边那堆拿成$z$个，就回到$Case2$是必败局面

4.若$z=0$，此时左边那堆的个数$0\lt k\lt L$，由定义可得目前是必败局面

---

$Case5$

$x\gt max(L,R)$时$L[l][r]=x$，即证状态$(x,a_l,a_{l+1}...a_{r-1},x)$是必败态

假设先手取了其中一堆变成了$z$个

1.若$z\gt max(L,R)$，回到$Case5$本身

2.若$0\lt z\lt max(L,R)$，将另一堆也拿成$z$个便得到$Case2$的必败局面

3.若$z=0$，只需要将另一堆拿成$L$或$R$，由定义可得此时必败

4.若$L\le z\le R$或$R\le z\le L$

$Case3$可以解决最左堆$L\lt z\le R$，最右堆$L\le z\lt R$的情况

同理$Case4$可以解决最左堆$R\le z\lt L$，最右堆$R\lt z\le L$的情况

所以我们只需解决最左堆是$z=L$和最右堆是$z=R$的情况

而这两种情况把另一堆拿完就可以由定义得到必败

---

综上所述，我们得到

L[l][r]= \begin{cases} 0, &{x=R}\\ x+1, &{L\le x\lt R}\\ x-1, &{R\lt x\le L}\\ x, &otherwise \end{cases}$$ <h4> 同理也可以得到$R[l][r]$的转移方式 而最后解的判断直接由数组定义得到 当且仅当$L[2][n]=w[1]$或$R[1][n-1]=w[n]$时（只用判断一种）时先手必败 </h4> ```c++ /* 其实也挺好想的一道题目，每次的子游戏只有少了最左和最右两种 然后带记忆化 DFS 一下应该就可以解决了 其实也可以类似区间 DP 的思路找吧 私人阴间分讨，ZJOI你无敌了 🐎爆炸了 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair< int,int > #define QAQ return ; #define QWQ return 0; #define TAT return const int N=1e3+10; int w[N]; int L[N][N] ,R[N][N]; void sovel() { int n; cin>>n; for( int i=1;i<=n;i++ ) for( int j=1;j<=n;j++ ) L[i][j]=R[i][j]=0; for( int i=1;i<=n;i++ ) cin>>w[i], L[i][i]=R[i][i]=w[i]; for( int len=2;len<=n;len++ ) { for( int l=1, r=l+len-1;r<=n;l++, r++ ) { int l1=L[l][r-1], r1=R[l][r-1], x1=w[r]; if( x1 == r1 ) L[l][r]=0; else if( x1 >= l1 && x1 < r1 ) L[l][r]=x1+1; else if( x1 <= l1 && x1 > r1 ) L[l][r]=x1-1; else L[l][r]=x1; int l2=L[l+1][r], r2=R[l+1][r], x2=w[l]; if( x2 == l2 ) R[l][r]=0; else if( x2 >= r2 && x2 < l2 ) R[l][r]=x2+1; else if( x2 <= r2 && x2 > l2 ) R[l][r]=x2-1; else R[l][r]=x2; } } cout<<( L[2][n] == w[1] ? "0\n" : "1\n" ); } int main() { // freopen( "txt.in","r",stdin ); ios::sync_with_stdio( false ); cin.tie( nullptr ), cout.tie( nullptr ); int t; for( cin>>t;t;t-- ) sovel(); QWQ } ```