HDU 3537 Daizhenyang's Coin【翻硬币游戏】

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=3537

题意:

翻硬币游戏,每次可以翻动一个、二个或三个硬币,并且最右边的硬币开始必须是正面朝上的(Mock Turtles游戏)。

分析:

上个月的时候做过这题,因为不知道如何打表,所以直接照论文背下来的结论 = =
今天逛csdn的时候看见了打表的姿势,然后重新看了一遍题目,才发现我看错题了。。。
题目中说的并不是连续的拿若干个!!
这样将单个游戏看成只有一枚硬币正面朝上,其余全是反面朝上。那么对于翻转2,3个硬币的情况,看成单个游戏的组合。所以可以直接打!表!找规律!下面附打表代码。
最后观察发现当$2n$中$1$的个数为奇数的时候,其$sg$值为$2n$,否则为$2n+1$。输入的时候判断一下$a_i$的奇偶即可。
顺便附hihocoder中的一道类似题,讲解很好。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*************************************************************************
> File Name: 3537.cpp
> Author: jiangyuzhu
> Mail: 834138558@qq.com
> Created Time: 2016/7/31 13:46:50
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e2 + 5;
int a[maxn];
bool vis[maxn];
int sg[maxn];
void gao()
{
sg[0] = 1;
for(int i = 1; i < 50; i++){
memset(vis, false, sizeof(vis));
for(int j = 0; j < i; j++) vis[sg[j]] = true;
for(int j = 0; j < i; j++){
for(int k = 0; k < j; k++){
vis[sg[j] ^ sg[k]] = true;
}
}
for(int j = 1;; j++){//只有一个硬币可翻,不会输
if(!vis[j]){
sg[i] = j;
break;
}
}
cout<<i<<' '<<sg[i]<<" cal "<< __builtin_popcount(2 * i) <<endl;
}
}
int main (void)
{
int n;
// gao();
while(~scanf("%d", &n)){
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
}
sort(a, a + n);
int nn = unique(a, a + n) - a;//记得去重
int ans = 0;
for(int i = 0; i < nn; i++){
if(__builtin_popcount(a[i]) & 1) ans ^= 2 * a[i];
else ans ^= 2 * a[i] + 1;
}
if(ans) puts("No");
else puts("Yes");
}
return 0;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: