链接：
题目大意：
给你两个可重集 (a,b)，(a,b) 的元素个数都为 (n)，它们中每个元素的大小 (xin [1,n])。请你分别找出 (a, b) 的子集，使得它们中的元素之和相等。
正文：
这是一道非常牛逼的构造题。
设 (A,B) 分别为 (a,b) 的前缀和。猜想有解且一定连续。
若 (A_nleq B_n)，对于每个 (iin[1,n])，都能找到对应的 (jleq n) 使得 (B_jleq A_i,B_{j+1}>A_i)。也就是 (A_i<B_j+b_{j+1})，得到 (0leq A_i-B_j<n)，所以一共有 (n+1) 个 (A_i-B_j)。但又因为只有 (n) 个 (i)，鸽笼原理，必有 (A_{i_1}-B_{j_1}=A_{i_2}-B_{j_2})。(mathcal{O}(n)) 桶排即可。
代码:
const int N = 2e6 + 10;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n;
ll a[N], b[N];
ll bucket[N][2];
bool flag;
void Sol1(int i, int j)
{
printf ("%d
", i - bucket[a[i] - b[j]][0]);
for (int k = bucket[a[i] - b[j]][0] + 1; k <= i; k++)
printf ("%d ", k);
}
void Sol2(int i, int j)
{
printf ("%d
", j - bucket[a[i] - b[j]][1]);
for (int k = bucket[a[i] - b[j]][1] + 1; k <= j; k++)
printf ("%d ", k);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
memset (bucket, -1, sizeof bucket);
n = Read();
for (int i = 1; i <= n; i++) a[i] = Read() + a[i - 1];
for (int i = 1; i <= n; i++) b[i] = Read() + b[i - 1];
if (a[n] < b[n]) swap (a, b), flag = 1;
for (int i = 0, j = 0; i <= n; i++)
{
for (; b[j] <= a[i] && j <= n; j++);
j--;
if (~bucket[a[i] - b[j]][0])
{
if (flag) {Sol2(i, j); putchar(10); Sol1(i, j);}
else {Sol1(i, j); putchar(10); Sol2(i, j);}
break;
}
else bucket[a[i] - b[j]][0] = i, bucket[a[i] - b[j]][1] = j;
}
return 0;
}