题解：AT_abc347_d [ABC347D] Popcount and XOR

zibenlun · 2024-03-31 09:37:49 · 题解

解决

题意

您将得到非负整数 a 、 b 和 C 。

确定是否有一对非负整数 (X, Y) 满足以下所有五个条件。如果存在这样的对，则打印一个。

• 0 \le X \lt 2^{60}
• 0 \leq Y \lt 2^{60}
• \operatorname{popcount}(X) = a
• \operatorname{popcount}(Y) = b
• X \oplus Y = C

思路

首先要满足 X \oplus Y = C 我们需要在把 C 转化成二进制后的所有位在 X 和 Y 中出现仅一次。那么 X 和 Y 的其余的位 只需要根据 a 和 b 的大小都选或者都不选即可。

细节

• 判断当 a 和 b 的位数减去构成 C 要用的位数后如果是奇数个，那么说明之后不能通过选取同一个位数相互抵消。

• 判断 a 和 b 能否用完，用不完也是不行的。

• 开 long long

代码

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define int_128 __int128
#define lowbit(x) (x&(-x))
using namespace std;
int a,b,c;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>a>>b>>c;
    int cnt=0;
    int x=c;
    while(x) {
        x-=lowbit(x);
        cnt++;
    }
    if(a+b<cnt || (a+b-cnt)%2==1) {
        cout<<-1;
    }
    else {
        int ans=0,anss=0;
        for(int i=0;i<=60;i++){
            if(c&(1ll<<i)){
                if(a>=b){
                    ans|=(1ll<<i);
                    a--;
                }
                else {
                    anss|=(1ll<<i);
                    b--;
                }
            }
        }
        for(int i=0;i<=60;i++){
            if((c&(1ll<<i)) == 0){
                if(a&&b){
                    a--;
                    b--;
                    ans|=(1ll<<i);
                    anss|=(1ll<<i);
                }
                else {
                    break;
                }
            }
        }
        if(a||b){
            cout<<-1;
        }
        else cout<<ans<<" "<<anss<<"\n";
    }
    return 0;
}