CF1849F

Linxrain的博客 / 2023-08-26 / 原文

问题链接

这里说一种非常简单的单\(log\)方法

显然地，如果在某二进制位上，有一些数字是\(0\)，另一些是\(1\)，那么我们考虑尽量地将这一位相同的数字分到不同的集合中，那么可以建一张图，图上相邻的点不在同一集合内

我们不妨从最高位向最低位考虑，假设初始状态中，所有的数字都在同一个组中。每当同一组中的的数字在这一位同时出现了\(1\)和\(0\)时，我们据此将它分成两组，这个过程形似\(01\)字典树

我们反复地进行这个操作，当所有的组中最多都只有两个数字时，意味着最小值最大时当前位为\(1\)，那么我们便把所有在同一组但不在同一连通块中的数字连边，并回退此次分组操作

最后\(DFS\)跑一遍图即可，可以发现这张图最后会是一个森林，总复杂度\(nlog\)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<int>>s,t;
vector<int>emp,e[2000005];
int a[2000005],ans[2000005],f[200005];
bool vis[2000005];
int find(int x){
    return f[x]==x?x:find(f[x]);
}
void dfs(int x,int now){
    if(vis[x])return;
    vis[x]=1;
    ans[x]=now;
    for(auto u:e[x])
        dfs(u,now^1);
}
void solve(){
    int n,mx;
    scanf("%d",&n);
    s.push_back(emp);
    mx=n;
    for(int i=1;i<=n;i++){
        f[i]=i;
        s[0].push_back(i);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=30;i>=0;i--){
        t.clear();mx=0;
        int now=1<<i;
        for(auto j:s){
            int flag=1;
            for(auto k:j)
                if(a[k]&now){
                    if(flag)t.push_back(emp);
                    t.back().push_back(k);
                    flag=0;
                }
            flag=1;
            for(auto k:j)
                if(!(a[k]&now)){
                    if(flag)t.push_back(emp);
                    t.back().push_back(k);
                    flag=0;
                }
        }
        for(auto i:t)
            mx=max(mx,(int)i.size());
        swap(s,t);
        if(mx<=2){
            for(auto i:s)
                if(i.size()==2){
                    int f1=find(i[0]),f0=find(i[1]);
                    if(f0==f1)continue;
                    f[f1]=f0;
                    e[i[0]].push_back(i[1]);
                    e[i[1]].push_back(i[0]);
                }
            swap(s,t);
        }
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs(i,1);
    for(int i=1;i<=n;i++)
        printf("%d",ans[i]);
}
int main(){
    int t=1;
    //scanf("%d",&t);
    while(t--)solve();
    return 0;
}