题解：P13552 鱼类考古学

首先证明我们一定是先 $\otimes$ 再 $+$。

如果不是，那会有 $(a+b)\otimes c\le \max(a,b,c)$，而把 $\max(a,b,c)$ 和另外两个 $\otimes$ 的结果加起来肯定不劣。

那么我们从高位往低位贪心，记录此时 $\otimes$ 和 $+$ 的剩余次数 $r_0$ 和 $r_1$，以及这一位 $0$ 和 $1$ 的个数 $c_0$ 和 $c_1$。有 $r_0+r_1=c_0+c_1-1$。如果 $c_1\le r_1$，那么显然这一位为 $1$ 的东西应该全部加起来。否则有 $c_0\le r_0$，那么这一位为 $0$ 的东西应该全部 $\otimes$ 成一个数。手模一下发现这样做刚好可以符合高位对低位的限制，那么直接模拟即可。

代码乱写的，看看就好。

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define uint unsigned int
#define pii pair<int,int>
#define io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
inline int read(){
	int x=0;bool f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return f?x:-x;
}
int t,n,k,a[1000005],b[1000005];
int main(){
	io;
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++) cin>>a[i];
		int r0=n-k,r1=k-1;
		ll ans=0;
		int m=n;
		for(int i=29;~i;i--){
			int c0=0,c1=0;
			for(int j=1;j<=m;j++) c0+=(a[j]>>i&1)^1,c1+=(a[j]>>i&1);
			if(c0>r0){
				r1-=c1;
				int tot=0;
				for(int j=1;j<=m;j++)
					if(a[j]>>i&1)
						ans+=a[j];
					else b[++tot]=a[j];
				m=tot;
				for(int j=1;j<=m;j++) a[j]=b[j];
			}
			else{
				if(c0) r0-=c0-1;
				int tot=0,now=(1<<30)-1;
				for(int j=1;j<=m;j++)
					if(!((a[j]>>i)&1))
						now&=a[j];
					else b[++tot]=a[j];
				if(now<(1<<30)-1) b[++tot]=now;
				m=tot;
				for(int j=1;j<=m;j++) a[j]=b[j];
			}
		}
		int now=(r0?(1<<30)-1:0);
		for(int i=1;i<=(r0?r0+1:0);i++)
			now&=a[i];
		ans+=now;
		for(int i=(r0?r0+2:1);i<=m;i++)
			ans+=a[i];
		cout<<ans<<'\n';
	}
    return 0;
}