K · K-MEX：中文题面与个人代码

时限 1 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

数组的 $\operatorname{mex}$ 是没有出现的最小非负整数。例如 $\operatorname{mex}([4,0,2,1])=3$ ，负数不占据非负整数的位置。

给定长度为 $n$ 的数组 $a$ 。对于一个非负整数 $k$ ，可以对每个下标独立选择保留 $a_i$ 或改为 $k-a_i$ 。所有选择完成后的数组记为 $a'$ ，定义 $k$ - $\operatorname{mex}(a)$ 为所有可得 $a'$ 的最大 mex。

有 $q$ 次询问，每次给出 $k$ 。只需输出所有询问答案的按位异或值。各次询问都从原数组出发，重复询问也要重复计入异或。

输入、输出与约束 #

$1\le T\le10^3$ 。每组输入 $1\le n\le5\times10^3$ 、 $n$ 个 $0\le a_i\le10^9$ ，再输入 $1\le q\le5\times10^5$ ，随后 $q$ 行各给出 $0\le k\le10^9$ 。保证 $\sum n\le5\times10^3$ 、 $\sum q\le5\times10^5$ 。每组输出一个整数。

样例 #

输入 1 #

2
3
0 1 3
3
1
2
5
9
0 0 1 1 2 3 3 4 5
7
4
5
6
7
8
9
10

输出 1 #

3
8

样例说明 #

第一组数组 $[0,1,3]$ ，三个询问 $k=1,2,5$ 的最大 mex 分别为 $2,2,3$ ，异或得到 $3$ 。例如 $k=2$ 时，零与二都只能由原来的零这个位置提供，无法同时出现，所以最大 mex 是二；不能把所有候选值的并集当成可同时实现的数组。 $k=5$ 时可以把三变成二，得到 $[0,1,2]$ ，mex 为三。第二组七个询问的最终异或为八。

个人代码：按互补对分组，再分小 k 与大 k #

固定 $k$ 后，每个位置只能在 $x$ 和 $k-x$ 之间选择。不同无序互补对之间不共享候选值。对于同一对，只有一个位置时优先覆盖较小的非负数；有至少两个位置时可同时覆盖两端；两端相等时无论出现几次也只能覆盖一个值。由此，先填较小未出现值的贪心可以最大化连续前缀长度。

as[x] 预处理 $0\le x\le2n$ 时的答案。used 只需标记 $[0,n]$ ，因为长度为 $n$ 的数组 mex 不超过 $n$ 。内层每次优先选较小可用端点，其已出现时再尝试较大端点。数组中数值非负是索引检查成立的前提，变换得到的负数不能写进 used。

当 $k>2n$ 时，同一位置的两个候选值不可能同时落在 $[0,n]$ ：它们的和为 $k$ 。因此原来就在范围内的数可以保留；另外只需考虑 $a_i\in[k-n,k]$ ，它们变换后落入 $[0,n]$ ，不会与原本小数的选择相冲突。b 存原数组缺失的小数，l,r 在排序后的数组中找出这个窗口，临时标记 k-a[i]，再找 b 中第一个仍未覆盖的数。代码构造 b 时没标记原值 $n$ ，但这不影响答案：要到 mex 为 $n$ 才会查到它，此时 $n$ 个位置已经用来覆盖 $0,\ldots,n-1$ 。

询问排序后，mp[k] 缓存“答案加一”，避免答案零与未缓存混淆。相同询问仍参与异或，只省去重算。

小 $k$ 预处理 $O(n^2)$ 。大 $k$ 的不同询问中，每个 $a_i$ 只会在整数 $k\in[a_i,a_i+n]$ 的至多 $n+1$ 个窗口里出现，因此所有窗口扫描总计 $O(n^2)$ ；每次扫描缺失表时，成功越过的条目都可归因于当次窗口中的一个数，外加首次未覆盖项，合计 $O(n^2+q)$ 。算上排序与映射，时间 $O(n^2+q\log q)$ ，空间 $O(n+q)$ 。

本地结果： 样例通过；280 组长度一到八的小数组，对每个询问枚举全部 $2^n$ 种变换选择，异或答案与原稿一致，覆盖重复询问、 $k=0$ 、跨越 $2n$ 的分界和 $k=10^9$ 。这些是本地核验，赛中 K 通过的事实另由成绩材料支持。

原始 C++ 文件 #

下载 K.cpp · 验证说明

下面展示原稿，保留未完成部分和已发现问题；下载文件保留原始字节。SHA-256：f27b430785da1f7414e3b9aed362d95a95b66fb86e3d3d669b6cc2fd9b011958。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=5e5+10;
int T,n,k[M],q,ans,a[N],b[N],as[N<<1],used[N];
map<int,int>mp;
void solve()
{
	mp.clear();
	ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)scanf("%d",&k[i]);
	sort(k+1,k+q+1);
	for(int x=0;x<=2*n;x++)
	{
		memset(used,0,sizeof(int)*(n+5));
		for(int i=1;i<=n;i++)
		{
			if(a[i]<x-a[i])
			{
				if(a[i]<=n&&!used[a[i]])
				{
					used[a[i]]=1;
				}
				else if(x-a[i]<=n)used[x-a[i]]=1;
			}
			else
			{
				if(x-a[i]>=0&&x-a[i]<=n&&!used[x-a[i]])
				{
					used[x-a[i]]=1;
				}
				else if(a[i]<=n)used[a[i]]=1;
			}
		}
		int mex=0;
		for(int i=0;i<=n;i++)
			if(!used[i])
			{
				mex=i;
				break;
			}
		as[x]=mex;
	}
	sort(a+1,a+n+1);
	for(int i=0;i<=n;i++) used[i]=0;
	for(int i=1;i<=n;i++) if(a[i]<n) used[a[i]]=1;
	int m=0;
	for(int i=0;i<=n;i++) if(!used[i]) b[++m]=i;
	for(int i=0;i<=n;i++) used[i]=0;
	for(int t=1,l=1,r=0;t<=q;t++)
	{
		if(k[t]<=2*n)ans^=as[k[t]];
		else
		{
			if(mp[k[t]])
			{
				ans^=mp[k[t]]-1;
				continue;
			}
			while(r<n&&a[r+1]<=k[t])r++;
			while(l<=n&&a[l]<k[t]-n)l++;
			for(int i=l;i<=r;i++) used[k[t]-a[i]]=1;
			for(int i=1;i<=m;i++) 
				if(!used[b[i]])
				{
					mp[k[t]]=b[i]+1;
					ans^=b[i];
					break;
				}
			for(int i=l;i<=r;i++) used[k[t]-a[i]]=0;
		}
	}
	cout<<ans<<'\n';
	return;
}
int main()
{
//	freopen("K.in","r",stdin);
//	freopen("K.out","w",stdout);
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}