题目#
给定若干个自然数 $a_{1\sim n}$。
你需要选出其中一些数，然后将你选出的数划分为若干个集合。
你需要最大化每个集合 $\tt mex$ 的异或和，输出这个值。
一个集合的 ${\tt mex}$ 是指最小的不在这个集合中的自然数，例如 ${0,1,2,4,5}$ 的 ${\tt mex}$ 是 $3$，${1,2,3}$ 的 ${\tt mex}$ 是 $0$。
保证 $1\le n\le 10^6$，$0\le a_i\le n$。
题解#
首先可以判断出，如果一个集合的 $\text {mex}$ 为 $x$ 的话，那么这个集合一定要包含 $1$ 到 $x-1$，而对于x后面的数要不要都无所谓
所以我们可以先取出最大的 $\text {mex}$，即最长的连续数 + 1
然后，考虑剩下的数。如果 $y$ 能凑出来那么对于 $z <y$，$z$ 一定能够凑出，所以想让 $z \text {} xor\text { } ans$ 最大，从大向小考虑，如果 $z & ans=0$，那么就选出 $1$ 到 $z-1$。
考场上就与没想出来，-30pointsQAQ
代码#
实现的不好，应该是 $O (n^2)$ 的，实际可以做到 $O (n)$（但由于数据太水 n 方能过去）
#include<bits/stdc++.h>
using namespace std;
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = 10 * x + ch - '0';
ch = getchar();
}
return f * x;
}
const int N = 1e6 + 10;
int a[N], n;
int cnt[N];
int maxa = -1;
long long ans;
int main()
{
freopen("mexor.in", "r", stdin);
freopen("mexor.out", "w", stdout);
n = read();
for(int i = 1;i <= n;i++)
{
a[i] = read();
cnt[a[i]]++;
maxa = max(maxa, a[i]);
}
while(1)
{
int i = -1;
for(;i <= maxa;i++)
{
if(cnt[i + 1] == 0)
{
break;
}
}
if(i == -1) break;
if((ans & (i + 1)) == 0)
{
ans += i + 1;
for(int j = 0;j <= maxa;j++)
{
cnt[j] --;
}
}
else
{
cnt[i] = 0;
}
}
printf("%lld", ans);
return 0;
}