天才和疯子互相为邻

「ARC106E」Medals

发表于 分类于

$Link$

有 $n$ 个人，第 $i$ 个人从第一天开始连续上 $a_i$ 天班，然后休息 $a_i$ 天。每天老板会在上班的人中选一个发一枚奖章。问最快在第几天结束时，每个人都至少有 $k$ 枚奖章。

$1\le n\le18,1\le k,a_i\le10^5$。

首先，答案的上界不超过 $5.4\times10^6$。证明考虑每 $3\times10^5$ 分一段，每段内的奖章全部给一个人，显然这样一个人拿到的奖章超过 $10^5$ 枚，下文中设这个上界为 $MAXX$。

考虑二分天数，然后检查能否满足。如何检查？

我们发现每天有很多个人有可能拿到奖章，但只有一个人最终能拿到奖章，这很像一个网络流。

从源点向每天连一条流量为 $1$ 的边，每天再向该天有工作的人连流量为 $+\infty$ 的边，每个人向汇点连流量为 $k$ 的边，这个图的最大流就是能发出的奖章数。

但是显然这个复杂度很大，如何优化？

首先可以注意到，有很多天数本质上是相同的（在这些天工作的人的集合相同）。所以我们可以把这天工作的人压成状态 $S$，每天的状态可以 $O(MAXXn)$ 预处理出来。这样，代表天的点就可以合并为表示工作的人的集合的 $2^n$ 个点，源点到这个点的流量，就是这个工作集合出现了几次。

下文中，我们把表示工作的人的集合的点称为左部点，表示人的点称为右部点。

然后，我们考虑不显式地跑网络流。由于这个图的特殊性质，我们其实可以直接算出图的最大流。

由最大流最小割定理，问题转化为求图的最小割。

我们 $O(2^n)$ 枚举没有被割掉的连到汇点的边的右部点的集合 $S$ ，然后考虑最小化割掉的源点连到左部点的边的流量和。

如果我们没有割掉某条右部点连到汇点的边，那么对于所有与这个右部点有边连接的左部点，源点到这些点的边都必须被割掉，否则就可以不被割掉。

容易发现，对于那些对应状态为 $S$ 的子集的左部点，源点到它们的边都可以被保留。而其它从源点连向左部点的边都得被删除。

肯定不能枚举子集，那样复杂度爆炸。我们可以直接使用 $FWT\ O(n2^n)$ 求出删除状态为 $S$ 时，保留的边的边权和。

总时间复杂度 $O(MAXXn+n2^n\log MAXX)$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define  mid ((l + r) >> 1)
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 18;
const int MAXX = 5.4e6;

int n, k;
int a[N + 1];
int type[MAXX + 1], w[1 << N];
int ans;

inline void init()
{
    for (int i = 1; i <= MAXX; i++) {
        int sum = 0;
        for (int j = 1; j <= n; j++)
            if (i % (2 * a[j]) > 0 && i % (2 * a[j]) <= a[j])
                sum |= (1 << (j - 1));
        type[i] = sum;
    }
    return;
}
inline bool check(int val)
{
    int sum, flow = n * k, p = n * k + val;

    for (int S = 0; S < 1 << n; S++)
        w[S] = 0;
    for (int i = 1; i <= val; i++)
        w[type[i]]++;
    for (int i = 1; i <= n; i++) {
        for (int S = 0; S < 1 << n; S++)
            if (S & (1 << (i - 1)))
                w[S] += w[S ^ (1 << (i - 1))];
    }
    for (int S = 0; S < 1 << n; S++) {
        sum = p - w[S];
        for (int i = 1; i <= n; i++)
            if ((S & (1 << (i - 1))) == 0)
                sum -= k;
        flow = min(flow, sum);
    }
    return flow >= n * k;
}
int main()
{
    n = read();
    k = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    init();

    int l = n * k, r = MAXX;

    while (l <= r) {
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    printf("%d\n", ans);
    return 0;
}