题解：CF1641D Two Arrays
题目描述
给定 \(n\) 个数组，第 \(i\) 个数组包含 \(m\) 个不同的整数—— \(a_{i,1}, a_{i,2},\ldots,a_{i,m}\)。同时给定一个长度为 \(n\) 的整数数组 \(w\)。
请你在所有满足条件的整数对 \((i, j)\)（\(1 \le i, j \le n\)）中，找到 \(w_i + w_j\) 的最小值，条件是 \(a_{i,1}, a_{i,2},\ldots,a_{i,m}, a_{j,1}, a_{j,2},\ldots,a_{j,m}\) 这 \(2m\) 个数两两不同。
输入格式
第一行包含两个整数 \(n\)、\(m\)（\(2 \leq n \leq 10^5\)，\(1 \le m \le 5\)）。
接下来的 \(n\) 行中，第 \(i\) 行首先给出 \(m\) 个不同的整数 \(a_{i,1}, a_{i,2}, \ldots, a_{i,m}\)，随后是 \(w_i\)（\(1\leq a_{i,j} \leq 10^9\)，\(1 \leq w_{i} \leq 10^9\)）。
随机化+高维前缀和
令 \(k=15\)，将每个数 \(p\) 映射到 \([0,k)\) 的整数 \(per_p\)，把它们压缩起来，求出 \(m(i)=\{per_p\mid p\in A_i\}\)。用高维前缀和求出 \(f(S)=\max_{m(i)\subseteq S}w_i\) 之类的东西，然后枚举 \(2^k\) 个 \(S\) 就可以计算了。据说随机 \(20\) 次可以通过。
Bitset
使用 bitset 求出 \(S_p=\{i\mid p\in A_i\}\)。对于每个 \(i\) 都求出 \(\bigcup_{p\in A_i}S_p\) 的补集中最小的元素（使用 _Find_first，为此需要预先对 \(w\) 排序）。记 \(m\) 为所有 \(A_i\) 大小的和，则时间复杂度 \(O(nm/w)\)。
但是空间开不下。根号分治，大小 \(<B\) 的 \(S_p\) 用 vector 直接存，否则才用 bitset 存。则时间复杂度（不用分析，只要 \(B\leq n/w\)，时间复杂度就不会变），空间复杂度 \(O(m+mn/wB)\)，所以直接取 \(B=n/w\) 就是最优空间复杂度 \(O(m)\)（反正就是过了。为什么和题解不一样？到底是怎样的，想不清楚了）。
容斥+Trie+栈
判断两个数组是否有重复元素，假如数组长度很小 \(\leq k\)，那么计算 \(\sum_{S\subseteq A}\sum_{T\subseteq B}[S=T](-1)^{|S|-1}\)，如果 \(A\) 和 \(B\) 有交就是 \(0\)，否则就是 \(1\)（二项式定理）。现在就可以判断一个数组是否和另一个数组有交了。
从小到大扫描，维护一个栈。当栈中存在数组和当前扫到的数组无交时，将数组弹栈，并尝试统计贡献。扫描完一个数组后，将该数组入栈。不难发现这样是最优的（和 CF1285F Classical? 题解 - 洛谷专栏有点像）。
为了维护那个容斥式子，使用 Trie 树即可。复杂度 \(O(n2^k)\)。
做法 1 代码
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <class T>
struct flower {vector<T> vec;flower& operator<<(const T& x) { vec.push_back(x); return *this; }int build() {auto bg = vec.begin(), ed = vec.end();sort(bg, ed);vec.erase(unique(bg, ed), ed);return (int)vec.size();}int operator()(const T& x) const { return (int)(lower_bound(vec.begin(), vec.end(), x) - vec.begin()); }
};
constexpr int N = 1e5 + 10, M = N * 5;
int n, m;
struct node2 {int w;vector<int> vec;
} a[N];
mt19937 rng{3412341};
flower<int> hua;
int main() {
#ifndef LOCALcin.tie(nullptr)->sync_with_stdio(false);
#endifcin >> n >> m;for (int i = 1; i <= n; i++) {a[i].vec.resize(m);for (int j = 0; j < m; j++) cin >> a[i].vec[j], hua << a[i].vec[j];cin >> a[i].w;}m = hua.build();for (int i = 1; i <= n; i++) {for (int &x : a[i].vec) x = hua(x);}constexpr int k = 15;static int p[M], f[1 << k];int ans = numeric_limits<int>::max();for (int t = 0; t < 100; t++) {for (int i = 0; i < m; i++) p[i] = rng() % k;memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i++) {int S = 0;for (int x : a[i].vec) S |= 1 << p[x];f[S] = min(f[S], a[i].w);}for (int j = 0; j < k; j++) {for (int S = 0; S < 1 << k; S++) if (S >> j & 1) f[S] = min(f[S], f[S ^ (1 << j)]);}for (int S = 0; S < 1 << k; S++) if (max(f[S], f[(1 << k) - S - 1]) <= 1e9) {ans = min(ans, f[S] + f[(1 << k) - S - 1]);}}cout << (ans == numeric_limits<int>::max() ? -1 : ans) << endl;return 0;
}
做法 2 代码
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
constexpr int N = 1e5 + 10, M = N * 5, B = 1560;
int n, m, tot;
bitset<N> bs[M / B + 10];
struct node {vector<int> vec;int id = -1;void push_back(int x) {if (id == -1) {vec.push_back(x);if (vec.size() >= B) {for (int y : exchange(vec, {})) bs[tot][y] = true;id = tot++;}} else {bs[id][x] = true;}}void merge_into(bitset<N>& dst) {if (id == -1) {for (int y : vec) dst[y] = true;} else {dst |= bs[id];}}
};
map<int, node> mp;
struct node2 {int w;vector<int> vec;
} a[N];
int main() {
#ifndef LOCALcin.tie(nullptr)->sync_with_stdio(false);
#endifcin >> n >> m;for (int i = 1; i <= n; i++) {a[i].vec.resize(m);for (int j = 0; j < m; j++) cin >> a[i].vec[j];cin >> a[i].w;}sort(a + 1, a + n + 1, [&](auto&& lhs, auto&& rhs) { return lhs.w < rhs.w; });for (int i = 1; i <= n; i++) {for (int x : a[i].vec) mp[x].push_back(i);}bitset<N> b;int ans = numeric_limits<int>::max();for (int i = 1; i <= n; i++) {b.reset(), b[0] = true;for (int x : a[i].vec) mp[x].merge_into(b);int j = (~b)._Find_first();debug("i = %d, j = %d\n", i, j);if (j <= n) ans = min(ans, a[i].w + a[j].w);}cout << (ans == numeric_limits<int>::max() ? -1 : ans) << endl;return 0;
}