CodeForces 618F Double Knapsack

Posted on By 二价氢

题目大意

给定两个多重集,集合里的元素大小都小于等于,求的子集,使得这两个子集的元素和相等

做法

奈何鸽笼原理都能玩出花来……

将集合变成数列,考虑A的前缀和,存在B的一个最大的前缀和使得,注意到,即只有n个取值,但若考虑0,我们有n+1个取值,因而由于鸽笼原理,一定存在,使得

(于是-1例行卖萌)

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 2;
long long a[maxn], b[maxn];
int jb[maxn], d[maxn], f[maxn];
int n;
int main() {
	ios::sync_with_stdio(0);
	memset(f, -1, sizeof(f));
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		b[i] += b[i - 1];
	}
	b[n + 1] = 0x3f3f3f3f3f3f3f3fll;
	int cr = 0;
	for (int i = 0; i <= n; i++) {
		while (b[cr + 1] <= a[i]) cr++;
		jb[i] = cr;
		d[i] = a[i] - b[cr];
	}
	for (int i = 0; i <= n; i++) {
		int &tp = f[d[i]];
		if (tp == -1) {
			tp = i;
		} else {
			cout << i - tp << endl;
			for (int j = tp + 1; j <= i; j++)
				cout << j << ' ';
			cout << endl << jb[i] - jb[tp] << endl;
			for (int j = jb[tp] + 1; j <= jb[i]; j++)
				cout << j << ' ';
			cout << endl;
			break;
		}
	}
	return 0;
}