题解：P17750 「RSOI-2C」异或 / xor

firefly_szy · 2026-11-12 22:25:17 · 题解

何意味题。

思路

对着这个建边条件思考，不难发现：u 和 v 两点之间可以建边，当且仅当 a_u 和 a_v 在二进制下的位数不同。

考虑如何证明这个东西。如果 a_u 和 a_v 的位数相同，那么它们的最高位在同一位且都为 1，异或之后这一位没了，必定有 a_u \oplus a_v < \min(a_u,a_v)。不符合建边条件，所以刚才那个结论是对的。

显然只需要有一个 a_i 与其他的位数不同就可以连一张连通图出来，那么只需要对所有数的位数都相同的情况进行处理。

记 w_i 为 a_i 在二进制下的位数。

枚举每个数，尝试把它位数变大或变小一位，也就是取 \min_{i}(a_i-(2^{w-1}-1),\ 2^{w}-a_i) 的最小值。

在尝试减小位数时注意特判 w_i=0 的情况。

做完了。

代码

::::success[code]

// code by Umbrella.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define pb push_back
#define mkp make_pair
namespace Umbrella{
    int n,a[1000005];
    int w[1000005];
    inline void solve(){
        cin>>n;
        int f=0;
        rep(i,1,n){
            cin>>a[i];
            int tot=0,now=a[i];
            while(now){
                ++tot,now>>=1;
            }
            w[i]=tot;
            if(i>1&&w[i]!=w[i-1]) f=1;
        }
        if(f||n==1) return cout<<0,void();
        int mi=1e18;
        rep(i,1,n){
            mi=min({mi,(1LL<<w[i])-a[i],a[i]-(1LL<<(w[i]?w[i]-1:0))+1});
        }
        cout<<mi;
    }
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int _T=1;
//  cin>>_T;
    while(_T--){
        Umbrella::solve();
    }
    return 0;
}

::::