题解 CF1325D 【Ehab the Xorcist】

2020-03-15 13:33:18


提供一种与大多数题解不同的方法。

显然 $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$ 进制输出即可。

#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;
}