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

A. 松果(pinecones)#

给最小的加 1。

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

4
using namespace std;
5

6
int main() {
7
    ios::sync_with_stdio(0);
8
    cin.tie(0), cout.tie(0);
9
    int n, mn = 100, p = 0;
10
    cin >> n;
11
    vector<int> a(n);
12
    for (int i = 0; i < n; ++i) {
13
        cin >> a[i];
14
        if (a[i] < mn) mn = a[i], p = i;
15
    }
16
    long long res = 1;
17
    for (int i = 0; i < n; ++i) {
18
        if (i != p) res *= a[i];
19
    }
20
    cout << res * (mn + 1) << endl;
21
    return 0;
22
}

B. 池化(pooling)#

直接模拟。

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

4
using namespace std;
5

6
int main() {
7
    ios::sync_with_stdio(0);
8
    cin.tie(0), cout.tie(0);
9
    int n, k;
10
    cin >> n >> k;
11
    vector<vector<int>> a(n + 1, vector<int>(n + 1));
12
    for (int i = 1; i <= n; ++i) {
13
        for (int j = 1; j <= n; ++j) {
14
            cin >> a[i][j];
15
        }
16
    }
17
    for (int i = k; i <= n; i += k) {
18
        for (int j = k; j <= n; j += k) {
19
            int r = 0;
20
            for (int d1 = 0; d1 < k; ++d1) {
21
                for (int d2 = 0; d2 < k; ++d2) {
22
                    r = max(r, a[i - d1][j - d2]);
23
                }
24
            }
25
            cout << r << ' ';
26
        }
27
        cout << endl;
28
    }
29
    return 0;
30
}

C. 选择排序(select)#

观察他给的样例能总结出规律。

字典序最小的一定是在顺序的基础上，交换第 $k$ 个和第 $k + 1$ 个；
字典序最大的有两种情况
- $k > \lfloor \frac{n}{2} \rfloor$ 一定是在逆序的基础上交换第 $k$ 个和第 $k + 1$ 个；
- 否则在逆序的基础上把 $[k + 1, n - k]$ 正过来。

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

4
using namespace std;
5

6
const int N = 2010;
7
int a[N];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int T;
13
    cin >> T;
14
    while (T--) {
15
        int n, k;
16
        cin >> n >> k;
17
        if (k == 0) {
18
            for (int i = 1; i <= n; ++i) cout << i << ' ';
19
            cout << endl;
20
            for (int i = 1; i <= n; ++i) cout << i << ' ';
21
            cout << endl;
22
        }
23
        else {
24
            for (int i = 1; i <= n; ++i) {
25
                if (i == k) cout << k + 1 << ' ';
26
                else if (i == k + 1) cout << k << ' ';
27
                else cout << i << ' ';
28
            }
29
            cout << endl;
30
            if (k > n / 2)
31
                for (int i = 1; i <= n; ++i) {
32
                    if (i == k) cout << n - k << ' ';
33
                    else if (i == k + 1) cout << n - k + 1 << ' ';
34
                    else cout << n - i + 1 << ' ';
35
                }
36
            else {
37
                for (int i = 1; i <= k; ++i) {
38
                    cout << n - i + 1 << ' ';
39
                }
40
                for (int i = k + 1; i <= n - k; ++i) {
41
                    cout << i << ' ';
42
                }
43
                for (int i = 1; i <= k; ++i) {
44
                    cout << k - i + 1 << ' ';
45
                }
46
            }
47
            cout << endl;
48
        }
49
    }
50
    return 0;
51
}

D. 困难的题目(hard)#

实际上一点也不困难。贪心的想，对于每一个数能覆盖到他的区间全加 w 一定不劣，不能覆盖他的一定是不加。因为 n 很小，用前缀和优化一下暴力处理即可，否则可能要变成一道数据结构题了。

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

6
using namespace std;
7

8
typedef long long LL;
9
const int N = 5010;
10
LL a[N], c[N];
11
bool res[N];
12
vector<tuple<int, int, int>> b[N];
13

14
int main() {
15
    ios::sync_with_stdio(0);
16
    cin.tie(0), cout.tie(0);
17
    int n, m, w;
18
    cin >> n >> m >> w;
19
    for (int i = 1; i <= m; ++i) {
20
        int l, r, v;
21
        cin >> l >> r >> v;
22
        if (~v) a[l] += v, a[r + 1] -= v;
23
        else b[l].emplace_back(l, r, w), b[r + 1].emplace_back(l, r, -w);
24
    }
25
    for (int i = 1; i <= n; ++i) {
26
        a[i] += a[i - 1];
27
    }
28
    for (int i = 1; i <= n; ++i) {
29
        memset(c, 0, sizeof(LL) * (n + 1));
30
        for (auto [l, r, w] : b[i]) {
31
            c[l] += w, c[r + 1] -= w;
32
        }
33
        LL mx = 0;
34
        for (int i = 1; i <= n; ++i) {
35
            c[i] += c[i - 1];
36
            a[i] += c[i];
37
            mx = max(mx, a[i]);
38
        }
39
        if (a[i] == mx) cout << 1;
40
        else cout << 0;
41
    }
42
    cout << endl;
43
    return 0;
44
}

E. 回文(palindrom)#

区间 DP，记 $f_{l, r}$ 为区间 $[l, r]$ 的回文串数量，考虑通过分类讨论区间左右端点的关系统计数量

f_{l, r} = \begin{cases} 1 & l = r\\ f_{l + 1, r} + f_{l, r - 1} + 1 & s_l = s_r\\ f_{l + 1, r} + f_{l, r - 1} - f_{l + 1, r - 1} & else \end{cases}

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

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 5010;
9
const int MOD = 1000000007;
10
LL f[N][N];
11

12
int main() {
13
    ios::sync_with_stdio(0);
14
    cin.tie(0), cout.tie(0);
15
    int T;
16
    cin >> T;
17
    while (T--) {
18
        string s;
19
        cin >> s;
20
        s = " " + s;
21
        int n = s.length() - 1;
22
        // cout << n << endl;
23
        for (int i = 1; i <= n; ++i) {
24
            f[i][i] = 1;
25
        }
26
        for (int i = 1; i < n; ++i) {
27
            f[i][i + 1] = s[i] == s[i + 1] ? 3 : 2;
28
        }
29
        for (int len = 3; len <= n; ++len) {
30
            for (int i = 1; i + len - 1 <= n; ++i) {
31
                int j = i + len - 1;
32
                f[i][j] = ((f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1]) % MOD + MOD) % MOD;
33
                if (s[i] == s[j]) f[i][j] = (f[i][j] + f[i + 1][j - 1] + 1) % MOD;
34
            }
35
        }
36
        cout << f[1][n] << endl;
37
    }
38
    return 0;
39
}

F. Fill the Square#

贪心的给前面填小的一定没问题，又因为有 26 个可选项，但是相邻的最多只有 4 个，后面一定能有可行解，直接暴力就行了。

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

6
using namespace std;
7

8
const int N = 20;
9
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
10
char a[N][N];
11

12
int main() {
13
    ios::sync_with_stdio(0);
14
    cin.tie(0), cout.tie(0);
15
    int T;
16
    cin >> T;
17
    for (int t = 1; t <= T; ++t) {
18
        int n;
19
        cin >> n;
20
        for (int i = 1; i <= n; ++i) cin >> (a[i] + 1);
21
        for (int i = 1; i <= n; ++i) {
22
            for (int j = 1; j <= n; ++j) {
23
                if (isalpha(a[i][j])) continue;
24
                else {
25
                    for (char c = 'A'; c <= 'Z'; ++c) {
26
                        bool f = true;
27
                        for (int d = 0; d < 4; ++d) {
28
                            int tx = i + dx[d], ty = j + dy[d];
29
                            if (a[tx][ty] == c) {
30
                                f = false;
31
                                break;
32
                            }
33
                        }
34
                        if (f) {
35
                            a[i][j] = c;
36
                            break;
37
                        }
38
                    }
39
                }
40
            }
41
        }
42
        cout << "Case " << t << ":" << endl;
43
        for (int i = 1; i <= n; ++i) cout << (a[i] + 1) << endl;
44
    }
45
    return 0;
46
}

G. The Cow Gathering#

H. Disruption#

先建出来树，然后每次将 p 到 q 路径上的所有边和 r 取个 min。可以直接无脑树剖 + 线段树，或者先对 r 排序，之后贪心用并查集维护（每条边只走一次，所以可以暴力走）。

我在默写树剖 + 线段树上取得了 25 min 的好成绩，你也来试试吧～～

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

4
using namespace std;
5

6
const int N = 50010;
7

8
int head[N], ver[N * 2], ne[N * 2], tot = 1;
9
int dep[N], cnt[N], fa[N], son[N];
10
int dfn[N], top[N], t;
11
int tr[N * 4], tag[N * 4];
12
int n, m;
13

14
void add(int x, int y) {
15
    ver[++tot] = y;
16
    ne[tot] = head[x];
17
    head[x] = tot;
18
}
19

20
void dfs1(int x) {
21
    cnt[x] = 1;
22
    for (int i = head[x]; i; i = ne[i]) {
23
        int y = ver[i];
24
        if (y == fa[x]) continue;
25
        dep[y] = dep[x] + 1;
26
        fa[y] = x;
27
        dfs1(y);
28
        if (cnt[y] > cnt[son[x]]) son[x] = y;
29
        cnt[x] += cnt[y];
30
    }
31
}
32

33
void dfs2(int x, int tp) {
34
    top[x] = tp;
35
    dfn[x] = ++t;
36
    if (son[x]) dfs2(son[x], tp);
37
    for (int i = head[x]; i; i = ne[i]) {
38
        int y = ver[i];
39
        if (y == fa[x] || y == son[x]) continue;
40
        dfs2(y, y);
41
    }
42
}
43

44
void pushup(int u) {
45
    tr[u] = min(tr[u << 1], tr[u << 1 | 1]);
46
}
47

48
void pushdown(int u) {
49
    if (tag[u] != 0x3f3f3f3f) {
50
        tag[u << 1] = min(tag[u << 1], tag[u]), tag[u << 1 | 1] = min(tag[u << 1 | 1], tag[u]);
51
        tr[u << 1] = min(tr[u << 1], tag[u]), tr[u << 1 | 1] = min(tr[u << 1 | 1], tag[u]);
52
        tag[u] = 0x3f3f3f3f;
53
    }
54
}
55

56
void modify(int u, int l, int r, int ql, int qr, int v) {
57
    if (ql <= l && r <= qr) {
58
        tr[u] = min(tr[u], v);
59
        tag[u] = min(tag[u], v);
60
    }
61
    else {
62
        int mid = l + r >> 1;
63
        pushdown(u);
64
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
65
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql ,qr, v);
66
        pushup(u);
67
    }
68
}
69

70
int query(int u, int l, int r, int p) {
71
    if (l == r) return tr[u];
72
    else {
73
        int mid = l + r >> 1;
74
        pushdown(u);
75
        if (p <= mid) return query(u << 1, l, mid, p);
76
        else return query(u << 1 | 1, mid + 1, r, p);
77
    }
78
}
79

80
void print(int u, int l, int r) {
81
    if (l == r) cout << tr[u] << ' ';
82
    else {
83
        int mid = l + r >> 1;
84
        pushdown(u);
85
        print(u << 1, l, mid), print(u << 1 | 1, mid + 1, r);
86
    }
87
}
88

89
void modify(int x, int y, int v) {
90
    while (top[x] != top[y]) {
91
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
92
        modify(1, 1, n, dfn[top[x]], dfn[x], v);
93
        x = fa[top[x]];
94
    }
95
    if (dfn[x] == dfn[y]) return;
96
    if (dfn[x] > dfn[y]) swap(x, y);
97
    modify(1, 1, n, dfn[x] + 1, dfn[y], v);
98
}
99

100
int main() {
101
    ios::sync_with_stdio(0);
102
    cin.tie(0), cout.tie(0);
103
    cin >> n >> m;
104
    for (int i = 1; i < n; ++i) {
105
        int x, y;
106
        cin >> x >> y;
107
        add(x, y), add(y, x);
108
    }
109
    dep[1] = 1;
110
    dfs1(1);
111
    dfs2(1, 1);
112
    memset(tr, 0x3f, sizeof(int) * (n * 4));
113
    memset(tag, 0x3f, sizeof(int) * (n * 4));
114
    while (m--) {
115
        int x, y, z;
116
        cin >> x >> y >> z;
117
        modify(x, y, z);
118
        // print(1, 1, n);
119
        // cout << endl;
120
    }
121
    for (int i = 2; i <= tot; i += 2) {
122
        int t = query(1, 1, n, max(dfn[ver[i]], dfn[ver[i ^ 1]]));
123
        cout << (t == 0x3f3f3f3f ? -1 : t) << endl;
124
    }
125
    return 0;
126
}

Star's Blog