ARC122D XOR Game 题解

link 本题为原T1

黑板上有 $2n$ 个整数。
每轮：

1. Alice 选一个数 $x$ 擦掉；

2. Bob 选一个数 $y$ 擦掉；

3. 将 $x \oplus y$ 记在笔记本上。（是另一个地方！）

重复 $n$ 轮，笔记本上有 $n$ 个数，分数是它们的最大值。
Alice 想最大化分数，Bob 想最小化分数。双方最优策略下，求分数。

$1\leq n\leq 2\times10^5,0\leq A_i\leq 2^{30}$

---

这道题其实不是博弈论。

因为最后所有数都能一一配对。当 Alice 选择某一组的其中一个数时，Bob 一定可以选择对应的另外一个数。

所以 Alice 怎么选根本不重要，Bob 占据绝对主动，一定可以最小化答案。

（赛时居然只看出来了第一步 A 怎么选不重要，太菜了qaq）

那么这道题的本质是：给你 $2n$ 个数，问你如何两两配对，使每组数的异或的最大值最小。

异或这种东西吧，还是要按位考虑的。不要成天想着哪些位置反掉了，然后根据修改的更新。

我们从高位到低位考虑贪心，尽量使高位为零。

手玩可以发现，如果最高位所有的 $1$ 都可以在一起消掉，那么就可以使这些 $1$ 以特定的方式相消使得这一位结果为 $0$。

也就是说，如果 $1$ 的数量为偶数，就可以让下一位变为“最高位”了，即递归下去。

当然这里递归下去是要分为这一位是 $0$ 和 $1$ 两个集合递归。毕竟 $1$ 是只能与 $1$ 消的。

$\color{transparent}\tiny -$

那么如果 $1$ 的数量为奇数，就必然有一个 $1$ 无法找 $1$ 相消，它就使得结果在这一位上为 $1$。

由于其他 $1$ 都能消掉，在这一位上为 $0$，那么说，实际上其他 $1$ 是对结果没有影响的。直接以上面那玩意为结果就可以了。

考虑如何求出 $0$ 的集合与 $1$ 的集合相消的最小值。使用字典树即可。

那么这一位由于已经是最大值，就不用递归下去了。

最后答案取 $\max$ 即可。

int n;
ll a[maxn];
bitset<maxm> b[maxn];
vector<int> fullset;
void input(){
	n=read();
	for(int i=1;i<=2*n;++i){
		a[i]=read();
		b[i]=a[i];
		fullset.emplace_back(i);
		// cout<<b[i]<<endl;
	}
}

struct Trie{
	struct Node{
		int son[2];
		bool isend;
		Node(){}
		void clear(){isend=0;son[0]=son[1]=0;}
	}t[maxn*maxm];
	int idx;

	void insert(bitset<maxm> &s,int l,int r){
		int now=0;
		for(int i=l;i>=r;--i){
			int c=s[i];
			if(t[now].son[c]==0) t[now].son[c]=++idx;
			now=t[now].son[c];
		}
		t[now].isend=1;
	}
	ll query(bitset<maxm> &s,int l,int r){
		int now=0;
		ll res=0;
		for(int i=l;i>=r;--i){
			int c=s[i];
			if(t[now].son[c]==0){
				now=t[now].son[c^1];
				res+=_2[i-r];
			}
			else now=t[now].son[c];
		}
		return res;
	}
	void clear(){
		for(int i=0;i<=idx;++i) t[i].clear();
		idx=0;
	}
}trie;

ll ans;
void solve(vector<int> &s,int dep){
	if(dep<0) return;

	int cnt=0;
	for(auto p: s){
		if(b[p][dep]==1) ++cnt;
	}
	if(cnt%2==0){
		vector<int> p1,p0;
		for(auto p: s){
			if(b[p][dep]==1) p1.emplace_back(p);
			else p0.emplace_back(p);
		}
		if(p0.size()) solve(p0,dep-1);
		if(p1.size()) solve(p1,dep-1);
	}
	else{
		trie.clear();
		for(auto p: s){
			if(b[p][dep]==0){
				trie.insert(b[p],dep,0);
			}
		}
		ll res=inf;
		for(auto p: s){
			if(b[p][dep]==1){
				res=min(res,trie.query(b[p],dep,0));
			}
		}
		ans=max(ans,res);
	}
}

int main(){
	input();
	solve(fullset,30);
	printf("%lld\n",ans);
	return 0;
}

不给submission了（