[Kickstart Round G 2019 C. Shifts] 中途相遇+线段树

发表于 | 分类于 | 阅读次数:

1. 题目链接

Kickstart Round G 2019 C. Shifts

2. 题目描述

Aninda 和 Boon-Nam是一个小型美术馆的保安。他们的工作包括 $N$ 个班次 $(1\le N\le 20)$。在每个班次中，两个警卫中的至少一个必须工作。

两位后卫对每个班次都有不同的偏好。对于第 $i$ 个班次，如果 Aninda 工作，她将获得 $A_i$ 幸福点，而如果 Boon-Nam 工作，她将获得 $B_i$ 幸福点。

如果两个警卫都获得至少 $H$ 个快乐点，他们将感到高兴。守卫会感到高兴的班次有几种不同的分配方式？

如果 Aninda 在一个作业中工作而不是另一工作，或者 Boon-Nam 在一个作业中工作而在另一工作中不工作，则认为两个作业是不同的。

3. 解题思路

3.1 中途相遇+线段树

把 $N$ 天等分成 前 $\frac{N}{2}$ 天、后 $(N-\frac{N}{2})$ 天。然后分别枚举前 $\frac{N}{2}$ 天、后 $(N-\frac{N}{2})$ 天的所有可能的组合，并对每种组合计算 Aninda 和 Boon-Nam 的幸福分数。

然后对于每个后$(N-\frac{N}{2})$ 天中的 $(\mathrm{right}_A, \mathrm{right}_B)$ ，我们计算前 $\frac{N}{2}$ 天的幸福点对 $(\mathrm{left}_A, \mathrm{left}_B)$的个数，其中 $\mathrm{left}_A\ge (H-\mathrm{right}_A)$，$\mathrm{left}_B\ge (H-\mathrm{right}_B)$。

我们对前 $\frac{N}{2}$ 天、后 $(N-\frac{N}{2})$ 天的幸福点对都进行一次升序排序，先排序第一维，再排序第二维。

然后，从小打大枚举排序后的后 $(N-\frac{N}{2})$ 天的幸福点对。对于每个后$(N-\frac{N}{2})$ 天中的 $(\mathrm{right}_A, \mathrm{right}_B)$ ，找到所有第一维符合 $\mathrm{left}_A\ge (H-\mathrm{left}_B)$ 的幸福点对，将改点对的 第二维 $\mathrm{right}_A$ 插入到线段树中。然后统计线段树中，第二维的幸福值在 $[H-\mathrm{left}_B, +\infty)$ 区间的个数（线段树的单点更新，区间查询）。

复杂度是 $\mathcal{O}(\frac{N}{2}\times 3^{\frac{N}{2}})$。

3.2 暴力枚举+剪枝

先枚举 $A$，再枚举 $B$，复杂度可以达到 $\mathcal{O}(2^{\frac{3N}{2}})$。

也可以直接枚举所有组合，复杂度可以达到$\mathcal{O}(3^N)$。

加几个剪枝，也许就过了。

4. 参考代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// 3.1 中途相遇+线段树
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

template<typename T> void umax(T& a, const T b) { a = max(a, b); }
template<typename T> void umin(T& a, const T b) { a = min(a, b); }

const int MAXN = 21;
const int HALF_STATES = pow(3, MAXN/2+1);
int T, N;
ll H, A[MAXN], B[MAXN];
pair<ll, ll> le_sum[HALF_STATES], ri_sum[HALF_STATES];
int seg[HALF_STATES*6];

void dfs(int le, int ri, int mask, ll sum_a, ll sum_b, pair<ll, ll> f[]) {
    if(le > ri) return;
    if(le == ri) {
        f[mask * 3 + 0] = make_pair(sum_a + A[le], sum_b);
        f[mask * 3 + 1] = make_pair(sum_a, sum_b + B[le]);
        f[mask * 3 + 2] = make_pair(sum_a + A[le], sum_b + B[le]);
        return;
    }
    dfs(le + 1, ri, mask * 3 + 0, sum_a + A[le], sum_b, f);
    dfs(le + 1, ri, mask * 3 + 1, sum_a, sum_b + B[le], f);
    dfs(le + 1, ri, mask * 3 + 2, sum_a + A[le], sum_b + B[le], f);
}

void build(int le, int ri, int rt) {
    seg[rt] = 0;
    if(le == ri) return;
    int md = (le + ri) >> 1;
    build(le, md, rt << 1);
    build(md + 1, ri, rt << 1 | 1);
}
void update(const int& pos, int le, int ri, int rt) {
    if(le == ri) {
        seg[rt] += 1;
        return;
    }
    int md = (le + ri) >> 1;
    if(pos <= md) update(pos, le, md, rt << 1);
    else update(pos, md + 1, ri, rt << 1 | 1);
    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}
int query(int L, int R, int le, int ri, int rt) {
    if(L <= le && ri <= R) return seg[rt];
    int md = (le + ri) >> 1, ret = 0;
    if(L <= md) ret += query(L, R, le, md, rt << 1);
    if(R > md) ret += query(L, R, md + 1, ri, rt << 1 | 1);
    return ret;
}

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-3.txt", "r", stdin);
#endif
    scanf("%d", &T);
    for(int cas = 1; cas <= T; ++cas) {
        scanf("%d %lld", &N, &H);
        for(int i = 1; i <= N; ++i) {
            scanf("%lld", &A[i]);
        }
        for(int i = 1; i <= N; ++i) {
            scanf("%lld", &B[i]);
        }
        if(N == 1) {
            printf("Case #%d: %d\n", cas, (A[1] >= H) && (B[1] >= H));
            continue;
        }
        int le_siz = pow(3, N/2), ri_siz = pow(3, N-N/2);

        dfs(1, N/2, 0, 0, 0, le_sum);
        dfs(1, N/2, 1, 0, 0, le_sum);
        dfs(1, N/2, 2, 0, 0, le_sum);

        dfs(N/2 + 1, N, 0, 0, 0, ri_sum);
        dfs(N/2 + 1, N, 1, 0, 0, ri_sum);
        dfs(N/2 + 1, N, 2, 0, 0, ri_sum);

        vector<ll> buf;
        for(int i = 0; i < le_siz; ++i) {
            buf.push_back(le_sum[i].second);
//            buf.push_back(H-le_sum[i].second);
        }
        for(int i = 0; i < ri_siz; ++i) {
//            buf.push_back(ri_sum[i].second);
            buf.push_back(H-ri_sum[i].second);
        }
        sort(le_sum, le_sum + le_siz);
        sort(ri_sum, ri_sum + ri_siz);

        sort(buf.begin(), buf.end());
        buf.erase(unique(buf.begin(), buf.end()), buf.end());
        int buf_siz = buf.size();

        build(1, buf_siz, 1);
        ll ans = 0, last_pos = le_siz;

        for(int i = 0; i < ri_siz; ++i) {
            pair<ll, ll> base = make_pair(H-ri_sum[i].first, H-ri_sum[i].second);
            int pos = lower_bound(le_sum, le_sum + last_pos, base) - le_sum;
            for(int j = pos; j < last_pos; ++j) {
                int id_j = lower_bound(buf.begin(), buf.end(), le_sum[j].second) - buf.begin() + 1;
                update(id_j, 1, buf_siz, 1);
            }
            int id_i = lower_bound(buf.begin(), buf.end(), H-ri_sum[i].second) - buf.begin() + 1;
            ans += query(id_i, buf_siz, 1, buf_siz, 1);
            last_pos = pos;
        }

        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}
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
// 暴力枚举+剪枝
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

template<typename T> void umax(T& a, const T b) { a = max(a, b); }
template<typename T> void umin(T& a, const T b) { a = min(a, b); }

const int MAXN = 21;
int T, N;
ll H, A[MAXN], B[MAXN];
bool mpA[1<<MAXN], mpB[1<<MAXN];

ll dfs(int pos, int status, ll sum, int& status_A) {
    if(pos > N) {
        return mpB[status];
    }
    int f = ((status_A >> (pos - 1)) & 1);

    ll ret = 0;
    if(f) {
        if(sum >= H) ret += 2 * dfs(pos + 1, status, sum, status_A);
        else {
            ret += dfs(pos + 1, status, sum, status_A);
            ret += dfs(pos + 1, status | (1 << (pos - 1)), sum + B[pos], status_A);
        }
    } else {
        ret += dfs(pos + 1, status | (1 << (pos - 1)), sum + B[pos], status_A);
    }
    return ret;
}

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-3.txt", "r", stdin);
#endif
    scanf("%d", &T);
    for(int cas = 1; cas <= T; ++cas) {
        scanf("%d %lld", &N, &H);
        for(int i = 1; i <= N; ++i) {
            scanf("%lld", &A[i]);
        }
        for(int i = 1; i <= N; ++i) {
            scanf("%lld", &B[i]);
        }
        vector<int> fA;
        for(int i = (1<<N)-1; i >= 0; --i) {
            ll sumA = 0, sumB = 0;
            for(int j=0; j<N;++j) {
                int f = (i >> j) & 1;
                if(!f) continue;
                sumA += A[j+1];
                sumB += B[j+1];
            }
            if(sumA >= H) {
                mpA[i] = true, fA.push_back(i);
            }
            else mpA[i] = false;
            if(sumB >= H) mpB[i] = true;
            else mpB[i] = false;
        }
        ll ans = 0;
        for(int& i : fA) {
            ans += dfs(1, 0, 0ll, i);
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！