2025春训第二十二场

A. 染色#

数据非常小，直接暴力就可以，非常保险。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int l1, r1, l2, r2;
7
    cin >> l1 >> r1 >> l2 >> r2;
8
    int res = 0;
9
    for (int i = 0; i <= 100; ++i) {
10
        if (l1 <= i && i < r2 && l2 <= i && i < r1) {
11
            res++;
12
        }
13
    }
14
    cout << res << endl;
15
    return 0;
16
}

B. 石头称重#

本来很简单的题刚开始被我想复杂了，当然，还有别的因素影响，导致卡了不到一个小时……

其实很简单，因为前面元素的和一定不大于后面的元素，所以情况一共有 $2^n$ 种，而且选后面的无论如何都比任意选前面的大。

这让我想到了二进制，每个数可以看做一个数位，选和不选是 0 和 1，完全满足上面的规律，例如 3(110) 一定小于 4(001)。

因为第一个二进制数是 0，我们令 k = k - 1，这样就完全和二进制对上了，接下来只需要对 k 进行二进制分解把对应的位置加上就是答案。

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

4
using namespace std;
5

6
const int N = 60;
7
long long w[N], s[N], k;
8
int n;
9

10
int main() {
11
    scanf("%d", &n);
12
    for (int i = 1; i <= n; ++i) {
13
        scanf("%lld", &w[i]);
14
        s[i] = s[i - 1] + w[i];
15
    }
16
    scanf("%lld", &k);
17
    if (k > (1ll << n)) printf("-1\n");
18
    else {
19
        k--;
20
        long long res = 0;
21
        for (int i = 0; i < n; ++i) {
22
            if (k >> i & 1) res += w[i + 1];
23
        }
24
        printf("%lld\n", res);
25
    }
26
    return 0;
27
}

C. 字符串#

这道题也有那么一点纸老虎的样子，看着无从下手，但是如果发现了就非常简单。

先考虑极限的情况，再考虑一般情况

区间长度为 2，两个字符必须不同；
区间长度为 3，三个字符必须互不相同；
区间长度为 4，允许一个字符在两端各出现一次；
长度更长的区间如果出现最多的字符间隔都不小于 2 依然是合法的。

得出结论，只要相同字符间隔 ≥ 2 即可。于是就好办了，开一个状态 $f_{i, j, k}$ 表示第 i 个位置选了 j，上一个位置选了 k 的方案数，线性 dp 即可。

一个位置的字符选择受到前两个字符的影响，所以需要同时记录两个状态，这样从 i - 1 到 i 的时候就可以做到不重不漏。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 5010;
6
const int MOD = 998244353;
7

8
char s[N];
9
int cnt[N];
10
long long f[N][27][27];
11

12
int main() {
13
    int n;
14
    scanf("%d", &n);
15
    scanf("%s", s + 1);
16
    f[0][26][26] = 1; // 用了一种不可能的情况表示边界，这种情况会在 i = 3 的时候消失
17
    for (int i = 1; i <= n; ++i) {
18
        if (s[i] != '?') {
19
            int t = s[i] - 'a';
20
            for (int j = 0; j <= 26; ++j) {
21
                for (int k = 0; k <= 26; ++k) {
22
                    if (j == t || k == t) continue;
23
                    f[i][t][j] += f[i - 1][j][k];
24
                    f[i][t][j] %= MOD;
25
                }
26
            }
27
        }
28
        else {
29
            for (int t = 0; t < 26; ++t) {
30
                for (int j = 0; j <= 26; ++j) {
31
                    for (int k = 0; k <= 26; ++k) {
32
                        if (j == t || k == t) continue;
33
                        f[i][t][j] += f[i - 1][j][k];
34
                        f[i][t][j] %= MOD;
35
                    }
36
                }
37
            }
38
        }
39
    }
40
    long long res = 0;
41
    for (int i = 0; i <= 26; ++i) {
42
        for (int j = 0; j <= 26; ++j) {
43
            res = (res + f[n][i][j]) % MOD;
44
        }
45
    }
46
    printf("%lld\n", res);
47
    return 0;
48
}

D. 喵喵#

这道题相对简单一点（因为虽然流程有点麻烦，但是一看容易看出来办法）

求一下最短路同时记录编号最小的前驱，结束后从 1 号开始沿着记录的最短路的逆路径跑 dfs，在搜索树上树形 dp 统计答案即可。

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

7
using namespace std;
8

9
const int N = 10010;
10

11
vector<pair<int, int>> ed[N];
12
int a[N], dis[N], pre[N], t;
13
long long res;
14
bool vis[N];
15

16
void dijkstra() {
17
    memset(dis, 0x3f, sizeof(dis));
18
    priority_queue<pair<int, int>> q;
19
    dis[1] = 0;
20
    q.push({0, 1});
21
    while (!q.empty()) {
22
        int x = q.top().second;
23
        q.pop();
24
        if (vis[x]) continue;
25
        vis[x] = true;
26
        for (auto [i, y] : ed[x]) {
27
            if (dis[y] > dis[x] + i) {
28
                dis[y] = dis[x] + i;
29
                pre[y] = x;
30
                q.push({-dis[y], y});
31
            }
32
            else if (dis[y] == dis[x] + i) {
33
                pre[y] = min(pre[y], x);
34
            }
35
        }
36
    }
37
}
38

39
void dfs(int x, int l) {
40
    if (vis[x]) return;
41
    vis[x] = true;
42
    for (auto [i, y] : ed[x]) {
43
        if (vis[y]) continue;
44
        if (x == pre[y]) {
45
            dfs(y, l + i);
46
            a[x] += a[y];
47
        }
48
    }
49
    res = max(res, (long long)a[x] * (l - t));
50
}
51

52
int main() {
53
    int n, m;
54
    scanf("%d%d%d", &n, &m, &t);
55
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
56
    for (int i = 1; i <= m; ++i) {
57
        int x, y, z;
58
        scanf("%d%d%d", &x, &y, &z);
59
        ed[x].push_back({z, y});
60
        ed[y].push_back({z, x});
61
    }
62
    dijkstra();
63
    memset(vis, 0, sizeof(vis));
64
    for (int i = 1; i <= n; ++i) {
65
        sort(ed[i].begin(), ed[i].end(), [](pair<int, int> a, pair<int, int> b) {
66
            return a.second < b.second;
67
        });
68
    }
69
    dfs(1, 0);
70
    printf("%lld\n", res);
71
    return 0;
72
}

E. 变量定义#

比较水，没什么好说的，按要求做就行。

1
keys = ["include", "using", "namespace", "return", "main", "int", "float", "double", "string", "char"]
2
n = int(input().strip())
3

4
def check(s: str):
5
    if s in keys:
6
        return 'No'
7
    if s[0] == '_' or s[0].isalpha():
8
        for c in s:
9
            if c != '_' and not c.isalnum():
10
                return 'No'
11
        return 'Yes'
12
    else:
13
        return 'No'
14

15
for _ in range(n):
16
    s = input()
17
    print(check(s.strip()))

F. 跳远比赛#

我因为 check 函数写挂 $\textcolor{green}{+11}$ ……

典型的二分答案题，二分最大值，贪心验证即可。具体的，验证的时候应该贪心的取尽可能最左边的点，给后的选择留更多的余地，感性上这是正确的（事实上也是正确的）。

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

4
using namespace std;
5

6
const int N = 100010;
7
const long long MAXN = 1000000000000000000;
8
typedef long long LL;
9
pair<LL, LL> a[N];
10
int n, m;
11

12
bool check(LL mid) {
13
    if (mid == 0) return true;
14
    LL cnt = 0, ls = -MAXN;
15
    for (int i = 1; i <= m; ++i) {
16
        // 这里的判断逻辑很容易挂，别问我怎么知道的
17
        if (ls + mid > a[i].second) continue;
18
        if (a[i].first - ls < mid) ls = ls + mid;
19
        else ls = a[i].first;
20
        cnt += (a[i].second - ls) / mid + 1;
21
        ls += (a[i].second - ls) / mid * mid;
22
    }
23
    return cnt >= n;
24
}
25

26
int main() {
27
    scanf("%d%d", &n, &m);
28
    for (int i = 1; i <= m; ++i) {
29
        scanf("%lld%lld", &a[i].first, &a[i].second);
30
    }
31
    sort(a + 1, a + m + 1);
32
    LL l = 0, r = MAXN;
33
    while (l < r) {
34
        LL mid = (l + r + 1) >> 1;
35
        if (check(mid)) l = mid;
36
        else r = mid - 1;
37
    }
38
    printf("%lld\n", l);
39
    return 0;
40
}

G. 宝藏#

这道题也很简单，看着像是个图论，实际上是个二维 dp，图都不用建出来。记 $f_{i, j}$ 表示走到 i 点用了 j 体力的时宝藏价值的最大值。 $f_{i, 0}$ 其实就是 i 山洞领一次的宝藏价值。更新状态时从低到高枚举 j，对于每一个 j 枚举所有边

f_{y, j} = \max\{{f_{y, j}, f_{x, j - w} + A_y}\}

把所有的 f 取 max 可以。

1
#include <iostream>
2

3
using namespace std;
4

5
const int M = 10010;
6
const int N = 1010;
7
struct ed {
8
    int x, y, z;
9
} ed[M];
10
int f[N][510];
11

12
int main() {
13
    int res = 0;
14
    int n, m, t;
15
    scanf("%d%d%d", &n, &m, &t);
16
    for (int i = 1; i <= n; ++i) scanf("%d", &f[i][0]);
17
    for (int i = 1; i <= m; ++i) scanf("%d%d%d", &ed[i].x, &ed[i].y, &ed[i].z);
18
    for (int i = 1; i <= t; ++i) {
19
        for (int j = 1; j <= m; ++j) {
20
            auto &[x, y, z] = ed[j];
21
            if (i >= z) {
22
                f[y][i] = max(f[y][i], f[x][i - z] + f[y][0]);
23
                res = max(res, f[y][i]);
24
            }
25
        }
26
    }
27
    printf("%d\n", res);
28
    return 0;
29
}

Star's Blog