CF618F Double Knapsack 题解

题意：

给你两个可重集 \(A, B\)，\(A, B\) 的元素个数都为 \(n\)，它们中每个元素的大小 \(x\in [1,n]\)。请你分别找出 \(A, B\) 的子集，使得它们中的元素之和相等。

\(n\leq 10^6\)。

~~什么神仙构造题~~ 姑且认为是打表找规律的构造题吧

结论：一定有解，并且存在连续子序列（子段）的解。

这里的连续子序列甚至不用排序，就是 \(A,B\) 任意排列中的某个连续子序列

证明：（鸽巢原理）

设 \(A_i = \sum_{j=1}^{i}a_j,B_i=\sum_{j=1}^{i}b_j\) ，并定义 \(A_0 = B_0=0\)

不失一般性¹，我们假设 \(A_n \le B_n\) 。

定义 \(f : \mathbb{N} \to \mathbb{N}\) ， \(f(i)~(0\le i \le n)\) 表示满足 \(A_i \ge B_{f(i)}\) 的最大整数，显然 \(0\le f(i) \le n\) 。

由于 \(A_i < B_{f(i)+1}\) ，则 \[ A_i < B_{f(i)} + b_{f(i)+1} \]

移项得 \[ A_i -B_{f(i)} < b_{f(i)+1} \] 因为 \(1\le b_{f(i)+1} \le n\) ，所以 \[ 0 \le A_i - B_{f(i)} < n \] 则 \(A_i - B_{f(i)}\) 有 \(n\) 种取值，而 \(0\le i \le n\) ，即 \(i\) 有 \(n+1\) 种取值

根据鸽巢原理，可知至少有两个 \(A_i - B_{f(i)}\) 是相等的。

这意味着，存在 \(l_1<r_1\) 满足 \[ A_{l_1} - B_{f(l_1)} = A_{r_1} - B_{f(r_1)} \] 记 \(l_2=f(l_1),r_2=f(r_1)\) ，移项可得 \[ A_{r_1}-A_{l_1}=B_{r_2}-B_{l_2} \] 故结论成立。

那么怎么求出 \(f(i)\) 呢，显然这个 \(f(i)\) 是单调不降的，于是直接维护一个指针就好了

然后我们用个桶，边跑边记录每个 \(A_i - B_{f(i)}\) 对应的 \(i\) 和 \(f(i)\)

直到碰到一个 \(A_i -B_{f(i)}\) ，之前出现过了，就输出答案。

注意要单独开个数组判断 \(A_i - B_{f(i)}\) ，因为 \(i\) 可以为 \(0\) 。

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

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e6+15))

bitset<N> vis;
int n,l1,l2,r1,r2,flag,a[N],b[N],l[N][2];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    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];
    if(a[n] > b[n]) {flag = 1; for(int i=1; i<=n; i++) swap(a[i], b[i]);}
    for(int i=0,j=0; i<=n; i++)
    {
        while(a[i] >= b[j] && j<=n) ++j; --j;
        if(vis[a[i]-b[j]])
        {
            l1 = l[a[i]-b[j]][0] + 1;
            l2 = l[a[i]-b[j]][1] + 1;
            r1=i; r2=j; break;
        }
        l[a[i]-b[j]][0] = i; l[a[i]-b[j]][1] = j;
        vis[a[i]-b[j]] = 1;
    }
    if(flag) {swap(l1,l2); swap(r1,r2);}
    cout << r1 - l1 + 1 << '\n';
    for(int i=l1; i<=r1; i++) cout << i << " \n"[i==r1];
    cout << r2 - l2 + 1 << '\n';
    for(int i=l2; i<=r2; i++) cout << i << " \n"[i==r2];
    return 0;
}