DDOSvoid's Blog

2020-2021 ACM-ICPC Brazil Subregional Programming Contest H SBC's Hangar

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/gym/102861/problem/H

Solution

注意到每个物品都大于等于比他小的任何物品的两倍，换句话说这个东西有点像二进制

即第 $k$ 小的物品大于前 $k-1$ 小的物品的总和

注意到原物品一共有 $2^n$ 中选法，那么我们可以二分找第 $r$ 小的选法使得第 $r+1$ 小的选法刚好大于右端点的限制

同样二分第 $l$ 小的选法使得第 $l-1$ 的选法刚好小于左端点的限制

那么我们的方案数就是第 $l$ 小到第 $r$ 小的选法中恰好选了 $k$ 个方案数

这个东西可以用数位 $dp$ 求

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
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <algorithm>
#define maxn 110
#define ll long long
#define ull unsigned long long
using namespace std;

int n, m;

ll a[maxn], L, R;

ull check(ll x) {
    ull s = 0;
    for (int i = 0; i < n; ++i) {
        if (x >> i & 1) s += a[i + 1];
        if (s > R) return s;
    } 
    return s;
}

ll f[maxn][maxn]; int d[maxn];
ll dfs(int pos, int limit, int k) {
    if (!pos) return k == m;
    if (!limit && ~f[pos][k]) return f[pos][k];
    int up = limit ? d[pos] : 1; ll ans = 0;
    for (int i = 0; i <= up; ++i) 
        ans += dfs(pos - 1, limit && i == d[pos], k + (i == 1));
    if (!limit) f[pos][k] = ans;
    return ans;
}

ll solve(ll x) {
    int l = 0;
    while (x) d[++l] = x % 2, x /= 2;
    return dfs(l, 1, 0);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1); cin >> L >> R; 
    ll l = 1, r = (1ll << n) - 1, mid, ans = -1;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid) >= L) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    l = 1, r = (1ll << n) - 1; ll Ans = -1;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid) <= R) Ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    fill(f[0], f[0] + maxn * maxn, -1);
    if (~ans && ~Ans) cout << solve(Ans) - solve(ans - 1) << "\n";
    else cout << "0\n";
    return 0;
}