【题解】HDU 3537 Daizhenyang's Coin

请注意,本文编写于 96 天前,最后修改于 92 天前,其中某些信息可能已经过时。

Problem

给定一排长度无限的硬币,其中有 $n$ 个是正面朝上的
给出正面朝上的硬币位置 $a_i$

每次操作可以翻转 $1,2$ 或 $3$ 枚硬币,其中最右端的硬币必须是正面 $\rightarrow$ 反面

无法操作者失败

Thought

看起来像是个 $sg$ 函数的题
设 $sg[i]$ 表示第 $i$ 个位置有硬币的 $sg$ 函数,注意第一个硬币的位置是 $0$ ,没有硬币状态为 $-1$

$$ sg[i]=mex\{sg[-1],sg[j],sg[j]\oplus sg[k]\}(j<k<i) $$

首先显然的 $sg[-1]=0$
接下来列出前面的一些 $sg$ 函数的取值

$$ sg[-1]=0\\ sg[0]=1\\ sg[1]=2\\ sg[2]=4\\ sg[3]=7\\ sg[4]=8\\ sg[5]=11\\ sg[6]=13 $$

发现一个规律:

$$ sg[i]= \begin{cases} i*2\\ i*2+1 \end{cases} $$

那么说明决定是否 $+1​$ 的就是能否在前面选出两个 $sg[j],sg[k]​$ 使得 $sg[j]\oplus sg[k]=2*i​$

首先若有 $sg[j]\oplus sg[k]=2*i$ , $sg[j],sg[k]$ 必然同为 $2i+1$ 或者 $2i$ 形式
并且有 $sg[j]\oplus sg[k]=2j\oplus 2k=2(j\oplus k)=2i$
则 $j\oplus k =i$

最终结论为当 $i$ 二进制中有奇数个 $1$ 时,为 $2i$ ,否则为 $2i+1$
可以从结论倒推,正向还真不会...

找规律找出来的...

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int getSG(int x) {
    int sum = x, ans = 0;
    while(x) {
        ans ^= (x & 1);
        x >>= 1;
    }
    return sum * 2 + (ans ^ 1);
}
map<int, bool> Map;
int n;
int main() {
    while(~scanf("%d", &n)) {
        int ans = 0;
        Map.clear();
        while(n --) {
            int a = read();
            if(!Map[a]) {
                ans ^= getSG(a);
                Map[a] = 1;
            }
        }
        puts(ans ? "No" : "Yes");
    }
    return 0;
}
Comments

添加新评论