CodeForces 思维题集锦 #1 - 76D (1700)

原题链接：76D Plus and xor (dp, greedy, math, *1700)

题意简述

给定两个数 ，你需要构造出两个数 ，使得 且 的同时， 尽量小。

解法分析

一道很 CF 的构造题。

首先，根据异或不进位加法的性质，两个数的异或和不超过它们的和，因此当 时无解。

同样根据不进位加法的性质，我们知道 与 的奇偶性必定相同，即 必定为偶数，否则无解，剩余情况均有解。

我们考虑如何构造符合条件的 同时 尽量小：

如果 和 有一位二进制位同为 ，则加法后为 ，异或后为 ，将两者的差右移 ，得到 。我们可以通过这种办法得到 中均为 的位。因此 的结果就是两数中均为 的位。

同时，根据加法和异或的性质，两数同一位上的 和 可以互换。为了让 尽量小，我们令 即可，可以用 求出 。

注意数据范围，需要使用 unsigned long long。

代码

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
using namespace std;
typedef unsigned long long ll;
 
ll a, b, x, y;
 
int main() {
    scanf("%llu%llu", &a, &b);
    if(a < b || (a - b) & 1) return puts("-1"), 0;
    x = (a - b) / 2; y = a - x;
    printf("%llu %llu\n", x, y);
    return 0;
}