define 奇数 png turn ret 硬币 一道 fin
有一个取数的游戏。初始时,给出一个环,环上的每条边上都有一个非负整数。这些整数中至少有一个 0。然后,将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏,两人轮流取数,取数的规则如下:
(1)选择硬币左边或者右边的一条边,并且边上的数非 0;
(2)将这条边上的数减至任意一个非负整数 (至少要有所减小);
(3)将硬币移至边的另一端。
如果轮到一个玩家走,这时硬币左右两边的边上的数值都是 0,那么这个玩家就输了。
如下图,描述的是 Alice 和 Bob 两人的对弈过程,其中黑色节点表示硬币所在节点。结果图 (d) 中,轮到 Bob 走时,硬币两边的边上都是 0,所以 Alcie 获胜。
(a)Alice (b)Bob (c)Alice (d)Bob
现在,你的任务就是根据给出的环、边上的数值以及起点(硬币所在位置),判断先走方是否有必胜的策略。
输入格式:
第一行一个整数 N(N≤20),表示环上的节点数。
第二行 N 个数,数值不超过 30,依次表示 N 条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。
输出格式:
仅一行。若存在必胜策略,则输出 "YES",否则输出 "NO"。
- 【输入1】
- 4
- 2 5 3 0
- 【输入2】
- 3
- 0 0 0
- 【输出1】
- YES
- 【输出2】
- NO
- 一脸蒙蔽的看完题解。、
这是一道数学题。。。
我们来举个例子:有一条边 R 从 x 指向 y,它的数值大于 0,AB 对弈,现在 A 走
那么如果数值为 1,A 走过去,数值变为 0,B 就走不回来了
如果数值为 2,A 走过去,数值变为 1,如果 B 走回来,A 不就死了?我们认为他们都足够聪明,怎么会做这种事情呢?(假设过来的前一条边已经走完了,数值为 0)
如果数值大于 3(我们假定为 3),A 走过去,数值变为 2,B 如果仁慈地走回来,数值变为 1,这样不就浪费了一步?
B 如果按照题意残忍地用最佳行动走回来,取光所有数值,那么数值变为 0,这条路就封死了,A 做了一件无意义的事情,还封死了自己可以走的一条路,这对于先手的 A 而言是不利的,
这两种方法都明显有违双方最优的前提。
[/color][b] 所以我们可以知道,无论是 A 走还是 B 走,即无论是先手走还是后手走,每走过一条路都一定取完,这样问题就简单了 [/b]
因为至少有个 0,所以就简单了一点。。谁把对手逼到死路(两边都是 0 的)就赢了
从起始点开始向两边找,只要有一边到 0 边距离为奇数就是先手赢反之后手赢
- 1#include 2#include 3#include 4#include 5#include 6#define lli long long int 7 const int MAXN = 2333;
- 8 int n,
- s[MAXN];
- 9 int judge(int p) 10 {
- 11
- return p & 1;
- 12
- }
- 13 void read(int & n) 14 {
- 15 char c = ' + ';
- int x = 0;
- bool flag = 0;
- 16
- while (c < '0' || c > '9') 17 {
- c = getchar();
- if (c == ' - ') flag = 1;
- }
- 18
- while (c >= '0' && c <= '9') 19 {
- x = x * 10 + (c - 48);
- c = getchar();
- }
- 20 flag == 1 ? n = -x: n = x;
- 21
- }
- 22 int main() 23 {
- 24 read(n);
- 25
- for (int i = 1; i <= n; i++) 26 read(s[i]);
- 27 int a = 0;
- 28
- while (s[++a]);
- 29 int b = 0;
- 30
- while (s[n + 1 - (++b)]);
- 31
- if (judge(--a) || judge(--b)) 32 printf("YES");
- 33
- else printf("NO");
- 34
- }
P1288 取数游戏 II
来源: http://www.bubuko.com/infodetail-2151536.html