§ Desc.

Link.

你有 $n$ 个朋友，他们会来你家玩，第 $i$ 个人 $1...A_i$ 天来玩，然后 $A_i+1...2A_i$ 天不来，然后 $2A_i+1...3A_i$ 又会来，以此类推;

每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。

你要给每个人都颁 $K$ 个奖，问至少需要多少天。

§ Sol.

前面的部分很套路了，主要看看建出二分图后我们应该做什么。首先根据 Hall's marriage theorem，我们要做的是判断任意子集的邻域大小是否大于等于该子集的大小。把 $n$ 个人拆成 $n\times k$ 个点，可以发现进行判断时不需要把同一类点（由同一个工人拆出来的 $k$ 个点）分开。设 $f(S)$ 为满足存在集合 $S$ 中任一工人会来打工的天数，则有解的一个充要条件为 $\forall S\subseteq 2^{\{1,\dots,n\}},m-f(U\setminus S) \geqslant |S|\times k$。

const int N = 18, K = 1e5;
int n, k, a[N + 5], f[2 * N * K + 5], g[1 << N];
bool check(int upp) {
    const int LIM = 1 << n, U = LIM - 1;
    for (int i=0;i<LIM;++i) g[i] = 0;
    rep (i,1,upp) g[f[i]]++;
    for (int j=0;j<n;++j) for (int i=0;i<LIM;++i) if (!(i&(1<<j))) g[i|(1<<j)] += g[i];
    for (int i=0;i<LIM;++i) if (upp - g[U^i] < __builtin_popcount(i) * k) return false;
    return true;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    rd(n, k); rds0i(a, n);
    for (int i=0;i<n;++i) {
        for (int t=0;;t+=2) for (int j=t*a[i]+1;j<(t+1)*a[i]+1;++j) {
            if (j > 2 * n * k) goto label;
            f[j] |= 1<<i;
        }
        label:;
    }
    int l = 0, r = 2 * n * k, res = -1;
    while (l <= r) {
        if (int mid = (l + r) / 2; check(mid)) r = mid - 1, res = mid;
        else l = mid + 1;
    }
    cout << res << "\n";
}