题目大意
给定两个多重集\(A\)和\(B\)，\(\mathrm{Size(A)} = \mathrm{Size(B)} = n\)，集合里的元素大小都小于等于\(n\)，求\(A\)和\(B\)的子集，使得这两个子集的元素和相等
做法
奈何鸽笼原理都能玩出花来……
将集合变成数列，考虑A的前缀和\(Prefix_i\)，存在B的一个最大的前缀和使得\(Prefix_j' \le Prefix_i\)，注意到\(Prefix_i - Prefix_j' \in [0, n - 1]\)，即只有n个取值，但若考虑0，我们有n+1个取值，因而由于鸽笼原理，一定存在\(i_1,j_1\)与\(i_2,j_2\)，使得\(Prefix_{i_1} - Prefix_{j_1}' = Prefix_{i_2} - Prefix_{j_2}'\)
即\(Prefix_{i_2} - Prefix_{i_1} = Prefix_{j_2}' - Prefix_{j_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;
}