题解：P8438 极寒之地

· · 题解

题解：P8438 极寒之地

思路

这道题可以使用格雷码。所谓格雷码，它的解释如下：

格雷码属于可靠性编码，是一种错误最小化的编码。
虽二进制码可直接由数模转换器转换成模拟信号，但在特例情况下：
如 (3)10 转换成 (4)10 时二进制码的每一个码位都需要改变，
能使数字电路产生极大的尖峰电流脉冲。
但是格雷码却没有这一个缺点，它在相邻位间进行转换时，
只有一码位发生变化。它很好地解决了普通编码的逻辑混淆问题。

也就是说：格雷码是指两数编码后的二进制数只有一位数不同，另且格雷码中 Min 数与 Max 数仅一位编码不同。

如下图，二进制数编码与格雷码编码仅有一码位之差，并且在二进制码中，数位不是 0 就是 1，所以在转化成格雷码的时候，一般都是直接将二进制数编码的最高码位到
最低码位依次判断，直到查找到第一个一个为 0 的码位，将此数位的数替换成 1：

解法

所以，就出现了格雷码的解法。我们可以直接维护所有子集，并且使用 __builtin_ctz() 来维护修改的数位。其实用 ffs() 也不是不可以。

那么我们配合按位异或、按位与，就可以直接写出 AC 代码。

代码

#include<bits/stdc++.h> //万能头
using namespace std;
int n,s=0;
unsigned long long a[35],ans,tot; //防止自溢，用 unsigned long long 类型
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=1;i<(1<<n);i++){
        int t=(i)&(-i); //直接按位与
        tot^=a[__builtin_ctz(t)]; //依次按位异或
        s^=t;
        ans^=tot*s;
    }
    cout<<ans<<endl; //输出结果，下课！
    return 0;
}