100 #P1167. *【博弈SG】模型一:翻转硬币(元问题)
*【博弈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,那么这样理解:只不过隐藏了两堆一样数目的石子。 */</p>#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; }
相关
在下列比赛中: