【一本通提高博弈论】[ZJOI2009]取石子游戏
2024-08-27 14:26:59
[ZJOI2009]取石子游戏
题目描述
在研究过 Nim 游戏及各种变种之后,Orez 又发现了一种全新的取石子游戏,这个游戏是这样的:
有
n
n
n 堆石子,将这
n
n
n 堆石子摆成一排。游戏由两个人进行,两人轮流操作,每次操作者都可以从最左或最右的一堆中取出若干颗石子,可以将那一堆全部取掉,但不能不取,不能操作的人就输了。
Orez 问:对于任意给出一个初始一个局面,是否存在先手必胜策略。
输入格式
文件的第一行为一个整数
T
T
T,表示有
T
T
T 组测试数据。对于每组测试数据:
第一行为一个整数
n
n
n,表示有
n
n
n 堆石子。
第二行为
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \ldots , a_n
a1,a2,…,an,依次表示每堆石子的数目。
输出格式
对于每组测试数据仅输出一个整数
0
0
0 或
1
1
1。其中
1
1
1 表示有先手必胜策略,
0
0
0 表示没有。
输入输出样例
样例输入1
1
4
3 1 9 4
样例输出1
0
说明/提示
对于
30
%
30 \%
30% 的数据,
n
≤
5
n \le 5
n≤5,
a
i
≤
10
5
a_i \le {10}^5
ai≤105。
对于
100
%
100 \%
100% 的数据,
1
≤
T
≤
10
1 \le T \le 10
1≤T≤10,
1
≤
n
≤
1000
1 \le n \le 1000
1≤n≤1000,
1
≤
a
i
≤
10
9
1 \le a_i \le {10}^9
1≤ai≤109。
Code
#include <bits/stdc++.h>
using namespace std;
int T;
int n, a[1005], l[1005][1005], r[1005][1005];
int main()
{
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
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 L = l[i][j - 1], R = r[i][j - 1], x = a[j];
if (x == R)
l[i][j] = 0;
if (x < L && x < R)
l[i][j] = x;
if (R < x && x < L)
l[i][j] = x - 1;
if (L < x && x < R)
l[i][j] = x + 1;
if (x > L && x > R)
l[i][j] = x;
L = l[i + 1][j], R = r[i + 1][j], x = a[i];
if (x == R)
r[i][j] = 0;
if (x < L && x < R)
r[i][j] = x;
if (R < x && x < L)
r[i][j] = x + 1;
if (L < x && x < R)
r[i][j] = x - 1;
if (x > L && x > R)
r[i][j] = x;
}
}
if (l[2][n] == a[1])
puts("0");
else
puts("1");
}
}
最新文章
- JavaScript和jQuery的类型判断
- Eclipse查看hadoop源代码出现Source not found,是因为没有添加.zip
- git 学习笔记3--status flow
- ssh框架介绍
- easyUI——datebox验证和自定义取消按钮
- DCEF3 相关资料
- hihocoder #1177 : 顺子 模拟
- 【JS】壹零零壹
- CODEVS 2451 互不侵犯
- Oracle表连接总结
- 团队作业4——第一次项目冲刺(Alpha版本)2017.4.22
- java应用的jar包多合一
- BZOJ_2795_[Poi2012]A Horrible Poem_hash+暴力
- 【 PostgreSQL】查询某模式下所有表的分布键信息
- shell脚本--cut命令与awk简单使用
- cmake 常用变量和常用环境变量查表手册---整理 .
- jdbc连接oracle时使用的字符串格式
- uva-317-找规律
- POJ 2396 Budget(有源汇上下界网络流)
- OC 对象调用属性或实例变量或方法的细节。