CF618F Double Knapsack 题解

题目链接：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;
}