嘘~ 正在从服务器偷取页面 . . .

CF1325D Ehab the Xorcist 题解

发布日期: 2024-01-18

更新日期: 2024-01-19

文章字数: 591

CF1325D Ehab the Xorcist 题解

题意：

给定整数 $u$ 和 $v(0\le u,v \le 10^{18})$

试构造长度最短的数组，使得数组内所有元素的异或和为 $u$，加和为 $v$。

如果有解，输出两行，第一行输出一个整数 $n$，第二行输出 $n$ 个非负整数，表示数组里的元素。

多解输出任意一组即可。如果无解，输出一行一个整数 $-1$。

Codeforces 居然没有 C++14 的提交方式了。

简单观察样例可以发现结论， $u > v$ 时一定无解。

这点很容易证明，因为异或本质上是二进制下的不进位加法，所以无论如何值都不会变得更大。

根据上面的结论，可以发现

$a + b = (a\oplus b) + 2(a \land b)$

即

$a + b - (a\oplus b) = 2(a \land b)$

这里的 $(a\land b)\times 2$ 表示的是手动进位（因为异或是不进位加法）

当然这里还有一个附加的结论，即 $\left(\sum_i x_i - \bigoplus_i x_i\right)$ 的值一定为偶数。

记 $\Delta = v - u$ ，则一般情况下 $\Delta$ 可以拆分为 $\{\frac{\Delta}{2},\frac{\Delta}{2}\}$ ，也就是说 $\{\frac{\Delta}{2},\frac{\Delta}{2},u\}$ 是一个一般可行解。

那什么时候不是可行解呢？其实就是一些特殊情况：

$\Delta = 0\,\land\,u = v \ne 0$ ，此时解为 $\{u\}$ 。
$\Delta = 0 \,\land \,u = v = 0$ ，此时解为 $\varnothing$ 。
$(u \land \frac{\Delta}{2}) = 0$ ，此时我们可以直接以 $u \oplus \frac{\Delta}{2}$ 合并，即解为 $\{\frac{\Delta}{2},\frac{\Delta}{2} \oplus u\}$ 。

时间复杂度 $\mathcal{O}(1)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int u,v; cin >> u >> v;
    int d = v - u;
    if(d < 0 || (d & 1)) return cout << "-1\n", 0;
    if(d == 0) { u ? (cout << "1\n" << u) : (cout << '0'); cout << '\n'; }
    else {
        int x = d >> 1;
        if((x & u) == 0) cout << "2\n" << x << ' ' << (x ^ u) << '\n';
        else cout << "3\n" << x << ' ' << x << ' ' << u << '\n';
    }
    return 0;
}