題目#
給定若干個自然數 $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;
}