CF618F Double Knapsack 做题记录

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

1n1061\le n\leq 10^6

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

发现值域是序列的长度 nn,这启发我们想到抽屉原理。设 sasasbsb 是两个序列的前缀和,不妨假设 sansbnsa_n\le sb_n,设 posipos_i 表示最大的满足 sbxsaisb_x\le sa_ixx,那么总有 posi=npos_i=n 或者 sbposi+1sai>0sb_{pos_i+1}-sa_i>0。后者移项得 saisbposi<bposi+1sa_i-sb_{pos_i}<b_{pos_i+1},而 posi=npos_i=n 的情况则由于 san<sbnsa_n<sb_n 所以有 saisbposi=0sa_i-sb_{pos_i}=0。由于 bposi+1b_{pos_i+1} 的最大值为 nn,所以总有 saisbposi<nsa_i-sb_{pos_i}<n

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

那么用个桶记录每个 saisbposisa_i-sb_{pos_i} 对应的 ii 即可,时间复杂度 O(n)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;
}