XOR Partition

题目描述

For a set of integers $ S $ , let's define its cost as the minimum value of $ x \oplus y $ among all pairs of different integers from the set (here, $ \oplus $ denotes bitwise XOR). If there are less than two elements in the set, its cost is equal to $ 2^{30} $ .

You are given a set of integers $ {a_1, a_2, \dots, a_n} $ . You have to partition it into two sets $ S_1 $ and $ S_2 $ in such a way that every element of the given set belongs to exactly one of these two sets. The value of the partition is the minimum among the costs of $ S_1 $ and $ S_2 $ .

Find the partition with the maximum possible value.

输入格式

The first line contains $ n $ ( $ 2 \le n \le 200000 $ ) — the number of elements in the set.

The second line contains $ n $ distinct integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 0 \le a_i < 2^{30} $ ) — the elements of the set.

妙妙题。

二分出来 \(m\)，然后去看 \(a_i\oplus a_j<m\) 的所有 \(i,j\) 是不是组成二分图。明显要黑白染色。

如何知道一个数列中最小的 \(a_x\oplus a_y(x\ne y)\)？ 有两种方法，而这两种方法衍生出这题的两种做法。

1，字典树

这个东西可以用字典树求。

考虑用字典树优化暴力建图。在跑字典树的途中，向小于 \(m\) 的所有子树连边，会连 \(\log n\) 次。

但是我不能连向自己所在的节点。所以要前后缀加上可持久化字典树就可以了。复杂度 \(O(nlog^2n)\)，这是我考场上想到的方法，但是没写。

这题还有另一个单 log 的字典树做法。但没看懂

2

将 \(a\) 从小到大排序后 \(\min\limits_{i=1}^{n-1} a_i\oplus a_{i+1}\) 就是答案。因为异或存在性质：如果 \(x<y<z\)，则 \(\min(x\oplus y,y\oplus z)<x\oplus z\)

这里也一样,将 \(a\) 从小到大排序后，如果 \(a_i\oplus a_{i+j}<m(j\ge 4)\)，那么一定无解。考虑 $a_{i}\oplus a_{i+j} $ 的最高位，中间夹的这五个数可能是 \(\{0,0,0,0,1\},\{0,0,0,1,1\},\{0,0,1,1,1\},\{0,1,1,1,1\}\)，然后这五种都存在三元环。

考虑一个 \(a_i\)，我们只让他和 \(a_{i+1},a_{i+2},a_{i+3}\) 去连边。但是这样好像还是会有一个问题，如何证明这样连边合法的情况下，不存在连了后面的边后才会出现非法情况。但是这样做是能过的。希望有大佬可以给个证明或 hack。OI比赛中还是打 Trie 计算除了前三个是否存在 \(a_i\oplus a_j<m\) 或者打拍比较保险。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,a[N],col[N],fl,e_num,hd[N],l=1,r=(1<<30)-1,id[N],p[N];
struct edge{
	int v,nxt;
}e[N<<3];
void add_edge(int u,int v)
{
	e[++e_num]=(edge){v,hd[u]};
	hd[u]=e_num;
}
int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		s=s*10+ch-48,ch=getchar();
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s;
}
void dfs(int x)
{
	for(int i=hd[x];i;i=e[i].nxt)
	{
		if(!~col[e[i].v])
			col[e[i].v]=col[x]^1,dfs(e[i].v);
		else if(col[e[i].v]^1^col[x])
			fl=1;
	}
}
int ok(int x)
{
	memset(hd,e_num=fl=0,sizeof(hd));
	memset(col,-1,sizeof(col));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=3&&j+i<=n;j++)
			if((a[i]^a[i+j])<x)
				add_edge(i,i+j),add_edge(i+j,i);
	for(int i=1;i<=n;i++)
		if(!~col[i])
			col[i]=0,dfs(i);
	return fl^1;
}
int cmp(int x,int y)
{
	return a[x]<a[y];
}
int main()
{
	n=read();
	if(n==2)
		return puts("01"),0;
	for(int i=1;i<=n;i++)
		a[i]=read(),id[i]=i;
	sort(id+1,id+n+1,cmp);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		p[id[i]]=i;
	while(l<=r)
	{
		int md=l+r>>1;
		if(ok(md))
			l=md+1;
		else
			r=md-1;
	}
	ok(r);
	for(int i=1;i<=n;i++)
		putchar(col[p[i]]+48);
}