[ARC106E] Medals 题解

题意

有一个商店和 \(N\) 名员工，其中第 \(i\) 名员工在第 \(1 \sim A_i\) 天工作，在第 \(A_i + 1 \sim 2 \times A_i\) 休息，接下来每 \(A_i\) 天改变一次状态。

每一天你都可以选择一名来上班的员工并为其颁一个奖，求使得每名员工都获得至少 \(K\) 个奖的最小天数。

• \(1 \le N \le 18\)
• \(1 \le K \le 10^5\)
• \(1 \le A_i \le 10^5\)

题解

首先考虑二分答案。

现在问题转化为了判定在制定天数内是否可以使得每名员工都获得至少 \(K\) 个奖。

考虑转化为二分图模型，将员工视为左部点，天数视为右部点，那么判定成立当且仅当存在一个完美匹配使得每个员工都有 \(K\) 条边。

将原图中的每个员工拆为 \(K\) 个点，那么判定成立当且仅当对左部图存在一个完美匹配。

考虑应用 Hall 定理，发现对于一个员工拆出的 \(K\) 个点，由于与其联通的右部点集合均相同，故对全部 \(K\) 个点整体判定强于对部分点进行判定。因此需要判定的点集只有 \(2^N\) 个。

考虑如何判定，问题转化为了对于每个点集，求出与其联通的右部点点集大小。

可以发现一个性质，即对于每个点集，与其相邻的右部点数量不少于全体右部点数量的一半。因此可以得出答案上界为 \(2 \times N \times K\)。因此我们只需要对 \(\left[N \cdot K, 2 \times N \times K\right]\) 内的答案进行判定。

根据上述分析可以得出右部点数量是 \(\mathcal{O}(NK)\) 级别的，所以我们从右部点的角度来考虑。同样可以发现，对于右部点，与其联通的左部点集合之后 \(2^N\) 种，且可以进行预处理。

那么我们可以对于每个左部点集合 \(S\)，求有多少个右部点的联通集合与其有交，发现难于计算，转化为求有多少个个右部点的联通集合与其不交，发现其数量等于联通集合为 \(S\) 的点集的补集的右部点数量。这个是便于处理的，使用高维前缀和即可。

因此我们可以通过对于所有可能的右部点，处理出与其联通的左部点集合，这可以在 \(\mathcal{O}(N^2K)\) 的时间内完成。

接下来对于每次判定，对于每个点集 \(S\)，处理出恰好与这些左部点联通的右部点数量。接下来使用高维前缀和处理出对于每个点集 \(S\)，与左部点联通集合为其子集的右部点数量。最后枚举所有点集进行判定即可。这部分的复杂度为 \(\mathcal{O}(NK + N2^N)\)。

总复杂度为 \(\mathcal{O}\left(N^2K + \log NK \left(NK + N2^N\right)\right)\)，可以通过。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;

valueType popcount(valueType n) {
    return __builtin_popcount(n);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, K;

    std::cin >> N >> K;

    ValueVector A(N);

    for (auto &iter : A)
        std::cin >> iter;

    valueType const V = 2 * N * K, S = 1 << N, FULL = S - 1;

    ValueVector type(V + 1, 0);

    for (valueType i = 1; i <= V; ++i) {
        for (valueType j = 0; j < N; ++j)
            if ((i - 1) / A[j] % 2 == 0)
                type[i] |= 1 << j;
    }

    auto check = [&](valueType lim) -> bool {
        ValueVector F(S, 0);

        for (valueType i = 1; i <= lim; ++i)
            ++F[type[i]];

        for (valueType i = 0; i < N; ++i)
            for (valueType j = 0; j < S; ++j)
                if (j & (1 << i))
                    F[j] += F[j ^ (1 << i)];

        for (valueType i = 0; i < S; ++i)
            if (lim - F[FULL ^ i] < popcount(i) * K)
                return false;

        return true;
    };

    valueType left = 1, right = V, ans = V;

    while (left <= right) {
        valueType const mid = (left + right) / 2;

        if (check(mid)) {
            ans = mid;
            right = mid - 1;
        } else
            left = mid + 1;
    }

    std::cout << ans << std::endl;

    return 0;
}