NC20484. [ZJOI2009]取石子游戏
描述
输入描述
文件的第一行为一个整数T，表示有 T组测试数据。对于每组测试数据，第一行为一个整数n，表示有n堆石子；第二行为n个整数ai，依次表示每堆石子的数目。
输出描述
对于每组测试数据仅输出一个整数0或1。其中1表示有先手必胜策略，0表示没有。
示例1
输入:
1 4 3 1 9 4
输出:
0
C++14(g++5.4) 解法, 执行用时: 79ms, 内存消耗: 8284K, 提交时间: 2019-09-16 16:53:50
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 1010
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,a[MAX],L[MAX][MAX],R[MAX][MAX];
int main()
{
int T=read();
while(T--)
{
n=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)L[i][i]=R[i][i]=a[i];
for(int len=2;len<=n;++len)
for(int i=1,j=i+len-1;j<=n;++i,++j)
{
int x=a[j],l=L[i][j-1],r=R[i][j-1];
if(x==r)L[i][j]=0;
else if((x>l&&x>r)||(x<l&&x<r))L[i][j]=x;
else if(r<x&&x<l)L[i][j]=x-1;
else L[i][j]=x+1;
x=a[i],l=L[i+1][j],r=R[i+1][j];
if(x==l)R[i][j]=0;
else if((x>l&&x>r)||(x<l&&x<r))R[i][j]=x;
else if(r<x&&x<l)R[i][j]=x+1;
else R[i][j]=x-1;
}
puts(a[1]==L[2][n]?"0":"1");
}
}
C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 8312K, 提交时间: 2020-04-01 17:04:56
#include<stdio.h>
#include<string.h>
int n,a[1005],l[1005][1005],r[1005][1005];
int main()
{
int T,i,j,k;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
if(n==1)
printf("1\n");
else
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(l,-1,sizeof(l));
memset(r,-1,sizeof(r));
for(i=1;i<=n;i++)
l[i][i]=r[i][i]=a[i];
for(i=1;i<=n-1;i++)
{
for(j=1;j+i<=n;j++)
{
k=j+i;
if(r[j][k-1]==a[k]) l[j][k]=0;
else if(a[k]<r[j][k-1]&&a[k]<l[j][k-1]||a[k]>r[j][k-1]&&a[k]>l[j][k-1]) l[j][k]=a[k];
else if(r[j][k-1]<l[j][k-1]) l[j][k]=a[k]-1;
else l[j][k]=a[k]+1;
if(l[j+1][k]==a[j]) r[j][k]=0;
else if(a[j]<l[j+1][k]&&a[j]<r[j+1][k]||a[j]>l[j+1][k]&&a[j]>r[j+1][k]) r[j][k]=a[j];
else if(l[j+1][k]<r[j+1][k]) r[j][k]=a[j]-1;
else
r[j][k]=a[j]+1;
}
}
if(r[1][n-1]==a[n])
printf("0\n");
else
printf("1\n");
}
}
return 0;
}