CF618F Double Knapsack 做题记录

给你两个可重集 $A, B$，$A, B$ 的元素个数都为 $n$，它们中每个元素的大小 $x\in [1,n]$。请你分别找出 $A$ 的一个子集和 B$ 的一个子集，使得它们中的元素之和相等。输出方案。

$1\le n\leq 10^6$。

直接考虑子序列是做不了的，那么不妨加强限制，考虑子段。

发现值域是序列的长度 $n$，这启发我们想到抽屉原理。设 $sa$ 和 $sb$ 是两个序列的前缀和，不妨假设 $sa_n\le sb_n$，设 $pos_i$ 表示最大的满足 $sb_x\le sa_i$ 的 $x$，那么总有 $pos_i=n$ 或者 $sb_{pos_i+1}-sa_i>0$。后者移项得 $sa_i-sb_{pos_i}<b_{pos_i+1}$，而 $pos_i=n$ 的情况则由于 $sa_n<sb_n$ 所以有 $sa_i-sb_{pos_i}=0$。由于 $b_{pos_i+1}$ 的最大值为 $n$，所以总有 $sa_i-sb_{pos_i}<n$。

注意到只要找到一个四元组 $(l1,r1,l2,r2)$，满足 $0\le l1<r1\le n,0\le l2<r2\le n$ 且 $a_{l1}-b_{l2}=a_{r1}-b_{r2}$ 则 $[l1+1,r1]$ 和 $[l2+1,r2]$ 就是一个合法的解。而 $sa_i-sb_{pos_i}$ 共有 $n$ 种取值，$i$ 却有 $n+1$ 种取值，所以总能找到两对相等的 $sa_i-sb_{pos_i}$。并且由于 $sa_i$ 互不相同，所以这两对的 $pos_i$ 也互不相同，所以找出来的是合法的解。

那么用个桶记录每个 $sa_i-sb_{pos_i}$ 对应的 $i$ 即可，时间复杂度 $O(n)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=1000005;

int n;
bool flg;
int a[S],b[S];
long long sa[S],sb[S];
int pos[S],val[S];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
	{
		sa[i]=sa[i-1]+a[i];
		sb[i]=sb[i-1]+b[i];
	}
	if(sa[n]>sb[n])
	{
		flg=true;
		swap(a,b);
		swap(sa,sb);
	}
	for(int i=0;i<=n;i++)
	{
		if(i>0) pos[i]=pos[i-1];
		while(pos[i]<n&&sb[pos[i]+1]<=sa[i]) pos[i]++;
		val[i]=-1;
	}
	int l1=-1,r1=-1,l2=-1,r2=-1;
	for(int i=0;i<=n;i++)
	{
		int pre=sa[i]-sb[pos[i]];
 		if(val[pre]!=-1)
 		{
 			if(!flg)
 			{
 				l1=val[pre],r1=i;
 				l2=pos[val[pre]],r2=pos[i];
 			}
 			else
 			{
 				l1=pos[val[pre]],r1=pos[i];
 				l2=val[pre],r2=i;
 			}
 		}
		else val[pre]=i;
	}
	if(l1>r1) swap(l1,r1);
	if(l2>r2) swap(l2,r2);
	l1++,l2++;
	printf("%d\n",r1-l1+1);
	for(int i=l1;i<=r1;i++) printf("%d ",i);
	printf("\n%d\n",r2-l2+1);
	for(int i=l2;i<=r2;i++) printf("%d ",i);
	return 0;
}