2026寒假集训个人训练赛第六场

前面感觉像是一套 OI 的模拟题，后面两道没找到来源。又因为看错数据范围开小数组导致 RE 多次。

A. 奇数(odd)#

先算出来全局的奇偶性，然后每次修改看一下区间和的奇偶性和 k * 区间长度的奇偶性是否相同。

1
#include <iostream>
2

3
using namespace std;
4
typedef long long LL;
5
const int N = 200010;
6
LL a[N];
7

8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n, q;
12
    cin >> n >> q;
13
    for (int i = 1; i <= n; ++i) {
14
        cin >> a[i];
15
        a[i] += a[i - 1];
16
    }
17
    bool f = a[n] & 1;
18
    while (q--) {
19
        int l, r;
20
        LL k;
21
        cin >> l >> r >> k;
22
        bool f1 = k * (r - l + 1) & 1, f2 = (a[r] - a[l - 1]) & 1;
23
        if (f ^ (f1 != f2)) cout << "YES" << endl;
24
        else cout << "NO" << endl;
25
    }
26
    return 0;
27
}

B. 覆盖层数(cover)#

离散化差分前缀和即可。

1
#include <iostream>
2
#include <map>
3
using namespace std;
4
typedef long long LL;
5
const int N = 200010;
6
map<LL, LL> a;
7
int t[N];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n;
13
    cin >> n;
14
    for (int i = 0; i < n; ++i) {
15
        int l, r;
16
        cin >> l >> r;
17
        a[l]++, a[r + 1]--;
18
    }
19
    LL pre = a.begin()->first;
20
    LL s = 0;
21
    for (auto &[k, v] : a) {
22
        t[s] += k - pre;
23
        s += v;
24
        pre = k;
25
    }
26
    for (int i = 1; i <= n; ++i) cout << t[i] << ' ';
27
    cout << endl;
28
    return 0;
29
}

C. 卡牌(card)#

我刚开始把他想的特别复杂，实际上并没有。保证了 $a_i \le d_i$ 所以无视 a 和 d 的绑定关系，自己也不可能杀掉自己；另外也不可能出现环。所以尽可能贪心打，直接 a 和 d 分开排序双指针扫描，每成功配对一次答案 -1 即可。

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

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 1000010;
8
LL a[N], b[N];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n, res = 0;
14
    cin >> n;
15
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
16
    sort(a + 1, a + n + 1);
17
    sort(b + 1, b + n + 1);
18
    res = n;
19
    for (int i = 1, j = 1; i <= n && j <= n; ++i) {
20
        while (j <= n && a[j] <= b[i]) j++;
21
        if (j <= n) res--, j++;
22
    }
23
    cout << res << endl;
24
    return 0;
25
}

D. 链(chain)^(补题)#

这题感觉我本来可能还能做出来，都是 E 题的那个树套树的点子害的……

可以逆向思维，从只有一个点开始加点，对于一个已经有了 $i$ 个连通块的状态，考虑加一个点

连上任意两个相邻的块，对 $i - 1$ 贡献了 $i - 1$ ；
在任意一个块左侧或者右侧添加，对 $i$ 贡献 $2i$ ；
在任意一个空隙加一个点，对 $i + 1$ 贡献 $i + 1$ 。

然后写成矩阵用矩阵快速幂就可以过了。这道题数据量有点大，先把查询离线了在快速幂的循环里一块乘才能过，时间复杂度是 $O\left(\left(m^2q + m^3\right)\cdot\log{n}\right)$ 。

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

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 510, M = 110;
9
const int MOD = 1000000007;
10
int m;
11
LL a[M][M], b[M][M], v[N][M], v2[M];
12

13
void mul1(LL v1[]) {
14
    memset(v2, 0, sizeof(v2));
15
    for (int i = 0; i < m; ++i) {
16
        for (int j = 0; j < m; ++j) {
17
            v2[i] = (v2[i] + a[j][i] * v1[j]) % MOD;
18
        }
19
    }
20
    memcpy(v1, v2, sizeof(v2));
21
}
22

23
void mul2() {
24
    memset(b, 0, sizeof(b));
25
    for (int i = 0; i < m; ++i) {
26
        for (int j = 0; j < m; ++j) {
27
            for (int k = 0; k < m; ++k) {
28
                b[i][j] = (b[i][j] + a[i][k] * a[k][j]) % MOD;
29
            }
30
        }
31
    }
32
    memcpy(a, b, sizeof(a));
33
}
34

35
int main() {
36
    ios::sync_with_stdio(0);
37
    cin.tie(0), cout.tie(0);
38
    int q;
39
    cin >> m >> q;
40
    for (int i = 1; i <= m; ++i) {
41
        if (i >= 2) a[i - 1][i - 2] += i - 1;
42
        a[i - 1][i - 1] += i * 2;
43
        if (i < m) a[i - 1][i] += i + 1;
44
    }
45
    vector<int> qs(q);
46
    for (int i = 0; i < q; ++i) {
47
        cin >> qs[i];
48
        qs[i]--;
49
        v[i][0] = 1;
50
    }
51
    bool f = true;
52
    while (f) {
53
        f = false;
54
        for (int i = 0; i < q; ++i) {
55
            if (qs[i] & 1) mul1(v[i]);
56
            qs[i] >>= 1;
57
            if (qs[i]) f = true;
58
        }
59
        mul2();
60
    }
61
    for (int i = 0; i < q; ++i) cout << v[i][0] << endl;
62
    return 0;
63
}

E. 完美的答卷(perfect)^(补题)#

我想到了一个特别麻烦的树形 DP + 可持久化 Trie 的做法，然而没写完。这个做法是单 log 时间复杂度，跑的很快。

树形 DP + 可持久化 Trie#

看到这种区间最大和最小，我直接本能的想到单调栈，单调栈能快速得到某个数为最大值的最大区间。然后问题就转化成了已知一个区间和最大值的位置，找到一个包含最大值的子区间，使得最小值和最大值的异或和最大。异或和最大，是经典的 Trie 能解决的问题。现在问题转化成了如何快速得到这个区间的所有可能的最小值构成的 Trie，因为必须包含这个最大值，所以整个问题可以分成两个子问题，右边的前缀 min 和左边的 后缀min。以前缀 min 为例，后缀 min 直接把数组 reverse 一下再来一遍就好了。我们想要得到的是每一个子区间可能的前缀 min，也是从左到右做单调递增单调栈的栈底元素，单调栈弹栈的过程其实就是新的最小值覆盖旧的最小值的过程，每个元素可能且仅可能被一个后面的元素弹出，最终这种覆盖的过程构成一棵内向树，反转所有的边，令树的结点为字典树，从根到叶子进行树形 DP（从右往左）可以得到任何一个中间点走到末尾路径上的所有前缀 min。最后只需要在维护一个树上倍增，然后利用可持久化 Trie 进行差分，就可以得到目标 Trie 了。

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

6
using namespace std;
7

8
typedef long long LL;
9
const int N = 300010;
10
int trie[N * 21][2];
11
int a[N], rt[N], tot;
12
int st[N], tp;
13
int ver[N], head[N], ne[N], f[N][20], idx;
14
int n;
15

16
void insert(int x, int cur, int pre) {
17
    for (int i = 19; i >= 0; --i) {
18
        bool t = x >> i & 1;
19
        trie[cur][t] = ++tot;
20
        trie[cur][t ^ 1] = trie[pre][t ^ 1];
21
        cur = trie[cur][t], pre = trie[pre][t];
22
    }
23
}
24

25
int query(int x, int l, int r) {
26
    int res = 0;
27
    for (int i = 19; i >= 0; --i) {
28
        bool t = x >> i & 1;
29
        if (trie[r][t ^ 1] && trie[r][t ^ 1] != trie[l][t ^ 1]) {
30
            res += 1 << i;
31
            l = trie[l][t ^ 1], r = trie[r][t ^ 1];
32
        }
33
        else {
34
            l = trie[l][t], r = trie[r][t];
35
        }
36
    }
37
    return res;
38
}
39

40
void add(int x, int y) {
41
    ver[++idx] = y;
42
    ne[idx] = head[x];
43
    head[x] = idx;
44
}
45

46
void dfs(int x) {
47
    for (int i = 1; i < 20; ++i) {
48
        f[x][i] = f[f[x][i - 1]][i - 1];
49
    }
50
    for (int i = head[x]; i; i = ne[i]) {
51
        int y = ver[i];
52
        if (y == f[x][0]) continue;
53
        f[y][0] = x;
54
        rt[y] = ++tot;
55
        insert(a[y], rt[y], rt[x]);
56
        dfs(y);
57
    }
58
}
59

60
int qrange(int x, int l, int r) {
61
    // cout << x << ' ' << l << ' ' << r << endl;
62
    int p = l;
63
    for (int i = 19; i >= 0; --i) {
64
        if (f[p][i] <= r) p = f[p][i];
65
    }
66
    p = f[p][0];
67
    // cout << "QWQ" << l << ' ' << p << ' ' << query(x, rt[p], rt[l]) << endl;
68
    return query(x, rt[p], rt[l]);
69
}
70

71
int work() {
72
    idx = tot = 0;
73
    memset(trie, 0, sizeof(trie));
74
    memset(head, 0, sizeof(head));
75
    int res = 0;
76
    // 单调递增
77
    tp = 0;
78
    int tst = 0;
79
    for (int i = 1; i <= n; ++i) {
80
        while (tp && a[i] <= a[st[tp]]) {
81
            add(i, st[tp--]);
82
        }
83
        st[++tp] = i;
84
    }
85
    while (tp) {
86
        add(n + 1, st[tp]);
87
        tp--;
88
    }
89
    f[n + 1][0] = n + 1;
90
    dfs(n + 1);
91
    // 单调递减
92
    tp = 0;
93
    for (int i = 1; i <= n; ++i) {
94
        while (tp && a[i] > a[st[tp]]) {
95
            res = max(res, qrange(a[st[tp]], st[tp], i - 1));
96
            tp--;
97
        }
98
        st[++tp] = i;
99
    }
100
    while (tp) {
101
        res = max(res, qrange(a[st[tp]], st[tp], n));
102
        tp--;
103
    }
104
    return res;
105
}
106

107
int main() {
108
    // freopen("input", "r", stdin);
109
    ios::sync_with_stdio(0);
110
    cin.tie(0), cout.tie(0);
111
    cin >> n;
112
    for (int i = 1; i <= n; ++i) cin >> a[i];
113
    int res = work();
114
    reverse(a + 1, a + n + 1);
115
    res = max(res, work());
116
    cout << res << endl;
117
    return 0;
118
}

分治#

MoScenix 的双 log 做法非常简洁干净。

F. City Game#

用 bitset 暴力。

1
#pragma GCC optimize("Ofast")
2
#include <iostream>
3
#include <bitset>
4

5
using namespace std;
6

7
const int N = 1000;
8
bitset<N> a[N];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n, m;
14
    char c;
15
    cin >> n >> m;
16
    for (int i = 0; i < n; ++i) {
17
        for (int j = 0; j < m; ++j) {
18
            cin >> c;
19
            a[i][j] = c == 'F';
20
        }
21
    }
22
    int res = 0;
23
    for (int i = 0; i < n; ++i) {
24
        bitset<N> t = a[i];
25
        int cnt = 0;
26
        for (int j = 0; j < m; ++j) {
27
            if (t[j] == 1) cnt++;
28
            else cnt = 0;
29
            res = max(res, cnt);
30
        }
31
        for (int k = i - 1; k >= 0; --k) {
32
            t &= a[k];
33
            cnt = 0;
34
            for (int j = 0; j < m; ++j) {
35
                if (t[j] == 1) cnt++;
36
                else cnt = 0;
37
                res = max(res, cnt * (i - k + 1));
38
            }
39
        }
40
    }
41
    cout << res * 3 << endl;
42
    return 0;
43
}

G. Colorful Lines#

从后往前算，给已经染过色的行和列打上标记，每次更新答案的时候减掉重复的即可。

1
#include <iostream>
2
#include <tuple>
3
#include <vector>
4
#include <set>
5

6
using namespace std;
7

8
typedef long long LL;
9
const int N = 300010;
10
vector<tuple<int, int, int>> qs;
11
set<int> row, col;
12
LL res[N];
13

14
int main() {
15
    ios::sync_with_stdio(0);
16
    cin.tie(0), cout.tie(0);
17
    int h, w, q, m;
18
    cin >> h >> w >> m >> q;
19
    qs.resize(q);
20
    for (int i = 0; i < q; ++i) {
21
        auto &[a, b, c] = qs[i];
22
        cin >> a >> b >> c;
23
    }
24
    for (int i = q - 1; i >= 0; --i) {
25
        auto &[op, n, c] = qs[i];
26
        if (op == 1) { // row
27
            if (row.count(n)) continue;
28
            res[c] += w - col.size();
29
            row.insert(n);
30
        }
31
        else { // col
32
            if (col.count(n)) continue;
33
            res[c] += h - row.size();
34
            col.insert(n);
35
        }
36
    }
37
    for (int i = 1; i <= m; ++i) cout << res[i] << ' ';
38
    cout << endl;
39
    return 0;
40
}

Star's Blog