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

不难发现第

2

次操作至多进行

1

次，因为在进行了

1

操作以后相同的操作可以用一次

1

操作替代。此时我们如果需要进行

2

操作，当且仅当第一次进行

2

操作更优且不会超过

y

。如果不进行

2

操作，我们进行一次

1

操作，使得

p

成为

x

的子集。

然后我们考虑

1

操作的本质：考虑其补集，进行一次

1

操作相当于枚举子集，因此我们只要算出来

x

和

y

补集在

p

补集的子集中的顺序然后相减再加

1

就可以了，而计算顺序也很简单，对二进制拆分后的每个

2^n

找一下子集中比自己小的数然后加起来就可以。时间复杂度

O(T\log n)

。（还有就是，这题怎么评上蓝的？）

CPP

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
#define INF (1ull<<63)-1
#define bp __builtin_popcountll
using namespace std;

int t,x,y,p,maxn=INF;

signed main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>x>>y>>p;
        if(x==y){
            cout<<0<<"\n";continue;
        }
        if((x|(p+1))==y||((x+1)|p)==y){
            cout<<1<<"\n";continue;
        }
        int num=1,nxt=(x|(p+1));
        if(nxt>((x+1)|p)&&(nxt&p)==p&&nxt<=y)x=nxt;
        else x=(x+1)|p;
        if(x==y){
            cout<<1<<"\n";continue;
        }
        if(y<x||(y&p)!=p){
            cout<<-1<<"\n";continue;
        }
        int nx=(maxn^x),ny=(maxn^y);p=(maxn^p);
        int ax=0,ay=0;
        for(int i=0;i<=62;i++){
            if(nx&(1ll<<i)){
                int k=((1ull<<i)-1)&p;
                ax+=(1ull<<bp(k));
                //cout<<k<<" "<<bp(k)<<" "<<ax<<"\n";
            }
        }
        for(int i=0;i<=62;i++){
            if(ny&(1ll<<i)){
                int k=((1ull<<i)-1)&p;
                ay+=(1ull<<bp(k));
                //cout<<k<<" "<<ay<<"\n";
            }
        }
        //cout<<ax<<" "<<ay<<" ";
        cout<<ax-ay+1ll<<"\n";
    }
}

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

文章操作

相关推荐

评论

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