题目#

给定若干个自然数 $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方能过去）

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
int read()
6
{
7
  int f = 1, x = 0;
8
  char ch = getchar();
9
  while(ch < '0' || ch > '9')
10
  {
11
    if(ch == '-') f = -1;
12
    ch = getchar();
13
  }
14

15
  while(ch >= '0' && ch <= '9')
16
  {
17
    x = 10 * x + ch - '0';
18
    ch = getchar();
19
  }
20
  return f * x;
21
}
22

23
const int N = 1e6 + 10;
24
int a[N], n;
25
int cnt[N];
26
int maxa = -1;
27

28
long long ans;
29
int main()
30
{
31
  freopen("mexor.in", "r", stdin);
32
  freopen("mexor.out", "w", stdout);
33
  n = read();
34

35
  for(int i = 1;i <= n;i++)
36
  {
37
    a[i] = read();
38
    cnt[a[i]]++;
39
    maxa = max(maxa, a[i]);
40
  }
41
  while(1)
42
  {
43
    int i = -1;
44
    for(;i <= maxa;i++)
45
    {
46
      if(cnt[i + 1] == 0)
47
      {
48
        break;
49
      }
50
    }
51
    if(i == -1) break;
52
    if((ans & (i + 1)) == 0)
53
    {
54
      ans += i + 1;
55
      for(int j = 0;j <= maxa;j++)
56
      {
57
        cnt[j] --;
58
      }
59
    }
60
    else
61
    {
62
      cnt[i] = 0;
63
    }
64
  }
65

66
  printf("%lld", ans);
67

68
  return 0;
69
}

Mexor

https://blog.histcat.top/posts/mexor/

作者

Histcat

发布于

2023-10-01

许可协议

CC BY-NC-SA 4.0

小葱拿糖

Wbtree