CF1790E题解

幻想繁星 · 2023-02-01 09:11:33 · 题解

题意

给定 x，求 a 和 b，使 a \oplus b=\frac{a+b}{2}=x。若有多个解输出任意一个即可。若无解输出 -1。

思路

我们可以先尝试打表，通过打表找到一些规律。

#include<bits/stdc++.h>
using namespace std;
inline long long read();
int main()
{
    for(int x=1;x<=1000;x++)
        for(int i=1;i<=x*2;i++)
            if((i^(x*2-i))==x)
            {
                cout<<x<<" "<<i<<" "<<(x*2-i)<<"\n";
                break;
            }
    return 0;
}

通过以上代码我们可以得到 1000 以内所有 x 的最小解。

结果如下：

传送

通过观察可发现若 x 有解则 a 最小为 \frac{x}{2}，此时 b=2x-a 即 b=\frac{3x}{2}。

所以只要判断 \frac{x}{2}\oplus\frac{3x}{2} 是否等于 x 并输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
inline long long read();
int main()
{
    int t=read();
    while(t--)
    {
        int x=read(),a=x/2,b=x*2-a;
        if((a^b)==x)
            cout<<a<<" "<<b<<"\n";
        else
            cout<<"-1\n";
    }
    return 0;
}

证明——2018ljw

令 a=0，b=x，对于二进制 x 的任意为 0 的位置 p，将 a，b 加上 2^p，异或不变，总和加上 2^{p+1}。

最终目标要使总和加上 x，可知 a，b 分别要加上 \frac{x}{2}。那么如果 x 与 \frac{x}{2} 某个位置均为 1 就无解，否则构造出的 a 即为最小。