题解 CF1325D 【Ehab the Xorcist】

提供一种与大多数题解不同的方法。 显然 $u>v$ 或 $u$ 与 $v$ 奇偶性不同时无解。 对于有解的情况，以 $u=14$ ，$v=20$ 为例， 先把 $u$ 和 $v$ 变成长度相同的 $2$ 进制串，高位补 $0$ 。 $$u:01110\ \ \ \ \ v:00101$$ 接着把答案数组看成 $2$ 进制，把 $v$ 的每一位转化成答案数组中这一位为 $1$ 的数的数量。 忽略其他数，对某一位上的数进行考虑。 若想让 $u$ 的某一位为 $0$ ，则 $v$ 的这一位显然要是偶数； 若想让 $u$ 的某一位为 $1$ ，则 $v$ 的这一位显然要是奇数。 即 $u$ 与 $v$ 的每一位的奇偶性必须相同。 然后从最高位开始循环，若第 $i$ 位 $u$ 与 $v$ 奇偶性不同，则 $v_i--$ ，$v_{i-1}+=2$ ，显然这样不影响 $v$ 的大小。 对以上例子进行这步操作后 $:$ $$u:01110\ \ \ \ \ v:00101$$ $$↓$$ $$u:01110\ \ \ \ \ v:00120$$ $$↓$$ $$u:01110\ \ \ \ \ v:00310$$ $$↓$$ $$u:01110\ \ \ \ \ v:2\text-1310$$ 然后发现出现了负数，于是需要让低位向高位借位，类似于减法借位。 这一步从低位开始循环。 若 $v$ 的第 $i$ 位为负数则 $v_i+=2$ ，$v_{i+1}--$ 。 但是这样会改变高位的奇偶性，所以仍需要在第 $i$ 位 $u$ 与 $v$ 奇偶性不同时 $v_i--$ ，$v_{i-1}+=2$ 。 对以上例子进行这步操作后 $:$ $$u:01110\ \ \ \ \ v:2\text-1310$$ $$↓$$ $$u:01110\ \ \ \ \ v:21210$$ $$↓$$ $$u:01110\ \ \ \ \ v:23110$$ 此时保证了 $u$ 与 $v$ 的每一位奇偶性相同且没有负数。 答案数组的第 $i$ 位为 $1$ 的次数是 $v_i$ ，所以答案数组的最小长度即为 $v$ 数字串中最大的数，在以上例子中答案数组的最小长度为 $3$ 。 构造答案数组十分简单，只要满足在 $2$ 进制下答案数组第 $i$ 位为 $1$ 的数的数量等于 $v_i$ 即可。 对于以上例子，答案数组可构造为： $$ans_1:11110$$ $$ans_2:11000$$ $$ans_3:01000$$ 每一位相加就是： $$23110\text{（即为v数字串）}$$ 最后转化为 $10$ 进制输出即可。 ```cpp #include<bits/stdc++.h> using namespace std; #define int long long #define N 64 int n,m,a[N],b[N]; signed main(){ scanf("%lld%lld",&n,&m); if(n>m||((m-n)&1)){ puts("-1"); return 0; } int tot1=0,tot2=0,tot,ans=0,t; a[++tot1]=n&1; while(n/=2) a[++tot1]=n&1; b[++tot2]=m&1; while(m/=2) b[++tot2]=m&1; tot=max(tot1,tot2); for(int i=tot;i>0;i--) if((b[i]-a[i])&1)b[i-1]+=2,b[i]--; for(int i=1;i<tot;i++){ if((b[i]-a[i])&1)b[i-1]+=2,b[i]--; if(b[i]<0)b[i]+=2,b[i+1]--; } for(int i=1;i<=tot;i++) ans=max(ans,b[i]); printf("%lld\n",ans); for(int i=1;i<=ans;i++){ t=0; for(int j=1,k=1;j<=tot;j++,k<<=1) if(b[j])t+=k,b[j]--; printf("%lld ",t); } return 0; } ```