[二分图] [状压] [SOSdp] [ARC106E] Medals

_Cheems · 2024-07-16 16:14:39 · 题解

首先二分答案，暴力拆点跑二分图最大匹配，不行会超时，需要优化。

尝试使用 \rm Hall 定理，暴力枚举人集合 S，现在的问题是怎么求与 S 相连的奖牌集合大小。

注意到一个重要性质：我们依次给每个人颁奖，那么总天数为 2nk。这是答案上界，也就是说天数并不多。

这启示我们从奖牌出发考虑贡献，记 P_i 表示可以获得第 i 天的奖牌的人的集合，那么 P_i 对 S 有贡献，当且仅当 P_i\cap S\ne \varnothing。

但是这并不好计算，不妨换个角度，计算 P_i\cap S=\varnothing 的数目，等价于 P_i\in \bar{S}。非常简洁优美，直接高维前缀和预处理即可。

注意二分前预处理 P_i 避免超时。复杂度 O(n2^n\log nk+n^2k)。

代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

const int N = 25, M = 4e6 + 5, MX = 1 << 18;
int n, k, a[N], P[M], f[MX], ppc[MX]; 

inline bool check(int p){
    for(int i = 0; i < MX; ++i) f[i] = 0;
    for(int i = 1; i <= p; ++i) ++f[P[i]];
    for(int i = 0; i < n; ++i)
        for(int S = 0; S < 1 << n; ++S)
            if((S >> i) & 1) f[S] += f[S ^ (1 << i)];
    for(int S = 1; S < 1 << n; ++S){
        int res = p - f[((1 << n) - 1) ^ S];
        if(ppc[S] * k > res) return false;
    }
    return true;
}
signed main(){
    for(int i = 1; i < MX; ++i) ppc[i] = ppc[i ^ (i & -i)] + 1;
    cin >> n >> k;
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= 2 * n * k; ++i)
        for(int j = 0; j < n; ++j){
            int id = i % (2 * a[j]);
            if(id && id <= a[j]) P[i] |= (1 << j); 
        }
    int L = 0, R = 2 * n * k;
    while(L + 1 < R){
        int mid = L + R >> 1;
        if(check(mid)) R = mid;
        else L = mid;
    }
    cout << R; 
    return 0;
}