唯一性

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

假设 \(L[i][j]\) 存在两个，那么我们先让 \([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=L[i][j-1],R=R[i][j-1],x=a[j]\)

\(x=R\)

这种情况下，我们令 \(L[i][j]=0\) ，因为 [i,j] 已经是个必败态了，左边加上任意石子，先手都可以全部取完，然后后手面对必败态
\(x<L,x<R\)

这种情况下，我们令 \(L[i][j]=x\) ，这样先手不管从哪堆开始取，如果没有取完，后手只需要在另一堆取走相同数量的石子，就回到了原来的情况，那么如果说先手把一堆取完了，另一堆的石子数量必然是小于 L 和 R 的，相当于是先手从数量为 L 或者 R 的堆中取走了一些石子，后手必胜
\(L<=x<R\)

这种情况下，我们令 \(L[i][j]=x+1\) ，这样先手左边取左边取，取到 L 时，后手取光右边即可；左边取到比 L 大的话，右边只要取走相同的石子就好了，这样可以变回同样的状态；取到比 L 小的话，右边取到相同的石子数为止，这样两边的石子数都小于 L 和 R ，这样就回到了状态 2 ；如果先手在右边取，如果取到比 L 大，我们维持状态即可，和上面一样；如果比 L 小，那么我们左边取到和左边相等，这样还是回到了状态 2 ；如果右边被先手取光了，那么我们把左边取到 L ，先手面临的就是必败态了
\(R<x<L\)

这种情况下，我们令 \(L[i][j]=x-1\) 即可，讲道理是和状态 3 差不多的情况 Q^Q
\([i,i]\) 的边界情况

我们只需要让 \(L[i][i]=a[i]\) 即可...因为左边放上 a[i] 就是先手必败的状态，考虑此时无论先手在哪里取，后手只要在另一堆里面取相同石子即可...

感谢

ORZ YYB

Code

//by Judge

#include<bits/stdc++.h>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define ll long long

using namespace std;

const int M=1003;

typedef int arr[M][M];

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline ll read(){ ll x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} char sr[1<<21];int CC=-1;

inline void Ot(){fwrite(sr,1,CC+1,stdout),CC=-1;}

int n,a[M]; arr L,R;

int main(){ int T=read();

	while(T--){ n=read();

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

		fp(len,1,n-2) fp(i,2,n-len){

			Rg int j=i+len;

			if(R[i][j-1]==a[j]) L[i][j]=0;

			else if(L[i][j-1]>a[j]&&R[i][j-1]>a[j]) L[i][j]=a[j];

			else if(L[i][j-1]<=a[j]&&R[i][j-1]>a[j]) L[i][j]=a[j]+1;

			else if(L[i][j-1]>a[j]&&R[i][j-1]<a[j]) L[i][j]=a[j]-1;

			else L[i][j]=a[j];

			if(R[i+1][j]==a[i]) R[i][j]=0;

			else if(L[i+1][j]>a[i]&&R[i+1][j]>a[j]) R[i][j]=a[i];

			else if(L[i+1][j]<=a[i]&&R[i+1][j]>a[j]) R[i][j]=a[i]+1;

			else if(L[i+1][j]>a[i]&&R[i+1][j]<a[j]) R[i][j]=a[i]-1;

			else R[i][j]=a[i];

		}

		sr[++CC]=48+(a[1]!=L[2][n]),sr[++CC]='\n';

	}

	return Ot(),0;

}

巴特西

[ZJOI2009]取石子游戏

唯一性

转移

感谢

Code

最新文章

热门文章