HDU 3537 Daizhenyang's Coin(博弈,翻硬币)
39 HDU 博弈 硬币
2023-09-27 14:26:07 时间
Daizhenyang's Coin
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 183 Accepted Submission(s): 83
Problem Description
We know that Daizhenyang is chasing a girlfriend. As we all know, whenever you chase a beautiful girl, there'll always be an opponent, or a rival. In order to take one step ahead in this chasing process, Daizhenyang decided to prove to the girl that he's better and more intelligent than any other chaser. So he arranged a simple game: Coin Flip Game. He invited the girl to be the judge.
In this game, n coins are set in a row, where n is smaller than 10^8. They took turns to flip coins, to flip one coin from head-up to tail-up or the other way around. Each turn, one can choose 1, 2 or 3 coins to flip, but the rightmost selected must be head-up before flipping operation. If one cannot make such a flip, he lost.
As we all know, Daizhenyang is a very smart guy (He's famous for his 26 problems and Graph Theory Unified Theory-Network Flow does it all ). So he will always choose the optimal strategy to win the game. And it's a very very bad news for all the competitors.
But the girl did not want to see that happen so easily, because she's not sure about her feelings towards him. So she wants to make Daizhenyang lose this game. She knows Daizhenyang will be the first to play the game. Your task is to help her determine whether her arrangement is a losable situation for Daizhenyang.
For simplicity, you are only told the position of head-up coins. And due to the girl's complicated emotions, the same coin may be described twice or more times. The other coins are tail-up, of course.
Coins are numbered from left to right, beginning with 0.
In this game, n coins are set in a row, where n is smaller than 10^8. They took turns to flip coins, to flip one coin from head-up to tail-up or the other way around. Each turn, one can choose 1, 2 or 3 coins to flip, but the rightmost selected must be head-up before flipping operation. If one cannot make such a flip, he lost.
As we all know, Daizhenyang is a very smart guy (He's famous for his 26 problems and Graph Theory Unified Theory-Network Flow does it all ). So he will always choose the optimal strategy to win the game. And it's a very very bad news for all the competitors.
But the girl did not want to see that happen so easily, because she's not sure about her feelings towards him. So she wants to make Daizhenyang lose this game. She knows Daizhenyang will be the first to play the game. Your task is to help her determine whether her arrangement is a losable situation for Daizhenyang.
For simplicity, you are only told the position of head-up coins. And due to the girl's complicated emotions, the same coin may be described twice or more times. The other coins are tail-up, of course.
Coins are numbered from left to right, beginning with 0.
Input
Multiple test cases, for each test case, the first line contains only one integer n (0<=n<=100), representing the number of head-up coins. The second line has n integers a1, a2 … an (0<=ak<10^8) indicating the An-th coin is head up.
Output
Output a line for each test case, if it's a losable situation for Daizhenyang can, print "Yes", otherwise output "No" instead.
Sample Input
0
1
0
4
0 1 2 3
Sample Output
Yes
No
Yes
Source
Recommend
zhouzeyong
经典模型。
详见:http://www.cnblogs.com/kuangbin/p/3218060.html
各个位置的SG值异或就行了
注意先去掉重合的点
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; int SG(int x) { int tmp = x; int cnt = 0; while(tmp) { if(tmp&1)cnt++; tmp>>=1; } if(cnt&1)return 2*x; else return 2*x + 1; } int a[110]; int main() { int n; while(scanf("%d",&n)==1) { for(int i = 0;i < n;i++) scanf("%d",&a[i]); sort(a,a+n); n = unique(a,a+n)-a; int sum = 0; for(int i = 0;i < n;i++) sum ^= SG(a[i]); if(sum)printf("No\n"); else printf("Yes\n"); } return 0; }
相关文章
- undefined reference to `__android_log_print'
- 2014 网选 广州赛区 hdu 5023 A Corrupt Mayor's Performance Art
- ZOJ 3804 YY's Minions (简单模拟)
- hdu Caocao's Bridges(无向图边双连通分量,找出权值最小的桥)
- SSM处理 No 'Access-Control-Allow-Origin' header is present on the requested resource 问题
- [Artoolkit] ARToolKit's SDK Structure on Android
- 彻底解决tensorflow:ImportError: Could not find 'cudart64_90.dll' tensorflow安装
- $GLOBALS['HTTP_RAW_POST_DATA'] 和$_POST的区别
- 数据库设计理论与实践·<五>常见疑难杂症
- 数据库之MySQL ERROR 1698 (28000) 错误:Access denied for user 'root'@'localhost'" error【摘抄】
- 'ping' 不是内部或外部命令,也不是可运行的程序
- java执行sql语句使用别名时显示Column '***' not found
- linux中竖线'|',双竖线‘||’,&和&&的意思
- How to deal with the problem '<' in OpenERP's view file
- XHXJ's LIS HDU - 4352 最长递增序列&数位dp
- A - Alice's Print Service ZOJ - 3726 (二分)
- shell出现syntax error near unexpected token `<' 解决方法
- fatal error LNK1104: cannot open file 'MSCOREE.lib'
- HDU 2852 KiKi's K-Number
- nginx 安装时候报错:make: *** No rule to make target `build', needed by `default'. Stop.
- 本机jdbc连接报The user specified as a definer ('root'@'%') does not exist
- rabbitmq inequivalent arg 'x-message-ttl' for queue 'QUEUE_NAME' in vhost '/'异常解决
- mysql grant all on *.* to xxx@'%' 报Access denied for user 'root'@'localhost'