感觉这题远没有蓝，如果放在T1肯定人均过。

做法

考虑什么时候取 a[i]^x 枚举 x 的最高位。然后看 x 的每一位取 1 相较取0 产生的贡献，扔到优先队列里面，取前 k 大的，注意如果取到某一位，这一位的贡献为负，就不要继续取了。

复杂度为 $\Theta(m^2n+mk\log m)$

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e>'9'||e<'0') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e^'0');
		e=getchar();
	}
	return x*y;
}
int n,m,k,a[100005];
int mx,ans;
signed main() {
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
	R(n),R(m),R(k);
	for(int i=1; i<=n; ++i) {
		R(a[i]);
		mx+=a[i];
	}
	if(!k){
		cout<<"0\n";return 0;
	}
	for(int h=0; h<m; ++h) {
		// the highest 1
		int x=(1ll<<h),res=0;
		int pf[31]= {0};
		priority_queue<pair<int,int> >q;
		for(int i=1; i<=n; ++i) {
			if(!(a[i]>>h&1)) {
				for(int j=0; j<h; ++j) {
					if(a[i]>>j&1)pf[j]-=(1ll<<j);
					else pf[j]+=(1ll<<j);
				}
			}
		}
		for(int j=0; j<h; ++j) {
			q.push({pf[j],j});
		}
		for(int i=1;i<k&&!q.empty();++i){
			int u=q.top().second;
			q.pop();
			if(pf[u]<=0)break;
			x|=(1ll<<u);
		}
		for(int i=1;i<=n;++i){
			res+=max(a[i],a[i]^x);
		}
		if(res>mx){
			mx=res,ans=x;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

鉴定为清新小蓝题，但是我写的很狗屎。

主要我的思路是一开始乱糊，然后胡这胡这就真了，所以代码非常难看（不过好像是实验最优解）。

这里只写一下思路。

首先这个 $MAX$ 看上去就很烦人，不过我们先不搭理它，我们可以先考虑直接贪心

我们考虑最高位，发现如果我们最高位放了1，那么所有最高位是1的数我们都可以扔掉不管了，因为异或了以后肯定没有原数大。

当然如果最高位都是1，我们就看下一位。

以此类推，直到找到某一位，使得存在一个数，它在这一位上是0

剩下的就是，我们还有 $k-1$ 个1可以放置，然后要最大化异或 $X$ 的和的基础上最小化 $X$

我一开始想要延续贪心的路线，发现一位能放，当且仅当这一位上0的个数比1多，但是这么贪非常错，这就好比是01背包你写贪心，不过我一开始没多想，交上去直接 95 分，但是注意到出题人绑包了，所以这个做法绝对假完了

前面已经说了，这本质上就是个01背包，我们做一下背包，顺便记录个方案就好了。

为了让这篇题解看起来更反胃，我要把我的狗屎代码放上来

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int s;int n,m,k;
int B;
int solve(int bit,int l,int r,int k,bool qdl){
	if(!bit){
		return 0;
	}
	int ok=0;
	for(int i=r; i>=l; i--){
		if(((1<<bit-1)&a[i])==0){
			ok++;
		}
	}
	if(qdl){
		if(ok){
			s|=(1<<bit-1);
			B=bit;
			return ok;
		}else{
			return solve(bit-1,l,r,k,qdl);
		}
	}
}
long long gongxian[33];
long long f[33][33],g[33][33];
int main(){
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	if(!k){
		printf("0");
		return 0;
	}
	for(int i=1;i <=n; i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);int len=solve(m,1,n,k,1);
	for(int j=B-1; j>=1; j--){
		int ok=0;
		for(int i=1; i<=len; i++)if(((1<<j-1)&a[i])==0)ok++;
		if(ok*2>len)gongxian[j]=(1<<j-1)*1ll*(ok*2-len);
	}long long mx=0;
//	cout<<len<<endl;	
//	cout<<B<<endl;
	if(!B){
		printf("0");
		return 0;
	}
	for(int i=1; i<=B-1; i++){
		for(int j=1; j<=k-1; j++){
			f[i][j]=max(f[i-1][j],f[i-1][j-1]+gongxian[i]);
//			cout<<f[i][j]<<endl;
			mx=max(f[i][j],mx);
		}
	}memset(g,0x7f,sizeof g);
	for(int i=0; i<=B-1; i++)g[i][0]=0;
	long long res=1000000000000000000;
	for(int i=1; i<=B-1; i++){
		for(int j=1; j<=k-1; j++){
			if(f[i-1][j-1]+gongxian[i]==f[i][j])g[i][j]=min(g[i][j],g[i-1][j-1]|(1<<i-1));
			if(f[i-1][j]==f[i][j])g[i][j]=min(g[i][j],g[i-1][j]);
			if(f[i][j]==mx)res=min(res,g[i][j]);
		}
	}if(res>(1<<m))res=0;
	cout<<(res|(1<<B-1));
	return 0;
}/*

*/ 

感谢观猴