D. *【博弈SG】模型一:翻转硬币(元问题)

    传统题 1000ms 128MiB

*【博弈SG】模型一:翻转硬币(元问题)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

【题意】
在一条直线上排列着一行硬币,有的正面朝上、有的背面朝上。
2名游戏者轮流对硬币进行翻转。
翻转时,先选一枚正面朝上的硬币翻转,如果愿意,可以从这枚硬币的左边选取一枚硬币一同翻转。
最后翻转使所有硬币反面朝上的玩家胜利。T表示朝下,H表示朝上。

上图将2和12同时翻转就构成一个合法的操作。
【输入格式】
多组数据,每组数据如下:
第一行一个整数n(1<=n<=100),表示有n个硬币朝上(即题目中的H状态)
第二行n个整数,表示朝上硬币的位置ai(1 <= ai <=10^8)
【输出格式】
每组数据输出一行。
如果先手赢输出 "Yes",否则输出"No"。

【样例输入】
5
2 5 9 10 12
【样例输出】
Yes

Hint

/*
解析:将位置i上的H看作一堆规模为i的石子,将i与j(j<i)同时翻转,
所得到的状态对应的源模型中nim中从一堆数目为i的石子中取i个,又还回来了j个,
相当于取了i-j个。PS:如果原来j为h,那么这样理解:只不过隐藏了两堆一样数目的石子。
*/

#include<bits/stdc++.h> using namespace std; int main() { int n,x,res; scanf("%d",&n); res=0; for(int i=1;i<=n;++i){ scanf("%d",&x); res^=x; } if(res>0) printf("Yes\n"); else printf("No\n"); return 0; }

</p>

寒假0207上午:博弈SG

未参加
状态
已结束
规则
XCPC
题目
7
开始于
2025-2-7 11:08
结束于
2025-2-7 11:40
持续时间
0.5 小时
主持人
参赛人数
21