2025春训第二十六场

题面可以看这里.

A. 数列计数#

最害怕的数学题。

$\prod_{i=1}^{n}\binom{a_i}{b_i}$ 等价于对于每一个 i，都有 $\binom{a_i}{b_i}$ 为奇数。

对于 $\binom{n}{k}$ ，根据（ChatGPT指出的）卢卡斯定理，取 p = 2 有

\binom{n}{k} \equiv \binom{n\ \text{mod}\ 2}{k\ \text{mod}\ 2} \binom{\lfloor\frac{n}{2}\rfloor}{1}\ (\text{mod}\ 2)

右边这一项同理可以不断展开，最终等价于**取出了 n 和 k 的所有二进制位算组合数再乘积。**显然要想保证是奇数，只能 k 的每个二进制位都不比 n 大。

对于每一项做一次数位 dp，统计每一位都比 $a_i$ 小的数的个数即可，时间复杂度是 $\Theta(n\log 10^9)$ 。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100010;
6
const int MOD = 998244353;
7
int a[N];
8
long long f[31][2]; // 第i位，是否顶上界
9

10
int dp(int a, int l) {
11
    f[30][1] = 1;
12
    for (int i = 29; i >= 0; --i) {
13
        if (a >> i & 1) { // 可选 1 和 0
14
            if (l >> i & 1) {
15
                f[i][1] = f[i + 1][1];
16
                f[i][0] = (f[i + 1][0] * 2 + f[i + 1][1]) % MOD;
17
            }
18
            else {
19
                f[i][1] = f[i + 1][1];
20
                f[i][0] = f[i + 1][0] * 2 % MOD;
21
            }
22
        }
23
        else { // 只能选 0
24
            if (l >> i & 1) {
25
                f[i][1] = 0;
26
                f[i][0] = (f[i + 1][0] + f[i + 1][1]) % MOD;
27
            }
28
            else {
29
                f[i][1] = f[i + 1][1];
30
                f[i][0] = f[i + 1][0];
31
            }
32
        }
33
    }
34
    return (f[0][0] + f[0][1]) % MOD;
35
}
36

37
int main() {
38
    int T;
39
    scanf("%d", &T);
40
    while (T--) {
41
        int n;
42
        scanf("%d", &n);
43
        for (int i = 1; i <= n; ++i) {
44
            scanf("%d", &a[i]);
45
        }
46
        long long res = 1;
47
        for (int i = 1; i <= n; ++i) {
48
            int l;
49
            scanf("%d", &l);
50
            res = (res * dp(a[i], min(l, a[i]))) % MOD;
51
        }
52
        printf("%lld\n", res);
53
    }
54
    return 0;
55
}

D. 弯曲筷子#

这道题需要发现一个小结论，显然我当时没发现……

先对 c 数组排序一下，排序后一根筷子只可能和他相邻的或者隔一个的筷子配对。所以问题就转化成了一个线性dp 的问题。对于每一个 i 只用考虑 i - 1 和 i - 2. dp时主要需要考虑兜底，即如何强制选上必须选的，状态转移方程很简单，可以参考下面的代码。

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

5
using namespace std;
6

7
const int N = 300010;
8

9
pair<int, bool> c[N];
10
long long f[N][2];
11

12
long long p2(long long a) {
13
    return a * a;
14
}
15

16
int main() {
17
    int T;
18
    scanf("%d", &T);
19
    while (T--) {
20
        int n, m;
21
        scanf("%d%d", &n, &m);
22
        memset(f, 0x3f, sizeof(long long) * (n * 2 + 1));
23
        for (int i = 1; i <= n; ++i) {
24
            scanf("%d", &c[i].first);
25
            c[i].second = false;
26
        }
27
        for (int i = 1; i <= m; ++i) {
28
            int t;
29
            scanf("%d", &t);
30
            c[t].second = true;
31
        }
32
        f[0][1] = 0;
33
        sort(c + 1, c + n + 1);
34
        int pre = 0;
35
        for (int i = 1; i <= n; ++i) {
36
            if (c[i - 1].second) {
37
                f[i][0] = f[i - 1][1]; // 一定要配对
38
                f[i][1] = f[i - 1][0] + p2(c[i].first - c[i - 1].first);
39
            }
40
            else {
41
                f[i][0] = min(f[i - 1][0], f[i - 1][1]); // 随意
42
                if (i >= 2) f[i][1] = min(f[i - 1][0] + p2(c[i].first - c[i - 1].first), f[i - 2][0] + p2(c[i].first - c[i - 2].first));
43
            }
44
        }
45
        if (c[n].second) printf("%lld\n", f[n][1]);
46
        else printf("%lld\n", min(f[n][0], f[n][1]));
47
    }
48
    return 0;
49
}

E. 修复公路#

我感觉这应该是最水的一道题，我们需要用最小的代价使不连通的图连通，显然就是把本来不连通的连通块作为节点建一棵树，答案是连通块数量 - 1.

需要主意别把初始化写挂😭

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <cstring>
5

6
using namespace std;
7

8
const int N = 300010;
9

10
vector<int> ed[N];
11
bool vis[N];
12

13
void dfs(int x) {
14
    if (vis[x]) return;
15
    vis[x] = true;
16
    for (int y : ed[x]) {
17
        dfs(y);
18
    }
19
}
20

21
void solve() {
22
    int n;
23
    scanf("%d", &n);
24
    for (int i = 1; i <= n; ++i) {
25
        vis[i] = false;
26
        ed[i].clear();
27
    }
28
    for (int i = 1; i <= n; ++i) {
29
        int t;
30
        scanf("%d", &t);
31
        if (i - t > 0) ed[i].push_back(i - t), ed[i - t].push_back(i);
32
        if (i + t <= n) ed[i].push_back(i + t), ed[i + t].push_back(i);
33
    }
34
    int cnt = 0;
35
    for (int i = 1; i <= n; ++i) {
36
        if (!vis[i]) cnt++, dfs(i);
37
    }
38
    printf("%d\n", cnt - 1);
39
}
40

41
int main() {
42
    int T;
43
    scanf("%d", &T);
44
    while (T--) {
45
        solve();
46
    }
47
    return 0;
48
}

G. 宝石商店#

这是一道纯数据结构题，不难发现

(a_i \lor x) \oplus (a_i \land x) = a_i \oplus x

问题转化成在区间 [l, r] 内找一个 i，使得 $a_i \oplus x$ 最大。于是可持久化字典树或者主席树套字典树都行。建议别写树套树，一错一个不吱声。

我不作死，我写的是字典树。

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

4
using namespace std;
5

6
const int N = 200010;
7

8
int trie[N * 60][2], rt[N], tot;
9

10
void add(int x, int cur, int pre) {
11
    for (int i = 30; i >= 0; --i) {
12
        bool t = x >> i & 1;
13
        trie[cur][t] = ++tot;
14
        trie[cur][t ^ 1] = trie[pre][t ^ 1];
15
        cur = trie[cur][t], pre = trie[pre][t];
16
    }
17
}
18

19
int query(int x, int l, int r) {
20
    int res = 0;
21
    for (int i = 30; i >= 0; --i) {
22
        bool t = x >> i & 1;
23
        if (trie[r][t ^ 1] && trie[r][t ^ 1] != trie[l][t ^ 1]) {
24
            res += 1 << i;
25
            l = trie[l][t ^ 1], r = trie[r][t ^ 1];
26
        }
27
        else {
28
            l = trie[l][t], r = trie[r][t];
29
        }
30
    }
31
    return res;
32
}
33

34
int main() {
35
    int T;
36
    scanf("%d", &T);
37
    while (T--){
38
        int n, m;
39
        scanf("%d%d", &n, &m);
40
        for (int i = 1; i <= n; ++i) {
41
            rt[i] = ++tot;
42
            int t;
43
            scanf("%d", &t);
44
            add(t, rt[i], rt[i - 1]);
45
        }
46
        while (m--) {
47
            int l, r, x;
48
            scanf("%d%d%d", &l, &r, &x);
49
            printf("%d\n", query(x, rt[l - 1], rt[r]));
50
        }
51
        memset(trie, 0, (tot + 1) * sizeof(trie[0]));
52
        memset(rt, 0, (n + 1) * sizeof(int));
53
        tot = 0;
54
    }
55
    return 0;
56
}

I. 部落冲突#

我这里魔改了一下并查集，这道题用并查集处理唯一的困难就是操作2（野蛮人 a 移动到部落 b 中），直接改野蛮人 a 的父亲可能会波及到他的子树，所以需要一种办法让每个野蛮人始终是叶子。于是我开了 n 个虚拟节点分别初始化成每个野蛮人的父亲，用来合并和交换，进行合并和交换的时候动的永远都是虚拟节点，这样随便改父亲就不会出问题了。

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

4
using namespace std;
5

6
const int N = 1000010;
7

8
int rep[N], rnk[N * 2], fa[N * 2]; // 前 n 个表示野蛮人，中间表示初始虚拟节点
9
int getfa(int x) {
10
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
11
}
12

13
void solve() {
14
    int n, q;
15
    scanf("%d%d", &n, &q);
16

17
    int tot = 2 * n;
18
    for (int i = 1; i <= n; ++i) {
19
        fa[i] = i + n;
20
        fa[i + n] = i + n;
21
        rep[i] = i + n; // 代表点暂时选中间的初始节点，不能动前 n 个
22
        rnk[i + n] = i;
23
    }
24

25
    while (q--) {
26
        int op;
27
        scanf("%d", &op);
28
        if (op == 4) {
29
            int a;
30
            scanf("%d", &a);
31
            printf("%d\n", rnk[getfa(a)]);
32
        }
33
        else {
34
            int a, b;
35
            scanf("%d%d", &a, &b);
36
            if (op == 1) {
37
                int r1 = rep[a], r2 = rep[b];
38
                fa[r2] = r1; // 合并
39
                rep[b] = r1;
40
            }
41
            else if (op == 2) {
42
                fa[a] = rep[b]; // 野蛮人只能是叶子
43
            }
44
            else {
45
                swap(rnk[rep[a]], rnk[rep[b]]);
46
                swap(rep[a], rep[b]);
47
            }
48
        }
49
    }
50
}
51

52
int main() {
53
    int T;
54
    scanf("%d", &T);
55
    while (T--) {
56
        solve();
57
    }
58
    return 0;
59
}

J. 选择配送#

这道题应该是第二水的题，尝试分类讨论分离两个点的参数，尝试去绝对值

|p_1 - p_2| + |q_1 - q_2| = \max\{|(p_1 + q_1) - (q_1 + q_2|), |(p_1 - q_1) - (p_2 + q_2)|\}

只需要记录四个极端值 $\max\{x_i + y_i\}, \min\{x_i + y_i\},\max\{x_i - y_i\},\min\{x_i - y_i\}$ 就能找到对于每个候选配送站的最大距离。

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

4
using namespace std;
5

6
const int N = 1000010;
7

8
int main() {
9
    int T;
10
    scanf("%d", &T);
11
    while (T--) {
12
        int n, m;
13
        long long mn_s = LLONG_MAX, mx_s = LLONG_MIN, mn_m = LLONG_MAX, mx_m = LLONG_MIN;
14
        scanf("%d%d", &n, &m);
15
        for (int i = 1; i <= n; ++i) {
16
            long long x, y;
17
            scanf("%lld%lld", &x, &y);
18
            mx_s = max(mx_s, x + y);
19
            mn_s = min(mn_s, x + y);
20
            mx_m = max(mx_m, x - y);
21
            mn_m = min(mn_m, x - y);
22
        }
23
        long long res = LLONG_MAX;
24
        for (int i = 1; i <= m; ++i) {
25
            long long x, y;
26
            scanf("%lld%lld", &x, &y);
27
            long long su = x + y, me = x - y;
28
            res = min(res, max(max(abs(su - mx_s), abs(su - mn_s)), max(abs(me - mx_m), abs(me - mn_m))));
29
        }
30
        printf("%lld\n", res);
31
    }
32
    return 0;
33
}

Star's Blog