Description

题目链接

题目大意:构造一个尽可能短的序列 $\{a_n\}$,满足 $\text{xor}_{i = 1}^n a_i = u, \sum \limits_{i = 1}^n a_i = v$。

Solution

首先当 $u > v$ 时显然无解,$u = v$ 时特判一下。

现在考虑 $u < v$ 的情况。一个显然的结论是 $u \equiv v \pmod 2$:考虑最低位上的情况,由于异或相当于不进位加法,最低位又没有可以向它进位的位,因此两个数最低位上的情况一定相同。

先往序列里加一个元素 $u$,然后考虑再加上 $v - u$,又由于 $v - u$ 一定是 $2$ 的倍数,因此 $\{u, \frac{v - u}{2}, \frac{v - u}{2}\}$ 一定是满足条件的。

现在再考虑缩短序列,如果 $u \& \frac{v - u}{2} = 0$,即两个数没有同为 $1$ 的位,那么可以将 $u$ 和 $\frac{v - u}{2}$ 合成一项。

看 dls 一分钟秒了这题...太可怕了...

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

LL u, v;

int main() {
    read(u), read(v);
    if (u == v) {
        if (u == 0) {
            puts("0");
            return 0;
        }
        printf("1\n%lld\n", u);
        return 0;
    }
    if (u % 2 != v % 2 || u > v) {
        puts("-1");
        return 0;
    }
    if ((((v - u) >> 1LL) & u))    printf("3\n%lld %lld %lld\n", (v - u) >> 1, (v - u) >> 1, u);
    else    printf("2\n%lld %lld\n", (v - u) >> 1, ((v - u) >> 1LL) ^ u);
    return 0;
}
Last modification:September 2nd, 2021 at 02:17 am