2025年夏季个人训练赛第七场

A. 气球（balloon）#

好在 k 只有 100，直接 dp 就可以解决， $f_{i, j, k}$ 表示第 i 个气球颜色为 j 颜色和上一个 (不 if k == 0) 一样的方案数。

1
#include <iostream>
2

3
using namespace std;
4

5
const int MOD = 1000000007;
6
const int N = 100010;
7

8
long long f[N][110][2], s[N];
9

10
int main() {
11
    int n, k;
12
    scanf("%d%d", &n, &k);
13
    s[0] = 1;
14
    for (int i = 1; i <= n; ++i) {
15
        for (int j = 1; j <= k; ++j) {
16
            f[i][j][0] = ((s[i - 1] - f[i - 1][j][1] - f[i - 1][j][0]) % MOD + MOD) % MOD;
17
            f[i][j][1] = f[i - 1][j][0];
18
            s[i] = (s[i] + f[i][j][0] + f[i][j][1]) % MOD;
19
        }
20
    }
21
    printf("%lld\n", s[n]);
22
    return 0;
23
}

B. 机器人（robot）#

每次改就只会被改的那条点后面的路径，先 dp 一遍预处理出来经过每个位置的机器人个数，每次修改的时候顺着原来那条链全减掉然后再顺着新的链全加回去，全部重新取 max，并不会 TLE。

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

4
using namespace std;
5

6
const int N = 1510;
7

8
char mp[N][N];
9
int f[N][N], deg[N][N], value[N][2]; // 0 是右 1 是下
10

11
void calc(int n) {
12
    int res = 0;
13
    for (int i = 1; i <= n; ++i) {
14
        res = max(res, max(f[i][n + 1] * value[i][0], f[n + 1][i] * value[i][1]));
15
    }
16
    printf("%d\n", res);
17
}
18

19
int main() {
20
    int n;
21
    scanf("%d", &n);
22
    for (int i = 1; i <= n; ++i) {
23
        scanf("%s%d", mp[i] + 1, &value[i][0]);
24
        for (int j = 1; j <= n; ++j) {
25
            if (mp[i][j] == 'R') deg[i][j + 1]++;
26
            else deg[i + 1][j]++;
27
        }
28
    }
29
    for (int i = 1; i <= n; ++i) {
30
        scanf("%d", &value[i][1]);
31
    }
32
    for (int i = 1; i <= n + 1; ++i) {
33
        for (int j = 1; j <= n + 1; ++j) {
34
            if (i <= n && j <= n) f[i][j] = 1;
35
            if (mp[i - 1][j] == 'D') f[i][j] += f[i - 1][j];
36
            if (mp[i][j - 1] == 'R') f[i][j] += f[i][j - 1];
37
        }
38
    }
39
    calc(n);
40
    int q;
41
    scanf("%d", &q);
42
    while (q--) {
43
        int x, y;
44
        scanf("%d%d", &x, &y);
45
        int t = f[x][y];
46
        int i = x, j = y;
47
        while (i <= n && j <= n) {
48
            if (mp[i][j] == 'R') {
49
                j++;
50
                f[i][j] -= t;
51
            }
52
            else if (mp[i][j] == 'D') {
53
                i++;
54
                f[i][j] -= t;
55
            }
56
        }
57
        i = x, j = y;
58
        mp[i][j] = mp[i][j] == 'R' ? 'D' : 'R';
59
        while (i <= n && j <= n) {
60
            if (mp[i][j] == 'R') {
61
                j++;
62
                f[i][j] += t;
63
            }
64
            else if (mp[i][j] == 'D') {
65
                i++;
66
                f[i][j] += t;
67
            }
68
        }
69
        calc(n);
70
    }
71
    return 0;
72
}

C. 积木大赛（blocks）#

按 a + b 排序， $f_{i, j}$ 表示选到第 i 个积木，重量为 j 的最大高度，按照背包的思路 dp 即可。

why? 其实我做的时候是蒙出来的。

本质上就是考虑相邻的两个积木互相摞的可能性。如果两个积木互换位置都能摞上，那顺序就不影响了；如果只有一种能摞上那一定是 a + b 小的在上面。所以按照 a + b 从小到大排序没问题。

\begin{align} &a_1 + b_1 < a_2 + b_2\\ &\begin{cases} a_2 \le b_1 \rArr a_1 < b_2\\ a_1 \le b_2 \rArr \text{不确定} \end{cases} \end{align}

1
#include <iostream>
2
#include <algorithm>
3
#define int long long
4

5
using namespace std;
6

7
const int N = 1010;
8
struct wood {
9
    int a, b, c;
10
} a[N];
11
long long f[N][20010];
12

13
signed main() {
14
    int n;
15
    scanf("%lld", &n);
16
    for (int i = 1; i <= n; ++i) {
17
        scanf("%lld%lld%lld", &a[i].a, &a[i].b, &a[i].c);
18
    }
19
    sort(a + 1, a + n + 1, [](wood a, wood b) {
20
        return a.a + a.b < b.a + b.b;
21
    });
22
    for (int i = 1; i <= n; ++i) {
23
        for (int j = 0; j <= 20000; ++j) {
24
            if (j >= a[i].a && j - a[i].a <= a[i].b) f[i][j] = max(f[i - 1][j], f[i - 1][j - a[i].a] + a[i].c);
25
            else f[i][j] = f[i - 1][j];
26
        }
27
    }
28
    long long res = 0;
29
    for (int i = 0; i <= 20000; ++i) {
30
        res = max(res, f[n][i]);
31
    }
32
    printf("%lld\n", res);
33
    return 0;
34
}

D. Positioning Peter’s Paintings#

签到题。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    long long a, b, x, y;
7
    cin >> a >> b >> x >> y;
8
    cout << min(max(a, x) + (b + y), max(b, y) + (a + x)) * 2 << endl;
9
    return 0;
10
}

E. Cryptogram Cracking Club#

水题++

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0);
8
    string s;
9
    long long n, sum = 0, cur = 0;
10
    cin >> s >> n;
11
    for (char c : s) {
12
        if (isdigit(c)) cur = cur * 10 + c - 48;
13
        else {
14
            sum += cur;
15
            cur = 0;
16
            if (sum > n) break;
17
        }
18
    }
19
    sum += cur;
20
    cur = 0;
21
    n %= sum;
22
    n++;
23
    char ls;
24
    sum = 0;
25
    for (char c : s) {
26
        if (isdigit(c)) cur = cur * 10 + c - 48;
27
        else {
28
            sum += cur;
29
            cur = 0;
30
            if (sum >= n) {
31
                cout << ls << endl;
32
                break;
33
            }
34
            ls = c;
35
        }
36
    }
37
    if (sum < n) cout << ls << endl;
38
    return 0;
39
}

G. Floor is Lava#

洛谷链接

太巧妙了，把边当点，对新图跑一遍最短路。

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

8
using namespace std;
9

10
typedef long long LL;
11
const int N = 200010;
12

13
vector<tuple<int, int, int>> ed[N];
14
vector<pair<int, int>> newed[N];
15
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> q;
16
LL dis[N];
17
bool vis[N];
18

19
int main() {
20
    int n, m;
21
    scanf("%d%d", &n, &m);
22
    for (int i = 1; i <= m; ++i) {
23
        int x, y, w;
24
        scanf("%d%d%d", &x, &y, &w);
25
        ed[x].push_back({w, y, i});
26
        ed[y].push_back({w, x, i});
27
    }
28
    for (int i = 1; i <= n; ++i) {
29
        sort(ed[i].begin(), ed[i].end());
30
        for (int j = 1; j < ed[i].size(); ++j) {
31
            auto [a, b, c] = ed[i][j - 1];
32
            auto [d, e, f] = ed[i][j];
33
            newed[c].push_back({d - a, f});
34
            newed[f].push_back({d - a, c});
35
        }
36
    }
37
    for (auto [a, b, c] : ed[1]) newed[0].push_back({a, c});
38
    for (auto [a, b, c] : ed[n]) newed[c].push_back({0, m + 1});
39
    memset(dis, 0x3f, sizeof(dis));
40
    dis[0] = 0;
41
    q.push({dis[0], 0});
42
    while (!q.empty()) {
43
        int x = q.top().second;
44
        q.pop();
45
        if (vis[x]) continue;
46
        vis[x] = true;
47
        for (auto [w, y] : newed[x]) {
48
            if (dis[y] > dis[x] + w) {
49
                dis[y] = dis[x] + w;
50
                q.push({dis[y], y});
51
            }
52
        }
53
    }
54
    printf("%lld\n", dis[m + 1]);
55
    return 0;
56
}

Star's Blog