HDU-3537 Daizhenyang's Coin
Daizhenyang's Coin
有连个人互相博弈，给出若干个硬币，其中有 \(n\) 个硬币正面朝上，其余背面朝上，每个人每次操作：选择 1、2、3 个（可不连续）的硬币，将其翻面。并保证最左边的硬币一定得是由正面朝上翻转到背面朝上，如果没有办法进行操作，则判定输，求判断当前是否是先手必输
翻硬币博弈
这种类型的问题有一个定理：局面的SG 值为局面中每一个正面朝上的棋子单一存在时的SG 值的异或和
设当前正面朝上的硬币为1，背面朝上的硬币为0，则当前问题 [01100101] 可以分解为子问题 [01], [001], [000001], [00000001]，则可以视为 sg[01100101] = [01] ^ [001] ^ [000001] ^ [00000001]
于是就可以根据题目的要求推导一下sg函数：
#include
#include
using namespace std;
const int maxn = 1e5 + 10;
int sg[maxn];
int vis[maxn], num[maxn];
int main()
{
int n = 10;
sg[0] = 1;
sg[1] = 2;
sg[2] = 4;
for(int i=3; i<=n; i++)
{
for(int j=0; j 经过观察发现，所有的 sg[x] 都等于 2x 或者 2x + 1，但是没有办法知道什么时候是 2x 什么时候是 2x + 1
但是我们如果把 x 换成二进制数，就会发现，如果有奇数个 1，则 sg[x] = 2x，否则为 sg[x] = 2x + 1
哎，但是实际的证明还是没看懂：
同时该题的题目说了会给出重复的正面硬币朝上的情况，所以要进行去重
#include
#include
#include
using namespace std;
const int maxn = 110;
int num[maxn];
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
int sum = 0;
for(int i=0; i>= 1;
}
if(cnt & 1) x <<= 1;
else x = x << 1 | 1;
sum ^= x;
}
printf("%s\n", (sum && n) ? "No" : "Yes");
}
return 0;
}