[构造] Codeforces 618F Wunder Fund Round 2016 F. Double Knapsack

给定两个大小为n的可重集A, B ，两个数集中的元素均为[1, n]的整数。
现在要求在两个数集中各找出一个非空子集(子集也为可重集) ，满足两个集合中元素的和相等。
n<=10^6

加限制使得选的为两个连续的段。
不妨设SA<=SB，记SA的前缀和为SA(0),SA(1),SA(2),…, SB的前缀和为SB(0),SB(1),SB(2),…
对于每个SA(i)，找到最大的SB(j)满足SA(i)>=SB(j)，这样可以得到n+1个SA(i)-SB(j)，然而每个都是在0到n-1之间。
所以至少有两个是一样的。
于是SA(i)-SB(j)=SA(p)-SB(q)，即SA(i)-SA(p)=SB(j)-SB(q)。

#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair<int,int> abcd;inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){char c=nc(),b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}const int N=1000005;int n,a[N],b[N];
ll sa[N],sb[N];
int match[N];
int pos[N];inline void print(int l,int r){if (l>r) swap(l,r);printf("%d\n",r-l);for (int i=l+1;i<=r;i++)printf("%d ",i);printf("\n");
}int main(){int flag=0;freopen("t.in","r",stdin);freopen("t.out","w",stdout);read(n);for (int i=1;i<=n;i++) read(a[i]),sa[i]=sa[i-1]+a[i];for (int i=1;i<=n;i++) read(b[i]),sb[i]=sb[i-1]+b[i];if (sa[n]>sb[n]){flag=1;for (int i=1;i<=n;i++) swap(a[i],b[i]),swap(sa[i],sb[i]);}sort(sb,sb+n+1);for (int i=0;ipos[i]=-1;for (int i=0;i<=n;i++){int it=upper_bound(sb,sb+n+1,sa[i])-sb-1;match[i]=it;if (~pos[sa[i]-sb[it]]){int t=pos[sa[i]-sb[it]];if (!flag)print(t,i),print(match[t],match[i]);elseprint(match[t],match[i]),print(t,i);    return 0;}elsepos[sa[i]-sb[it]]=i;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！