Title
Given n(n<=2e5) different numbers, the i-th number ai(0<=ai<
Need to divide n numbers into two sets S1 and S2
The cost cost(S) of a set S:
①If there is only one number in the set, the cost is
②Otherwise, it is the smallest 
Maximize min(cost(S1), cost(S2)), and output the corresponding plan
That is, it is necessary to output a string of 01 with a length of n, 0 means that the selected number is in the A set, and 1 means that the selected number is in the B set
Source of ideas
Fucking AC & amp; Official Solution
Problem Solution 1 (Complete Graph Minimum XOR Spanning Tree)
Conclusion
(i, j) The cost of connecting edges is a[i]^a[j], and the minimum spanning tree is found for the complete graph of n points.
The black and white coloring of the minimum spanning tree is the solution,
The first one will cause the minimum spanning tree to generate an odd cycle, so the edge weight not added to the minimum spanning tree is the maximum value
proof
Inductively, considering that part of the minimum spanning tree has been obtained,
Since each time of merging, the two connected components are merged with the current minimum cost, which is equivalent to the increasing order of edge weights
Therefore, when merging two connected components (u, v), set the edge weight as w,
The meaning of connecting edges is to make u and v mutually exclusive in two sets
① If (u, v) is not in the same connected component, merge, and temporarily avoid w appearing in the final answer once, greedy
②If (u, v) is in the same connected component, examine the number of points between (u, v) on the tree (including the endpoint)
(1) If it is an odd number, it means that u and v are already in the same set,
Connecting the mutually exclusive edge of w will cause a strange cycle,
In order to maintain the legitimacy of the bipartite graph, it cannot be connected,
The w that happens for the first time is the minimum value that is maximized
(2) If it is an even number, it means that u and v are already in different sets,
Even the mutually exclusive side of w will not affect the answer, because it will not be counted in the answer
The board was copied in 20 years when I was playing Niuke and many schools. I feel that boruvka is only commonly used on the minimum spanning tree such as the trie tree.
The minimum spanning tree is obtained by recursively merging the trie tree. When merging, the edges are taken from the two leaves.
Complexity O(n*logn*logV)
Code 1 (boruvka on the trie tree, Niuke multi-school board)
#include <bits/stdc++.h>
//#include <iostream>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,ll> P;
const int N=2e5 + 10,M=30*N;
int n,u,v,w,a[N],tr[M][2],id[M],c;
char ans[N];
vector<int>e[N];
bool vis[N];
void dfs(int u,int w){
ans[u]=w + '0';
vis[u]=1;
for(auto &v:e[u]){
if(vis[v])continue;
dfs(v,w^1);
}
}
void ins(int v, int y){
int rt=0;
for(int j=29;j>=0;--j){
int x=v>>j &1;
if(!tr[rt][x]){
tr[rt][x] = + + c;
tr[c][0]=tr[c][1]=id[c]=0;
}
rt=tr[rt][x];
}
id[rt]=y;
}
P unite(int x,int y,int d){
if(d==0){
return P(a[id[x]]^a[id[y]],1ll*id[x]*N + id[y]);
}
P res=P(1<<30,0);
bool zero=0;
for(int i=0;i<2; + + i){
if(tr[x][i] & amp; & amp; tr[y][i]){
res=min(res,unite(tr[x][i],tr[y][i],d-1));
zero=1;
}
}
if(!zero){
if(tr[x][0] & amp; & amp; tr[y][1]){
res=min(res,unite(tr[x][0],tr[y][1],d-1));
}
else if(tr[x][1] & amp; & amp; tr[y][0]){
res=min(res,unite(tr[x][1],tr[y][0],d-1));
}
}
return res;
}
void cal(int u,int d){
int ls=tr[u][0],rs=tr[u][1];
if(ls)cal(ls,d-1);
if(rs)cal(rs,d-1);
if(ls & amp; & amp; rs){
P x = unite(ls,rs,d-1);
int y=x.se/N,z=x.se%N;
e[y].pb(z);
e[z].pb(y);
}
}
int main(){
scanf("%d", &n);
for(int i=1;i<=n; + + i){
scanf("%d", &a[i]);
ins(a[i],i);
}
for(int i=1;i<=n; + + i){
ins(a[i],i);
}
cal(0,30);
for(int i=1;i<=n; + + i){
if(!vis[i])dfs(i,1);
}
ans[n + 1]='\0';
printf("%s\\
",ans + 1);
return 0;
}
Code 2 (standard boruvka, official solution)
It can be regarded as a copy of the orthodox writing of boruvka, not limited to the trie tree
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); + + i)
typedef long long LL;
typedef pair<int, int> PII;
const int N = 200000;
const int NODES = 32 * N;
const int INF = int(2e9);
int n;
int a[N];
int nx[NODES][2], cnt[NODES], fn[NODES];
int nodeCount = 1;
void addInt(int x, int pos) {
int ind = 0;
for (int i = 29; i >= 0; --i) {
int bit = (x >> i) & 1;
if (nx[ind][bit] == 0) {
nx[ind][bit] = nodeCount++;
}
ind = nx[ind][bit];
+ + cnt[ind];
}
fn[ind] = pos;
}
void addInt(int x) {
int ind = 0;
for (int i = 29; i >= 0; --i) {
int bit = (x >> i) & 1;
ind = nx[ind][bit];
+ + cnt[ind];
}
}
void removeInt(int x) {
int ind = 0;
for (int i = 29; i >= 0; --i) {
int bit = (x >> i) & 1;
ind = nx[ind][bit];
--cnt[ind];
}
}
PII findXor(int x) {
int ind = 0, res = 0;
for (int i = 29; i >= 0; --i) {
int bit = (x >> i) & 1;
if (cnt[nx[ind][bit]]) {
ind = nx[ind][bit];
} else {
ind = nx[ind][bit^1];
res |= 1 << i;
}
}
return mp(res, fn[ind]);
}
int par[200000], ra[200000];
void dsuInit() {
forn(i, n) par[i] = i, ra[i] = 1;
}
int dsuParent(int v) {
if (v == par[v]) return v;
return par[v] = dsuParent(par[v]);
}
int dsuMerge(int u, int v) {
u = dsuParent(u);
v = dsuParent(v);
if (u == v) return 0;
if (ra[u] < ra[v]) swap(u, v);
par[v] = u;
ra[u] + = ra[v];
return 1;
}
vector<int> v[200000];
vector<pair<int, PII> > toMerge;
vector<int> g[200000];
int color[200000];
void coloring(int x, int c){
if(color[x] != -1) return;
color[x] = c;
for(auto y : g[x]) coloring(y, c ^ 1);
}
int main() {
scanf("%d", &n);
forn(i, n) scanf("%d", a + i);
forn(i, n) addInt(a[i], i);
dsuInit();
for (int merges = 0; merges < n - 1; ) {
forn(i, n) v[i].clear();
forn(i, n) v[dsuParent(i)].pb(i);
toMerge. clear();
forn(i, n) if (!v[i].empty()) {
for (int x : v[i]) {
removeInt(a[x]);
}
pair<pair<int, int>, int> res = mp(mp(INF, INF), INF);
for (int x : v[i]) {
res = min(res, mp(findXor(a[x]), x));
}
toMerge.pb(mp(res.first.first, mp(res.second, res.first.second)));
for (int x : v[i]) {
addInt(a[x]);
}
}
for (auto p : toMerge) {
if (dsuMerge(p. second. first, p. second. second)) {
+ + merges;
g[p.second.first].pb(p.second.second);
g[p.second.second].pb(p.second.first);
}
}
}
forn(i, n) color[i] = -1;
coloring(0, 1);
forn(i, n) printf("%d", color[i]);
puts("");
return 0;
}
Problem solution 2 (bipartite + bipartite graph judgment)
1. Maximize the minimum value, first consider the dichotomy, dichotomy answer v, connect the value of (a[p]^a[i])<=v
Indicates that the point pair (p,i) cannot appear in the same set,
If the graph after connecting the edges is a bipartite graph, it can be bipartite to the big bipartite graph, otherwise it can be bipartite to the small bipartite graph
The final solution, since it is a bipartite graph, can be output after black and white coloring
2. When connecting edges, go down the trie tree. For the current value a[i],
Satisfying (a[p]^a[i])<=v, on the same node of the trie tree, can only have one value
Contradictory method: If there are two, the XOR of the two of them will also <=v, forming a three-membered ring and resulting in no solution
Therefore, when traversing from the high bit to the low bit, when traversing to the jth bit,
According to (v is 0/1 at the jth position, a[i] is 0/1 at the jth position), decide to go to 0/1 in the next step, so as not to exceed v
Each step is unique, and each point has at most logV edges
3. It is necessary to judge n=2, that is, there is no edge
Complexity O(n*logn*logV*α(n))
Code 3 (binary + trie + greedy + bipartite graph judgment, my mess)
#include <bits/stdc++.h>
//#include <iostream>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b); + + i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a. size())
#define sci(a) scanf("%d", &(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\\
",a)
#define ptlle(a) printf("%lld\\
",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5 + 10,M=31*N;
int n,a[N],tr[M][2],num[M],par[N*2],c=1;
char ans[N];
vector<int>vec[M],e[N];
bool vis[N];
void dfs(int u,int w){
ans[u]=w + '0';
vis[u]=1;
for(auto &v:e[u]){
if(vis[v])continue;
//printf("u:%d v:%d w:%d\\
",u,v,w);
dfs(v,w^1);
}
}
void ins(int v, int i){
int rt=0;
for(int j=29;j>=0;--j){
int x=v>>j &1;
if(!tr[rt][x]){
tr[rt][x] = + + c;
tr[c][0]=tr[c][1]=num[rt]=0;
}
rt=tr[rt][x];
num[rt] + + ;
if(num[rt]<=2)vec[rt].pb(i);
}
}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
void add(int x,int y){
x=find(x),y=find(y);
if(x==y) return;
par[y]=x;
}
void XOR(int x,int y){
e[x].pb(y);
e[y].pb(x);
add(x,y + n);
add(x + n,y);
}
// To satisfy (a[p]^a[i])<=v (p,i) are connected to the mutually exclusive edge
// (v>>j & amp;1,a[i]>>j & amp;1,a[p]>>j & amp;1)
bool ck(int i,int v){
int rt=0;
for(int j=29;j>=0;--j){
int x=a[i]>>j & amp;1,z=v>>j & amp;1,nex=tr[rt][x],oth=tr[rt][x^1];
//printf("i:%d v:%d j:%d x:%d z:%d nex:%d oth:%d\\
",i,v,j,x,z,nex,oth) ;
if(!z)rt=nex;//(0,x,x)
else {
// Discuss in 3, 2, 1, and discuss whether you are currently in x or not
if(num[nex]>=3) return 0;//3 pairs of mutual exclusion must be sent
int cnt=0,p=-1;
for(auto &w:vec[nex]){
if(w==i)continue;
cnt + + ;
if(cnt>=2) return 0;//3 pairs of mutual exclusion must be sent
p=w;
}
if(cnt){
//printf("XOR v:%d i:%d p:%d\\
",v,i,p);
XOR(i,p);
}
rt=oth;
}
if(!rt)break;
}
return 1;
}
bool ok(int x){
rep(i,1,2*n){
if(i<=n)e[i].clear();
par[i]=i;
}
rep(i,1,n){
if(!ck(i,x)) return 0;
}
rep(i,1,n){
if(find(i)==find(i + n)) return 0;
}
return 1;
}
void sol(){
if(n==2){
puts("10");
return;
}
int l=0,r=(1<<30)-1;
while(l<=r){
int mid=l + (r-l)/2;
if(ok(mid))l=mid + 1;
else r=mid-1;
}
//printf("r:%d\\
",r);
ok(r);//ans=l
rep(i,1,n){
if(!vis[i]){
dfs(i,1);
}
}
ans[n + 1]='\0';
printf("%s\\
",ans + 1);
}
int main(){
sci(n);
rep(i,1,n){
sci(a[i]);
ins(a[i],i);
}
sol();
return 0;
}
//7421 6530