CF1849F

· · 题解

Solution

有趣的题目，昨晚写了个 O(n \log^2 V) 的做法，但是人傻常数大过不去。在末尾我稍微提一下吧。感谢这条评论给我的启发。

考虑异或最基本的一个性质：如果 a<b<c 那么 a \oplus c > \min\{a \oplus b,b \oplus c\}，因此一个集合两两异或的最小值为相邻两数异或的最小值，我们不妨把原序列排个序。

很容易想到二分答案之后对于所有 a_i \oplus a_j < m 的 (i,j) 连边，然后判定是不是二分图。但是这样边的数量会达到 O(n^2) ，难以接受。不过很容易发现，如果三个数之间两两连边，那么肯定有奇环，这是不合法的。而且，如果第一个数和最后一个数有连边，这样说明限制非常严，那不合法十之八九对不对。

我们证明一个引理：如果 x 和 x+4 有连边，那么一定不合法。

证明：考虑 a_x \oplus a_{x+4} 的最高位。然后我们把 a 的这几位拿出来看。显然的，比这一位高的位在 [x,x+4] 上都是相同的，所以可以把它们忽略。

那么单独考虑这一位，只可能是 \{0,1,1,1,1\} 或 \{0,0,1,1,1\} 或 \{0,0,0,1,1\} 或 \{0,0,0,0,1\} 四种情况。很容易发现，对于前两种情况，后三个数两两异或的这一位都是 0；对于后两种情况，前三个数两两异或的这一位都是 0。因为 x 和 x+4 已经有连边了，所以这些异或是 0 的肯定都能连边，那么必定存在为长度是 3 的环，肯定无解。

那么显然，对于 x+5 及以后的肯定还是如此。因此，只要我们连的边跨度不超过 3，如果判断出来有解，就不会有跨度很大的边，那么实际图的形态保持不变，正确；如果无解，那么实际图只会有更多的边，一定无解。

因此只有 O(3n) 条有用的边。那么就可以二分答案了。

我的做法是在二分答案后用 Trie 树优化建图，这样最多 O(n \log V) 条边，但是常数太大过不去 /ll

代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=200000+10;
int n,a[MAXN],b[MAXN],rev[MAXN],col[MAXN],tmp; vector<int> G[MAXN]; 
void dfs(int u,int c) {
    if(col[u]!=-1) return tmp&=(col[u]==c),void();
    col[u]=c; for(auto v:G[u]) dfs(v,c^1);
    return ;
}
int solve(int m) {
    tmp=1,memset(col,-1,sizeof(col)); ffor(i,1,n) G[i].clear();
    ffor(i,1,n) ffor(j,i+1,min(n,i+3)) if((b[i]^b[j])<m) G[i].push_back(j),G[j].push_back(i);
    ffor(i,1,n) if(col[i]==-1) dfs(i,1);
    return tmp;
}
int bfind(int l,int r) {
    int ans=-1,mid;
    while(l<=r) {
        mid=l+r>>1;
        if(solve(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n; ffor(i,1,n) cin>>a[i];
    vector<pair<int,int>> vc; ffor(i,1,n) vc.push_back({a[i],i});
    sort(vc.begin(),vc.end());
    ffor(i,1,n) b[i]=vc[i-1].first,rev[vc[i-1].second]=i;
    if(n==2) return cout<<10,0;
    int ans=bfind(0,(1<<30)-1),h=solve(ans);
    ffor(i,1,n) cout<<col[rev[i]];
    return 0;
}