给你两个可重集 , 的元素个数都为 ,它们中每个元素的大小 。请你分别找出 的一个子集和 B$ 的一个子集,使得它们中的元素之和相等。输出方案。
。
直接考虑子序列是做不了的,那么不妨加强限制,考虑子段。
发现值域是序列的长度 ,这启发我们想到抽屉原理。设 和 是两个序列的前缀和,不妨假设 ,设 表示最大的满足 的 ,那么总有 或者 。后者移项得 ,而 的情况则由于 所以有 。由于 的最大值为 ,所以总有 。
注意到只要找到一个四元组 ,满足 且 则 和 就是一个合法的解。而 共有 种取值, 却有 种取值,所以总能找到两对相等的 。并且由于 互不相同,所以这两对的 也互不相同,所以找出来的是合法的解。
那么用个桶记录每个 对应的 即可,时间复杂度 。
代码如下:
#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;
}