histcat

Problem#

Given several natural numbers $a_{1\sim n}$.

You need to select some of these numbers and then divide the selected numbers into several sets.

You need to maximize the XOR sum of the $\tt mex$ of each set and output this value.

The ${\tt mex}$ of a set refers to the smallest natural number not in this set; for example, the ${\tt mex}$ of ${0,1,2,4,5}$ is $3$, and the ${\tt mex}$ of ${1,2,3}$ is $0$.

It is guaranteed that $1\le n\le 10^6$, $0\le a_i\le n$.

Solution#

First, it can be determined that if the $\text{mex}$ of a set is $x$, then this set must contain $1$ to $x-1$, and it doesn't matter whether to include the numbers after x.

So we can first extract the largest $\text{mex}$, which is the longest consecutive number + 1.

Then, consider the remaining numbers. If $y$ can be formed, then for $z < y$, $z$ can definitely be formed, so to maximize $z \text{ }xor\text{ } ans$, we consider from large to small. If $z & ans=0$, then select from $1$ to $z-1$.

I couldn't think of this during the exam, -30pointsQAQ

Code#

The implementation is not good; it should be $O(n^2)$, but it can actually be done in $O(n)$ (but due to the data being too trivial, it can only pass in quadratic time).

#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;
}