Codeforces Round 773 div.2 F

F. Two Arrays

题意：给出 \(n\) 个数组，每个数组都有 \(m\) 个不同元素，有权值 \(w_i\)，我们称两个不包含相同元素的数组是匹配的，要求匹配的数组对当中， \(w_i+w_j\) 的最小值（\(n\le10^5,m\le5,a_i\le10^9\)）

奇技淫巧：

哈希，我们可以把 \(w\) 映射到一个很小的范围上去（比如1000以内），可能会产生冲突，但要导致最终结果出错，当前仅当作为答案选取的两个数组 \(i,j\) 中的至多10个不同元素映射产生了冲突，可以估计，产生冲突的概率是很小的。

这样我们就将 \(w\) 的值域压缩到了一个很小的范围。

这个冲突概率大概是1%左右，为了避免运气不好，可以卡个时多次跑，取最小ans

解法一：

首先考虑bitset的 \(n^2\) 暴力

先将所有数组按照 \(w\) 排序

对每个权值，用bitset记录它在哪些数组上出现过

然后暴力枚举每个数组，把它的元素出现过的位置或起来

然后取最早的从未出现的位置，更新答案。

复杂度 \(O(n^2m/64)\)，值域压缩后，空间复杂度 \(10000\times n\)（）

struct node{
    int v[6];
    int w;
}a[maxn];
bitset<maxn> t[13335], p;
 
int n, m;
void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> a[i].v[j];
            a[i].v[j] %= 13335;
        }
        cin >> a[i].w;
    }
    sort(a+1, a+n+1, [](node x, node y){ return x.w < y.w;});
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) t[a[i].v[j]][i-1] = true;
 
    ll ans = 1e18;
    for(int i=1;i<=n;i++){
        p = 0;
        for(int j=1;j<=m;j++) p |= t[a[i].v[j]];
        int pos = 1 + (~p)._Find_first();
        if(pos < i && pos > 0) ans = min(ans, 1ll * a[pos].w + a[i].w);
    }
    
    if(ans > (ll)1e17) ans = -1;
    cout << ans << '\n';
}

解法二：

同样压缩值域，狠一点直接压缩到20

这样我们就可以用一个int来表示一个数组

然后问题就转换为了：有 \(n\) 个数对： \(a_i,w_i\) ，要求一个数对 \(i,j\)，满足 \(a_i\&a_j\) 为0，使 \(w_i+wj\) 最大

然后似乎可以SOSDP？

解法三（正解）：

如果要无概率呢？

我们需要一个东西来快速判断一段区间内有无数组能和一个新数组匹配

考虑两个数组 \(a,b\)，如何判断它们能否匹配，当然可以简单地扫一遍，但这不能扩展

先说结论：我们把 \(a\) 的所有子集都存进一个set，然后对于 \(b\) 的每个子集，如果它在 \(a\) 中出现过：

• 如果这个子集有奇数个元素，记1
• 如果这个子集有偶数个元素，记-1

可以预想，假设 \(a\) 与 \(b\) 共有 \(k\) 个相同元素，它们重复的子集个数则有 \(2^k\) 个，去掉空集，奇数子集将比偶数子集多一个。

那么这么计数得到的结果一定是1，除非 \(a\) 与 \(b\) 完全不同，结果才为0

这样下来，如果我们要拿 \(b\) 和 \(a_1,a_2...a_t\) 这 \(t\) 个数组匹配，就只需要把这 \(m\) 个数组的所有子集加入集合（不去重），然后再拿 \(b\) 去按上述方式计数，如果 \(b\) 和所有 \(a\) 都无法匹配，计数结果即为 \(t\)

不过如果这里我们用mutiset的话，复杂度为 \(O(n\times2^m\times log(n\times2^m))\) ，有点难以接受，可以用字典树来统计每个集合出现了多少次。

最后的解法：

先将数组们按照 \(w\) 排序，然后用双指针 \(l,r\)，先不断将 \(r\) 右移，找到第一个可以和前 \(r-1\) 个数匹配的位置，然后将 \(l\) 从这个 \(r\) 的位置不断左移，直到 \(r\) 不能再和前 \(l\) 个数组匹配为止。

这样我们就找到了第一组解，因为 \(w\) 是排序好的，后续 \(l\) 不需要再向右移动，右移 \(r\) 的过程中发现前 \(l\) 个数组与 \(r\) 不匹配了，就将 \(l\) 左移，然后更新答案。

namespace Tire{
    struct tire{
        map<int, int> ch;
        int num;
    }t[3200020];
    int cnt = 0;
    void insert(vector<int> &arr, int ad){
        int p = 0;
        for(int v:arr){
            if(!t[p].ch.count(v)) t[p].ch[v] = ++cnt;
            p = t[p].ch[v];
        }
        t[p].num += ad;
    }
    int query(vector<int> &arr){
        int p = 0;
        for(int v:arr){
            if(!t[p].ch.count(v)) return 0;
            p = t[p].ch[v];
        }
        return t[p].num;
    }
}
 
int n, m;
struct node{
    vector<int> v;
    int w;
}a[maxn];
 
vector<int> csd;
void add(int p, vector<int> &arr, int ad){
    if(p >= arr.size()){
        if(csd.empty()) return;
        if(ad > 0) Tire::insert(csd, 1);
        else Tire::insert(csd, -1);
        return;
    }
    add(p+1, arr, ad);
    csd.push_back(arr[p]);
    add(p+1, arr, ad);
    csd.pop_back();
}
 
int calcu(int p, vector<int> &arr){
    if(p >= arr.size()) return Tire::query(csd) * ((csd.size() % 2) ? 1 : -1);
    int res = 0;
    res += calcu(p+1, arr);
    csd.push_back(arr[p]);
    res += calcu(p+1, arr);
    csd.pop_back();
    return res;
}
 
void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        a[i].v.resize(m);
        for(int j=1;j<=m;j++){
            cin >> a[i].v[j-1];
        }
        sort(a[i].v.begin(), a[i].v.end());
        cin >> a[i].w;
    }
    sort(a+1, a+n+1, [](node &x, node &y){ return x.w < y.w;});
    int l, r = n + 1, ans = 2e9 + 1;
 
    for(int i=1;i<=n;i++){
        if(calcu(0, a[i].v) == i-1){
            add(0, a[i].v, 1);
        }else{
            l = i-1, r = i+1;
            while(calcu(0, a[i].v) != l){
                add(0, a[l].v, -1);
                ans = min(ans, a[i].w + a[l].w);
                l--;
            }
            break;
        }
    }
 
    for(int i=r;i<=n && l>0;i++){
        if(calcu(0, a[i].v) != l){
            while(l > 0 && calcu(0, a[i].v) != l){
                add(0, a[l].v, -1);
                ans = min(ans, a[i].w + a[l].w);
                l--;
            }
        }
    }
    if(ans > (int)2e9) ans = -1;
    cout << ans << '\n';
}