专栏文章

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

nnsp
P13995题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minz0yc7
此快照首次捕获于
2025/12/02 10:40
3 个月前
此快照最后确认于
2025/12/02 10:40
3 个月前
查看原文
还是被同学拉着做的题。
显然无论怎么操作 xx 都是递增的。
在进行过一次 1 操作后无论如何操作，pp 所含有的 11 的集合都一定会是 xx 所含 11 的集合的子集。设已经进行过 1 次 1 操作，则 xx 在做 +1+1 操作时，pp 上连续的 11 段都一定会被进位，所以可以把 xx 上 pp 的这一位为 11 的位删去，剩下的位都往低位推，可以理解成从高到低遍历 pp 的位，如果 pp 的第 ii 位为 11 则 xx 的最高位到第 i+1i+1 位都右移一位。也可以这样写代码把 xx 转化成 aa：
CPP
#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 操作对 xx 的值增加的贡献一定低于 1 操作。
对 yy 也做一遍如上的操作得到 bb 最后计算一下 b−ab-a 得到差就行了。
另外要注意分讨第一步做 2 操作和特判无解。
CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...