题解：P13995 【MX-X19-T4】「FeOI Round 4.5」Supernova

nsp · 2025-09-08 14:16:49 · 题解

还是被同学拉着做的题。

显然无论怎么操作 x 都是递增的。

在进行过一次 1 操作后无论如何操作，p 所含有的 1 的集合都一定会是 x 所含 1 的集合的子集。设已经进行过 1 次 1 操作，则 x 在做 +1 操作时，p 上连续的 1 段都一定会被进位，所以可以把 x 上 p 的这一位为 1 的位删去，剩下的位都往低位推，可以理解成从高到低遍历 p 的位，如果 p 的第 i 位为 1 则 x 的最高位到第 i+1 位都右移一位。也可以这样写代码把 x 转化成 a：

#define ll long long
ll a = 0,base = 1;
for(int i = 0;i <= 62;++i){
    if(!((p>>i)&1)){
        if((x>>i)&1)a |= base;
        base <<= 1;
    }
}

将数字这样转化之后还能得到另一个便利：2 操作对 x 的值增加的贡献一定低于 1 操作。

对 y 也做一遍如上的操作得到 b 最后计算一下 b-a 得到差就行了。

另外要注意分讨第一步做 2 操作和特判无解。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 1000010
#define INF 0x3f3f3f3f3f3f3f3fll
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define cpx complex<double>
#define poly vector<ll>
int T;
ll x,y,p,ans,a;

ll solve(ll from){
    ll b = 0;
    ll base = 1;
    for(int i = 0;i <= 62;++i){
        if(!((p>>i)&1)){
            if((from>>i)&1)b |= base;// 把 y 搬运到 a 上
            base <<= 1;
        }
    }
    if(a<b)return LLONG_MAX-100;
    return a-b;
}

// 主函数
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> T;
    while(T--){
        cin >> x >> y >> p;
        if(y == x){cout << "0\n";continue;}
        if(y == (x | (p+1))){cout << "1\n";continue;}
        if((y&p) != p || y < x){cout << "-1\n";continue;}
        a = 0;
        // 对 y 做
        ll base = 1;
        for(int i = 0;i <= 62;++i){
            if(!((p>>i)&1)){
                if((y>>i)&1)a |= base;// 把 y 搬运到 a 上
                base <<= 1;
            }
        }
        ll val = min(solve((x+1)|p)+1,solve((x|p+1)+1|p)+2);
        if(val > LLONG_MAX-100)cout << "-1\n";
        else cout << val << '\n';
    }
    return 0;
}