【AtCoder Grand 031C】Differ by 1 Bit 题解

题目大意

  给出 $N,A,B$，要求构造一个长度为 $2^N$ 的排列 $P_0,...,P_{2^N-1}$，使得 $P_0=A$，$P_{2^N-1}=B$，且相邻两个元素二进制下只有一位不同。若不存在则输出 NO。
  $N \leq 17$

学艺不精

  正好不久前数电课学了格雷码，这题又恰好是长度为 $2$ 的幂的排列且相邻两个元素只有一位不同，就自然想到了用格雷码来构造。
  用格雷码的话，相当于构造一个从 $0$ 到 $A \oplus B$ 的格雷码序列，最后再全部异或 $A$。当然，要调整一下二进制位谁先谁后。

  结果 WA 到死。。。

  用格雷码的本质错误在于，格雷码是要求循环的，但是这个题所要的排列是不循环的，所以 “$A$ 和 $B$ 只有一位不同” 这个有解判断是错的。

题解

  先从有解判断开始。因为每次改一个二进制位，因此最后 $A$ 和 $B$ 二进制下必须有奇数个位不同。这个是必要条件。
  然后通过构造方法能证明充分性。假设 $A$ 和 $B$ 在第 $x$ 位不同，那么大家都去掉第 $x$ 位，变成 $A'$ 和 $B'$，这样它们就有偶数位不同了。任意把 $A'$ 再改一位变成 $mid$，这样 $A'$ 和 $mid$、$mid$ 和 $B'$ 都有奇数位不同了。递归构造 $(A',mid)$ 和 $(mid,B')$，得出两个序列拼起来，再把第 $x$ 位补上，前面的序列第 $x$ 位跟 $A$ 相同，后面的序列第 $x$ 位跟 $B$ 相同。

  这位大佬的几何解释更加直观：https://www.cnblogs.com/zhoushuyu/p/10548483.html

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=2e5+5;

int n,a,b,N,er[30],c[maxn];

int lowbit(int x) {return x&(-x);}

bool bz[30];
void dfs(int k,int a,int b)
{
	if (k==1)
	{
		printf("%d %d ",a,b);
		return;
	}
	fo(i,0,n-1) if (((a>>i)&1)^((b>>i)&1))
	{
		bz[i]=1;
		int mid=a;
		fo(j,0,n-1) if (!bz[j])
		{
			mid^=er[j];
			break;
		}
		dfs(k-1,a,mid);
		dfs(k-1,mid^er[i],b);
		bz[i]=0;
		break;
	}
}

int main()
{
	scanf("%d %d %d",&n,&a,&b);
	N=(1<<n)-1;
	
	fo(i,0,N)
		for(int x=i; x; x-=lowbit(x)) c[i]++;
	fo(i,0,n-1) er[i]=1<<i;
	
	if ((c[a]&1)==(c[b]&1)) puts("NO"); else
	{
		puts("YES");
		dfs(n,a,b);
	}
}