正题

题目链接:https://www.luogu.com.cn/problem/CF618F

题目大意

给出大小为\(n\)，值域为\([1,n]\)的两个可重集合\(A,B\)

需要你对它们各求出可重子集使得两个子集中的数字和相等

输出方案。

\(1\leq n\le 10^6\)

解题思路

这个值域范围就很提示性的往鸽笼原理方面考虑。

此题的结论就是一定有连续子序列的解。

先搞一个前缀和\(A,B\)，假设\(A_n\leq B_n\)。

现在我们要求两个\(l,r\)满足

\[A_{r_1}-A_{l_1}=B_{r_2}-B_{l_2}
\]

\[\Rightarrow A_{r_1}-B_{r_2}=A_{l_1}-B_{l_2}
\]

现在问题就变为了求两个相同的\(A_x-B_y\).

对于每个\(A_x\)（\(x\in[0,n]\)），求出一个最大的\(y\)使得\(B_y\leq A_x\)

那么显然有\(A_x-B_y\in[0,n-1]\)，也就是\(A_x-B_y\)一共只有\(n\)种取值，而我们有\(n+1\)个，所以至少有两个相同的。

开两个桶记录一下出现位置就好了。

时间复杂度\(O(n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=1e6+10;

ll n,a[N],b[N],la[N],lb[N];

signed main()

{

	scanf("%lld",&n);

	for(ll i=1;i<=n;i++)

		scanf("%lld",&a[i]),a[i]+=a[i-1];

	for(ll i=1;i<=n;i++)

		scanf("%lld",&b[i]),b[i]+=b[i-1];

	bool f=0;

	if(a[n]>b[n]){

		for(ll i=1;i<=n;i++)

			swap(a[i],b[i]);

		f=1;

	}

	ll ala,alb,ara,arb;

	for(ll i=0,j=0;i<=n;i++){

		while(b[j]<=a[i])j++;j--;

		if(la[a[i]-b[j]]){

			ala=la[a[i]-b[j]];

			alb=lb[a[i]-b[j]];

			ara=i;arb=j;

		}

		la[a[i]-b[j]]=i+1;

		lb[a[i]-b[j]]=j+1;

	}

	if(f)swap(ala,alb),swap(ara,arb);

	printf("%lld\n",ara-ala+1);

	for(ll i=ala;i<=ara;i++)printf("%lld ",i);

	printf("\n%lld\n",arb-alb+1);

	for(ll i=alb;i<=arb;i++)printf("%lld ",i);

	return 0;

}

巴特西

CF618F-Double Knapsack【结论】

正题

题目大意

解题思路

code

最新文章

热门文章