题解：AT_agc031_c [AGC031C] Differ by 1 Bit
Wxb2010
·
·
题解
前言
这是一篇 \mathcal{O}(2^n) 的分治构造的题解。
构造题要大胆猜想，小心求证。下文中 \operatorname{pcnt}(x) 表示 x 在二进制下的 1 的个数。
解题
初步分析
相邻的位置，二进制恰有一位不同，不妨定义对某数的修改：将该数异或 2^k(0\le k<n)。
两个数的编辑距离：两个数的异或和的 \operatorname{pcnt}。即将一个数变成另一个数的最小修改次数。
首先可以观察到，序列首尾的两个数 $s,t$，$s$ 经过 $2^n-1$ 次修改后得到 $t$，由于 $2^n-1$ 一定是奇数，$dis(s,t)$ 也必须为奇数，否则无解，可以判掉。
我们似乎无法再找到一种无解的情况，不妨猜想：对于任意 $dis(s,t)$ 为奇数的情况，一定有解。
## 刻画问题
然而构造方案并不是很容易，进制相关问题中，一种常见的方法是按二进制位分析，
不妨从此方面考虑，尝试将原问题划分为两个规模相等的子问题。
为了让两个子问题之间不使用相同的数，我们可以选择一个二进制位，规定某一子问题使用的数该位必须为 $1$，另一个该位必须为 $0$。
那么，对于一个问题，可以刻画为六元组 $(s,t,l,r,T,S)$：当前要填入区间 $[l,r]$，使用的数必须是 $T$ 的超集、$S$ 的子集，下标 $l$ 必须填 $s$，下标 $r$ 必须填 $t$。
$l,r$ 容易分治，设一个 $mid=\frac{l+r}{2}$ 即可，考虑怎么处理另外四个变量。
$T$ 的超集限制可能影响到实现难度，所以下文中的 $s,t,S$，与 $T$ 有关的位（$T$ 在该位上为 $1$）都设置为 $0$，在递归边界时补上即可。
## 构造方案
定义**有效位**：$a$ 的某一二进制位为有效位，当且仅当 $a$ 在该位上为 $1$。
选择一个二进制位来区分左右子问题，令 $z=s\oplus t$，则选择 $z$ 的一个有效位 $h$ 作为区分位。
:::info[补充]{open}
由于 $dis(s,t)$ 为奇数，则 $z$ 一定有有效位。
:::
如果对递归左子问题选择 $(s,t\oplus 2^h,l,mid)$（后两位暂不考虑），那么 $dis(s,t\oplus 2^h)$ 是偶数，一定不行。
再额外取一位 $p$，如果 $z\oplus 2^h$ 有有效位，则从 $z\oplus 2^h$ 中取，否则从 $S\oplus 2^h$ 中取。（避免取到同一位）
对于两个子问题，分别递归 $(s,t\oplus 2^h\oplus 2^p,l,mid),(t\oplus 2^p,t,mid+1,r)$ 即可满足 $dis(s,t)$ 为奇数，且分治处满足题意。
对于 $S,T$ 的维护也是容易的，$s,t$ 中，哪个 $h$ 位上为 $1$，哪一侧的 $T$ 就补上该位；$S$ 删去 $h$ 位即可。此外，$s,t,S$ 注意删去与 $T$ 有关的位。
至此，我们成功将一个问题划分为两个互不影响、形式相同的子问题，边界条件是区间长为 $2$，填入 $s\oplus T,t\oplus T$ 即可。
求解的即为 $(A,B,0,2^n-1,0,2^n-1)$，上述 $h,p$ 的选取，都可以位运算 $\mathcal{O}(1)$ 求解，复杂度即为 $\mathcal{O}(2^n)$。
# 实现
:::info[code]
```cpp
#include<bits/stdc++.h>
using namespace std;//判了 EOF
#define pc(a) ((wrp==obuf+IO&&(fwrite(obuf,1,IO,stdout),wrp=obuf)),(*wrp++)=a)
#define pcnt(x) __builtin_popcount(x)
#define LG(x) (31^__builtin_clz(x))
const int IO=1<<17;
char obuf[IO+1],*wrp=obuf;
int n,res[IO+1];
inline void write(int x){
int sk[20],top=0;
do{
sk[++top]=x%10,x/=10;
}while(x);
while(top) pc(sk[top--]+'0');
pc(' ');
}
void solve(int s,int t,int l,int r,int T,int S){//要最小化 s,t 编辑距离
if(l+1==r) return res[l]=s|T,res[r]=t|T,void();//只剩两个数了
int mid=(l+r)>>1,z=s^t,h=1<<LG(z);//放的数是 S|T 的子集，T 的超集，S,s,t 以及删掉 T 有关部分了
int p=1<<LG((z!=h?z:S)^h),x=S^h;//h 位用来划分集合了，p 表示额外改变的一位
solve(s&x,(t^p^h)&x,l,mid,T|(s&h),x),solve((t^p)&x,t&x,mid+1,r,T|(t&h),x);
}
int main(){
int lgn,A,B;cin>>lgn>>A>>B,n=(1<<lgn)-1;//修改一定是奇数次，
if(~pcnt(A^B)&1){puts("NO");return 0;}// bit 位差为偶数一定不行
solve(A,B,0,n,0,n),pc('Y'),pc('E'),pc('S'),pc('\n');//分治构造
for(int i=0;i<=n;i++) write(res[i]);
return fwrite(obuf,1,wrp-obuf,stdout),0;
}
```
:::