题目链接：Educational Codeforces Round 172 (Rated for Div. 2)

A题

贪心（题目中也明确规定了就是贪心），排序从最大的开始取就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
    int n, k;
    cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    std::sort(a.begin(), a.end(), std::greater<int>());
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (res + a[i] <= k) {
            res += a[i];
        } else break;
    }
    cout << k - res << '\n';
}

B题

贪心，如果有数字只出现了一次，那么取到它可以得到两分，设该数字个数为$cnt1$，则先手可以得到$2\lceil \frac{cnt1}{2} \rceil$分，之后出现多次的数字一定不可能被一个人取完，但一定可以取到一个，设出现次数大于一的数字个数为$cnt2$ ，那么最终答案就是$2\lceil \frac{cnt1}{2} \rceil+cnt2$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
    int n;
    cin >> n;
    std::vector<int> cnt(n + 1);
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        cnt[num]++;
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 1) {
            cnt1++;
        } else if (cnt[i] > 1) {
            cnt2++;
        }
    }
    cout << (cnt1 + 1) / 2 * 2 + cnt2 << '\n';
}

C题

换一个角度看这个问题，我们将整个位串分为$m$组，每一组的1的个数与0的个数之差乘该组权值就是该组Bob超过Alice的分数，即$\sum_{i=1}^{m}(i-1)(cnt1_i-cnt0_i)=\sum_{i=2}^{m}(\sum_{j=i}^{m}cnt1_i-\sum_{j=i}^{m}cnt0_i)$，也就是从第二组开始到最后位置的所有1，0的数量差+从第三组开始到最后位置所有1，0的数量差…，这样算下来，第二组被加了一次，第三组被加了两次，…，第m组只被加了(m-1)次，这样我们只需要看从某一个位置作为起点到最后一个位置的0，1数量差，把它当作一组。

从后往前推出从当前位置到末尾的10数量差，之后从大到小取即可，注意第一组没有加权，排序时应丢弃第一个位置的数字。

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
void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    std::vector<int> sum(n);
    for (int i = n - 1; i >= 0; i--) {
        if (i < n - 1) {
            sum[i] = sum[i + 1];
        }
        if (s[i] == '1') {
            sum[i]++;
        } else {
            sum[i]--;
        }
    }
    sum.erase(sum.begin());
    std::sort(sum.begin(), sum.end(), std::greater());
    
    i64 ans = 0;
    for (int i = 1; i < n; i++) {
        ans += sum[i - 1];
        if (ans >= k) {
            cout << i + 1 << '\n';
            return;
        }
    }
    cout << -1 << '\n';
}

D题

（来源：jiangly）

我们先考虑吧左边界的情况，将所有用户按左边界按从小到大排序，那么左侧的用户的左边界一定比当前序号的用户左边界小，右侧的用户左边界一定比当前用户大，那么右侧的用户就不可能作为当前用户的predictor，此时取左侧所有用户右边界的大于当前序号的右边界的最小值，作为向当前用户推荐音乐的右边界，反之左边界同理。

注意如果有两个或多个序号左右边界相同，那么他们互为predictor，这需要特判一下，因为它们之中的第一个在确定推荐音乐的边界不知道第二个的存在，因此需要向下看一位，如果是边界相同的话，再更新。

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
void solve() {
    int n;
    cin >> n;
    std::vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
    }
    std::vector<int> L(n, -1), R(n, -1);
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    {
        std::sort(p.begin(), p.end(), [&](int i, int j) {
                if (l[i] != l[j]) {
                    return l[i] < l[j];
                }
                return r[i] > r[j];
            });
        std::set<int> ms;
        for (int j = 0; j < n; j++) {
            int i = p[j];
            auto it = ms.lower_bound(r[i]);
            if (it != ms.end()) {
                R[i] = *it;
            }
            ms.insert(r[i]);
            if (j < n - 1 && l[i] == l[p[j + 1]] && r[i] == r[p[j + 1]]) {
                R[i] = r[i];
            }
        }
    }
    {
        std::sort(p.begin(), p.end(), [&](int i, int j) {
                if (r[i] != r[j]) {
                    return r[i] > r[j];
                }
                return l[i] < l[j];
            });
        std::set<int> ms;
        for (int j = 0; j < n; j++) {
            int i = p[j];
            auto it = ms.upper_bound(l[i]);
            if (it != ms.begin()) {
                L[i] = *std::prev(it);
            }
            ms.insert(l[i]);
            if (j < n - 1 && l[i] == l[p[j + 1]] && r[i] == r[p[j + 1]]) {
                L[i] = l[i];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        int ans;
        if (L[i] == -1) {
            ans = 0;
        } else {
            ans = R[i] - L[i] - (r[i] - l[i]);
        }
        cout << ans << '\n';
    }
}