备战2025区域赛组队训练赛第 19 场

B. Lovers#

签到题，二分答案或者用 set.lower_bound。

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
const int N = 200010;
7
int a[N], b[N];
8
int n, k;
9

10
bool check(int mid) {
11
    for (int i = n - mid + 1, j = n; i <= n; ++i, --j) {
12
        if (a[i] + b[j] < k) return false;
13
    }
14
    return true;
15
}
16

17
int main() {
18
    int T;
19
    scanf("%d", &T);
20
    while (T--) {
21
        scanf("%d%d", &n, &k);
22
        for (int i = 1; i <= n; ++i) {
23
            scanf("%d", &a[i]);
24
        }
25
        for (int i = 1; i <= n; ++i) {
26
            scanf("%d", &b[i]);
27
        }
28
        sort(a + 1, a + n + 1);
29
        sort(b + 1, b + n + 1);
30
        int l = 0, r = n;
31
        while (l < r) {
32
            int mid = l + r + 1 >> 1;
33
            if (check(mid)) l = mid;
34
            else r = mid - 1;
35
        }
36
        printf("%d\n", l);
37
    }
38
    return 0;
39
}

F. God of Gamblers#

\frac{a}{a + b}

蒙出来的，不知道具体原理。因为如果不考虑钱不够的情况下，如果赌赢一次一定比上一次输之前多一块钱，就感觉是 $\frac{a}{a + b}$ .

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int a, b;
7
    while (scanf("%d%d", &a, &b) != EOF)
8
        printf("%.5lf\n", (double)a / (a + b));
9
    return 0;
10
}

G. Sum of xor sum#

我本来想用线段树维护矩阵乘法做 dp 的，理论上似乎也可行。但是有个更简单的做法，因为统计答案和数位是独立的，可以分开考虑不同的数位，这样就只有 0/1 了。考虑段的拼接，如何把连续的子区间合并答案，这里就不难想到最大子段和的维护，新答案 = 左段的答案 + 右段的答案 +（左端为 0 的后缀数 * 右端为 1 的前缀数）+（左端为 1 的后缀数 * 有段为 0 的前缀数）。按位拆开，线段树维护每位的答案，对于每一个请求做区间查询即可。

应该还有一个更快的 O(n) 的做法。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100010;
6
const int MOD = 1000000007;
7
typedef long long LL;
8

9
struct Node {
10
    LL sum;
11
    int val, sl0, sr0, len;
12

13
    void print() {
14
        printf("%lld %d %d %d %d\n", sum, val, sl0, sr0, len);
15
    }
16
};
17

18
Node merge(Node a, Node b) {
19
    Node c;
20
    if (a.val) c.sl0 = a.sl0 + (b.len - b.sl0);
21
    else c.sl0 = a.sl0 + b.sl0;
22
    if (b.val) c.sr0 = (a.len - a.sr0) + b.sr0;
23
    else c.sr0 = a.sr0 + b.sr0;
24
    c.val = a.val ^ b.val;
25
    c.len = a.len + b.len;
26
    c.sum = (LL)(a.sr0) * (b.len - b.sl0) + (LL)(a.len - a.sr0) * b.sl0 + a.sum + b.sum;
27
    c.sum %= MOD;
28
    return c;
29
}
30

31
struct SegmentTree {
32
    Node tr[N * 4];
33

34
    void pushup(int u) {
35
        tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
36
    }
37

38
    void build(int u, int l, int r, int a[], int b) {
39
        if (l == r) {
40
            int t = a[l] >> b & 1;
41
            tr[u] = {t, t, t ^ 1, t ^ 1, 1};
42
        }
43
        else {
44
            int mid = l + r >> 1;
45
            build(u << 1, l, mid, a, b), build(u << 1 | 1, mid + 1, r, a, b);
46
            pushup(u);
47
        }
48
    }
49

50
    Node query(int u, int l, int r, int ql, int qr) {
51
        if (ql <= l && r <= qr) return tr[u];
52
        else {
53
            int mid = l + r >> 1;
54
            Node res = {0, 0, 0, 0, 0};
55
            if (ql <= mid) res = merge(res, query(u << 1, l, mid, ql, qr));
56
            if (qr > mid) res = merge(res, query(u << 1 | 1, mid + 1, r, ql, qr));
57
            return res;
58
        }
59
    }
60
} smt[20];
61

62
int a[N];
63

64
int main() {
65
    int T;
66
    scanf("%d", &T);
67
    while (T--) {
68
        int n, q;
69
        scanf("%d%d", &n, &q);
70
        for (int i = 1; i <= n; ++i) {
71
            scanf("%d", &a[i]);
72
        }
73
        for (int i = 0; i < 20; ++i) smt[i].build(1, 1, n, a, i);
74
        while (q--) {
75
            int l, r;
76
            scanf("%d%d", &l, &r);
77
            LL res = 0;
78
            for (int i = 0; i < 20; ++i) {
79
                auto t = smt[i].query(1, 1, n, l, r);
80
                // t.print();
81
                res = (res + (1LL << i) * t.sum % MOD) % MOD;
82
            }
83
            // printf("\n");
84
            printf("%lld\n", res);
85
        }
86
    }
87
    return 0;
88
}

H. Arrangement for Contests#

贪心的从左到右一直取，需要一个线段树维护一下区间最小值。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100010;
6

7
int tr[N * 4], tag[N * 4];
8
int a[N];
9

10
void pushup(int u) {
11
    tr[u] = min(tr[u << 1], tr[u << 1 | 1]);
12
}
13

14
void pushdown(int u) {
15
    if (tag[u]) {
16
        tag[u << 1] += tag[u], tag[u << 1 | 1] += tag[u];
17
        tr[u << 1] += tag[u], tr[u << 1 | 1] += tag[u];
18
        tag[u] = 0;
19
    }
20
}
21

22
void build(int u, int l, int r) {
23
    tag[u] = 0;
24
    if (l == r) tr[u] = a[l];
25
    else {
26
        int mid = l + r >> 1;
27
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
28
        pushup(u);
29
    }
30
}
31

32
void modify(int u, int l, int r, int ql, int qr, int v) {
33
    if (ql <= l && r <= qr) {
34
        tr[u] += v;
35
        tag[u] += v;
36
    }
37
    else {
38
        pushdown(u);
39
        int mid = l + r >> 1;
40
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
41
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
42
        pushup(u);
43
    }
44
}
45

46
int query(int u, int l, int r, int ql, int qr) {
47
    if (ql <= l && r <= qr) return tr[u];
48
    else {
49
        pushdown(u);
50
        int mid = l + r >> 1, res = 0x3f3f3f3f;
51
        if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
52
        if (qr > mid) res = min(res, query(u << 1 | 1, mid + 1, r, ql, qr));
53
        return res;
54
    }
55
}
56

57
int main() {
58
    int T;
59
    scanf("%d", &T);
60
    while (T--) {
61
        int n, k;
62
        scanf("%d%d", &n, &k);
63
        for (int i = 1; i <= n; ++i) {
64
            scanf("%d", &a[i]);
65
        }
66
        build(1, 1, n);
67
        long long res = 0;
68
        for (int i = 1; i <= n - k + 1; ++i) {
69
            int t = query(1, 1, n, i, i + k - 1);
70
            res += t;
71
            // cout << t << ' ';
72
            modify(1, 1, n, i, i + k - 1, -t);
73
        }
74
        // cout << endl;
75
        printf("%lld\n", res);
76
    }
77
    return 0;
78
}

J. LOL#

暴搜前四个，同时维护第五个人的选择数，统计我方选英雄的方案数。然后需要乘 $A_{95}^{5} \cdot C_{90}^{10} \cdot C_{10}^{5}$ .

这个系数可以直接用 python 库算出来

1
❯ python
2
Python 3.12.2 | packaged by conda-forge | (main, Feb 16 2024, 20:54:21) [Clang 16.0.6 ] on darwin
3
Type "help", "copyright", "credits" or "license" for more information.
4
>>> import math
5
>>> math.perm(95, 5) * math.comb(90, 10) * math.comb(10, 5) % 1000000007
6
531192758

当然，也可以直接用答案反推出来，我们当时都懵了，感觉做对了但是求不出来这个系数，然后直接 515649254LL % MOD * power(res, MOD - 2) % MOD 倒推出来了。

1
#include <iostream>
2

3
using namespace std;
4
typedef long long LL;
5
const int MOD = 1000000007;
6
int a[5][100], b[100];
7
int t;
8
LL res;
9

10
LL power(LL n, LL p) {
11
    LL res = 1, b = n;
12
    while (p) {
13
        if (p & 1) res = res * b % MOD;
14
        b = b * b % MOD;
15
        p >>= 1;
16
    }
17
    return res;
18
}
19

20
void dfs(int x) {
21
    if (x == 4) {
22
        res = (res + t) % MOD;
23
        return;
24
    }
25
    for (int i = 0; i < 100; ++i) {
26
        if (b[i] || !a[x][i]) continue;
27
        b[i] = 1;
28
        if (a[4][i]) t--;
29
        dfs(x + 1);
30
        if (a[4][i]) t++;
31
        b[i] = 0;
32
    }
33
}
34

35
int main() {
36
    while (1) {
37
        for (int i = 0; i < 5; ++i) {
38
            for (int j = 0; j < 100; ++j) {
39
                if (scanf("%1d", &a[i][j]) == EOF) {
40
                    return 0;
41
                }
42
            }
43
        }
44
        t = 0;
45
        res = 0;
46
        for (int i = 0; i < 100; ++i) if (a[4][i]) t++;
47
        dfs(0);
48
        printf("%lld\n", res * 531192758 % MOD);
49
        // printf("%lld\n", 515649254LL % MOD * power(res, MOD - 2) % MOD);
50
    }
51
    return 0;
52
}

Star's Blog

B. Lovers#

F. God of Gamblers#

G. Sum of xor sum#

H. Arrangement for Contests#

J. LOL#