問題#
いくつかの自然数 $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;
}