bzoj 1413 [ZJOI2009]取石子游戏

1413: [ZJOI2009]取石子游戏

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 747  Solved: 490
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

1
4
3 1 9 4

Sample Output

0

数据范围
对于30%的数据 n≤5 ai≤105
对于100%的数据 T≤10 n≤1000 每堆的石子数目≤109

 

 参考了这里的思路。可以发现对于任意一段[i,j]，在其左边添上一个数，只有唯一的一个数（包括0即不添加）能够使新的序列[i-1,j]是一个必败状态。显然，如果有两个x,y都满足，不妨设x<y，那么对于y+[i,j]这个状态，可以把y取到x使其成为必败状态，这与每一个必败状态都转移不到必败状态矛盾。故得证。可知在右边添上一个数同理。

       令l[i][j]表示[i,j]左边添上的数，r[i][j]表示右边添上的数。假设我们已经知道了x=l[i-1][j],y=r[i][j-1],z=a[j]，那么：

       1.特殊情况a[j]=y，那么[i,j]本身就是一个必败状态，l[i][j]=0；

       2.如果a[j]<x,y，那么令l[i][j]=a[j]，然后先手在一边取k个，后手就在另一边取k个。新手显然先取到了，那么此时还剩下的那一堆的数量显然<x,y，因此后手有必胜策略；

       3.考虑x<=a[j]<y，那么令l[i][j]=a[j]+1，然后在第j堆个数>=x时，后手始终保持让第i-1堆得比第j堆得多一个；当第j堆个数<x时，后手始终保持第i-1堆和第j堆相同，然后同2；

       4.考虑y<a[j]<=x，那么令l[i][j]=a[j]-1，然后同3；

       5.考虑a[j]>x,y，那么令l[i][j]=a[j]。不妨设x<y（x>y同理），那么当第i-1堆个数>y时，后手保持第i-1堆和第j堆相同；然后同3；

       最后，如果a[1]==l[2][n]则无解；反之有解。

#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>

#define N 1007
using namespace std;

int n,a[N],l[N][N],r[N][N];

int main()
{
    int cas;scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (int i=1;i<=n;i++)
            l[i][i]=r[i][i]=a[i];
        for (int i=n-1;i>=1;i--)
            for (int j=i+1;j<=n;j++)
            {
                int x=l[i][j-1],y=r[i][j-1],z=a[j];
                if (z==y) l[i][j]=0;
                else if (z<x&&z<y||z>x&&z>y) l[i][j]=z;
                else if (x>y) l[i][j]=z-1;
                else l[i][j]=z+1;
                x=r[i+1][j],y=l[i+1][j],z=a[i];
                if (z==y) r[i][j]=0;
                else if (z<x&&z<y||z>x&&z>y) r[i][j]=z;
                else if (x>y) r[i][j]=z-1;
                else r[i][j]=z+1;
            }
        if (n==1) printf("%d
",1);
        else printf("%d
",(a[1]==l[2][n])?0:1);
    }
}