2025春训第二十场

第一场打完觉的非常水，于是第二场立刻就被真实了，已老实求放过😇😇😇。

A. 舞蹈机器人#

熟悉的情况，熟悉的打表（

打表

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

4
using namespace std;
5

6
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
7
set<pair<int, int>> s;
8

9
void dfs(int x, int y, int dep, int lim, bool f) {
10
    if (dep == lim) {
11
        s.insert({x, y});
12
        return;
13
    }
14
    for (int i = f; i < 4; i += 2) {
15
        dfs(x + dx[i], y + dy[i], dep + 1, lim, f ^ 1);
16
    }
17
}
18

19
int main() {
20
    int n = 50;
21
    for (int i = 1; i <= 20; ++i) {
22
        s.clear();
23
        dfs(0, 0, 0, i, 0);
24
        dfs(0, 0, 0, i, 1);
25
        cout << s.size() << endl;
26
    }
27
    cout << endl;
28
    return 0;
29
}
30

31
/*
32
4 12 24 40 60 84 112
33
4  8 12 16 20 24 28
34
1  2  3  4  5  6  7
35

36
4 * n * (n - 1) / 2
37
*/

AC 代码

1
n = int(input())
2
if n & 1:
3
    n = (n + 1) // 2
4
    print(n * (n + 1) * 2)
5
else:
6
    n = n // 2 + 1
7
    print(n * n)

B. 狗是啥呀#

这道比较简单一点，找一个单次伤害最大的作为最后一击，前面的找一个净伤害最高的一直打即可。

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

4
using namespace std;
5

6
int main() {
7
    int n;
8
    long long x, mxd = LLONG_MIN, mxk = 0;
9
    cin >> n >> x;
10
    for (int i = 1; i <= n; ++i) {
11
        long long d, h;
12
        cin >> d >> h;
13
        mxk = max(mxk, d);
14
        mxd = max(mxd, d - h);
15
    }
16
    if (x <= mxk) cout << 1 << endl;
17
    else if (mxd <= 0) cout << -1 << endl;
18
    else cout << 1 + (x - mxk + mxd - 1) / mxd << endl;
19
    return 0;
20
}

C. 枢纽#

看到这道题我直接就想到了点双联通分量缩点，于是写缩点写挂了（-14）……

事实上只有一组查询，完全可以暴力解决，从 a 出发搜索，经过 b 就直接 return 把搜到的点打上标记；同理从 b 出发打标记。如此，所有的点被分成三大区。

如果一个点两个标记都存在，表明他可以只经过 a 或者 b 到其他任何点，否则不能；
如果只有 a 或者 b 的标记，这两块点之间必须经过 a 和 b 才行。

所以答案是只被 a 标记的点个数 * 只被 b 标记的点个数。

优雅的做法

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

4
using namespace std;
5

6
const int N = 200010, M = 1000010;
7

8
int head[N], ver[M], ne[M], tot = 1;
9
bool vis[N][2];
10

11
void add(int x, int y) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
}
16

17
void dfs(int x, bool f, int t) {
18
    if (vis[x][f] || x == t) return;
19
    vis[x][f] = true;
20
    for (int i = head[x]; i; i = ne[i]) {
21
        int y = ver[i];
22
        dfs(y, f, t);
23
    }
24
}
25

26
int main() {
27
    int n, m, a, b;
28
    scanf("%d%d%d%d", &n, &m, &a, &b);
29
    for (int i = 1; i <= m; ++i) {
30
        int x, y;
31
        scanf("%d%d", &x, &y);
32
        add(x, y), add(y, x);
33
    }
34
    dfs(a, 0, b);
35
    dfs(b, 1, a);
36
    int t1 = 0, t2 = 0;
37
    for (int i = 1; i <= n; ++i) {
38
        if (vis[i][0] && !vis[i][1]) t1++;
39
        else if (vis[i][1] && !vis[i][0]) t2++;
40
    }
41
    t1--, t2--;
42
    printf("%lld\n", (long long)t1 * t2);
43
    return 0;
44
}

丑陋的做法（缩点）

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

6
using namespace std;
7

8
const int N = 200010, M = 1000010;
9

10
set<pair<int, int>> s;
11
int head[N], ver[M], ne[M], tot = 1;
12
int dfn[N], low[N], t;
13
int bcc_id[N], bcc_siz[N * 2], bcc_cnt;
14
bool cut[N];
15
vector<int> ed[N * 2], bcc[N];
16
stack<int> st;
17
int fa[N * 2], dep[N * 2];
18

19
void add(int x, int y) {
20
    ver[++tot] = y;
21
    ne[tot] = head[x];
22
    head[x] = tot;
23
}
24

25
void tarjan(int x, int from) {
26
    dfn[x] = low[x] = ++t;
27
    st.push(x);
28
    int cnt = 0;
29
    for (int i = head[x]; i; i = ne[i]) {
30
        if (i == (from ^ 1)) continue;
31
        int y = ver[i];
32
        if (!dfn[y]) {
33
            tarjan(y, i);
34
            low[x] = min(low[x], low[y]);
35
            if (dfn[x] <= low[y]) {
36
                cnt++;
37
                if (x != 1 || cnt > 1) cut[x] = true;
38
                bcc_cnt++;
39
                int tp;
40
                do {
41
                    tp = st.top();
42
                    st.pop();
43
                    bcc_id[tp] = bcc_cnt;
44
                    bcc_siz[bcc_cnt]++;
45
                    bcc[bcc_cnt].push_back(tp);
46
                } while (tp != y);
47
                bcc_siz[bcc_cnt]++;
48
                bcc[bcc_cnt].push_back(x);
49
            }
50
        }
51
        else low[x] = min(low[x], dfn[y]);
52
    }
53
}
54

55
void dfs(int x) {
56
    for (int y : ed[x]) {
57
        if (y == fa[x]) continue;
58
        fa[y] = x;
59
        dep[y] = dep[x] + 1;
60
        dfs(y);
61
        bcc_siz[x] += bcc_siz[y];
62
    }
63
}
64

65
int check(int x, int y) {
66
    while (x) {
67
        if (fa[x] == y) return x;
68
        x = fa[x];
69
    }
70
    return 0;
71
}
72

73
int main() {
74
    int n, m, a, b;
75
    scanf("%d%d%d%d", &n, &m, &a, &b);
76
    for (int i = 1; i <= m; ++i) {
77
        int x, y;
78
        scanf("%d%d", &x, &y);
79
        if (x == y) continue;
80
        if (x > y) swap(x, y);
81
        if (s.find({x, y}) != s.end()) continue;
82
        s.insert({x, y});
83
        add(x, y), add(y, x);
84
    }
85
    tarjan(1, 0);
86
    for (int i = 1; i <= n; ++i) {
87
        if (cut[i]) {
88
            bcc_id[i] = ++bcc_cnt;
89
            bcc_siz[bcc_cnt] = 1;
90
        }
91
    }
92
    for (int i = 1; i <= bcc_cnt; ++i) {
93
        if (!bcc[i].empty()) {
94
            for (int x : bcc[i]) {
95
                if (cut[x]) {
96
                    bcc_siz[i]--;
97
                    ed[bcc_id[x]].push_back(i);
98
                    ed[i].push_back(bcc_id[x]);
99
                }
100
            }
101
        }
102
        else break;
103
    }
104
    if (!cut[a] || !cut[b]) {
105
        printf("0\n");
106
    }
107
    else {
108
        dfs(1);
109
        int x = bcc_id[a], y = bcc_id[b];
110
        if (dep[x] > dep[y]) swap(x, y);
111
        int f = check(y, x);
112
        if (f) { // x 是 y 的祖先
113
            printf("%lld\n", (long long)(n - bcc_siz[f] - 1) * (bcc_siz[y] - 1));
114
        }
115
        else {
116
            printf("%lld\n", (long long)(bcc_siz[x] - 1) * (bcc_siz[y] - 1));
117
        }
118
    }
119
    return 0;
120
}

D. 魔法药水#

这是一道 dp 题。

n ≤ 100，意味着每秒递增的魔力值只会是 1 ~ 100 之间的整数。枚举选择的瓶数 t，维护一个状态 $f_{i, j, k}$ 表示前 i 瓶药水选了 j 瓶，魔力值之和对 t 的余数为 k 时魔力值的最大值。对于每一个 t，如果存在状态 $f_{n, t, m \% t}$ ，就尝试用这个状态更新答案。

需要特别注意对每一个 t 是否存在合法的最终状态。

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

4
using namespace std;
5

6
long long f[110][110][110], a[110];
7

8
int main() {
9
    int n;
10
    long long m, res;
11
    cin >> n >> m;
12
    res = m;
13
    for (int i = 1; i <= n; ++i) {
14
        cin >> a[i];
15
    }
16
    for (int t = 1; t <= n; ++t) {
17
        memset(f, -1, sizeof(f));
18
        f[0][0][0] = 0;
19
        for (int i = 1; i <= n; ++i) {
20
            f[i][0][0] = 0;
21
            // i 个 药水
22
            for (int j = 1; j <= t; ++j) {
23
                // 选了 j 个
24
                for (int k = 0; k < t; ++k) {
25
                    // 余数是 k
26
                    f[i][j][k] = f[i - 1][j][k];
27
                    if (~f[i - 1][j - 1][((k - a[i]) % t + t) % t])
28
                        f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][((k - a[i]) % t + t) % t] + a[i]);
29
                }
30
            }
31
        }
32
        if (~f[n][t][m % t]) res = min(res, (m - f[n][t][m % t]) / t);
33
    }
34
    cout << res << endl;
35
    return 0;
36
}

Star's Blog

A. 舞蹈机器人#

B. 狗是啥呀#

C. 枢纽#

D. 魔法药水#