Gray码：
先来看这么一个逗比问题：
一个月黑风高的夜晚，你成功潜入了银行。银行里的保险柜上有n个开关，
当每个开关都置于正确位置，保险柜会被打开，你的时间非常值钱，请你制定
一个作战计划，确保$2^n-1$次以内的操作能打开保险柜，不然正义的黑喵
警长会把你抓走！
为了逃避黑喵警长的魔爪，我们在这里得使用格雷码。
格雷码的介绍：
https://en.wikipedia.org/wiki/Gray_code
http://baike.baidu.com/item/%E6%A0%BC%E9%9B%B7%E7%A0%81
下面介绍几种比较实用的姿势。
1. 二进制 -> Gray
LL to_gray(LL x)
{
return x ^= (x>>1);//返回结果为Gray码的十进制表示。
}
2. Gray -> 二进制
LL to_bin(LL x)
{
LL y = x;
while(x>>=1)
{
y ^= x;
}
return y;
}
3. 构造长度为n的格雷码
构造姿势有很多种，不过直接把0~(1<<n)的二进制数字依次转为
格雷码是一种很方便的搞法。
vector<int> G;
for(int i=0;i<(1<<n);i++)
{
G.push_back(to_gray(i));
}
来切两道格雷码的题
Gym 101170 H
/*
求出两个格雷码对应的二进制数的十进制表示
做差即可。
*/
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
LL n, tmp[62];
char s1[62], s2[62];
LL to_bin(LL x)
{
LL y = x;
while(x>>=1)
{
y ^= x;
}
return y;
}
int main()
{
scanf("%lld %s %s", &n, s1+1, s2+1);
LL ans1 = 0;
for(int i=1;i<=n;i++)
{
ans1 += (LL)(s1[i]-'0')*(1LL<<(n-i));//此处有可能爆int
}
LL ans2 = 0;
for(int i=1;i<=n;i++)
{
ans2 += (LL)(s2[i]-'0')*(1LL<<(n-i));
}
LL res = to_bin(ans2) - to_bin(ans1) - 1;
cout << res << endl;
}
Gym 101252 J
/*
题目要我们生成组合 && 相邻的两个组合必须很接近由这
点，我们可以想到Gray码。
注意到台上的人数不能超过k。这和格雷码说好的不一样啊！
其实，如果我们把n阶格雷码中，1的个数大于k的元素删除
就会得到符合要求的序列。比较序列中相邻的两个元素，即
可得出操作。
为什么放逐掉那些数字，就能得到合法解呢？
下面粗略地分析了一下这个细思极恐的问题。
—————————————————昏割线——————————————————————————
先来看格雷码的另一种构造姿势：
a_{0},a_{1},.....a_{n-1}表示的格雷码的下
一个元素的构造方法
1. 如果 a_{0}+a_{1}+...+a_{n-1} 为偶数。
对最低位取反。eg: 101000 -> 101001
2. 如果 a_{0}+a_{1}+...+a_{n-1} 为奇数。
对位数最低的1的前一位取反。eg:101001 -> 101011
分析一下n=5,k=4的情况。
11110 舞台上有4个人
11111 咦！有5个人了，多出来了一个人。
11101 第1位 与 第0位 发生了交换
再来看看n=5,k=2的情况。
11000 舞台上有2人
11001 人多啦！
11011
11010
11110 (喵)
11111 (喵)
11101 (喵)
11100
10100 此时，舞台上人数为2。而且是11000的位数最低的1与
其右边发生了交换。注意到(喵喵喵)那三行。对应的正是n=5,k=4
的情况，因此该问题是可以通过第二类数学归纳法得到证明。
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
vector<int> vc;
int n, k;
//求出符合要求的序列。
void to_gray(LL x)
{
int cnt = 0, ans = x^(x>>1);
while(ans)
{
if(ans&1) cnt ++;
ans >>= 1;
}
if(cnt > k) return;
return vc.push_back(x^(x>>1));
}
//比较序列中相邻的两个元素，并得出该怎样操作。
void cmp(int x, int y)
{
int tmp = x^y;
int plus = 0, substr = 0;
for(int i=0;i<n;i++)
{
if((1<<i)&tmp)
{
if((1<<i)&x)
{
substr = i+1;
}
if((1<<i)&y)
{
plus = i+1;
}
}
}
if(plus && !substr)
{
printf("+%d", plus);
}
if(!plus && substr)
{
printf("-%d", substr);
}
if(plus && substr)
{
if(plus > substr)
{
printf("++%d", substr);
} else {
printf("--%d", substr);
}
}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin >> n >> k;
for(int i=0;i<(1<<n);i++)
{
to_gray(i);
}
for(int i=1;i<vc.size();i++)
{
cmp(vc[i-1], vc[i]);
}
printf("-%d", n);
}