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

A. 扫雷I#

按要求模拟就行，需要注意点不是 0 的格子视为无效操作。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 60;
6
int a[N][N];
7

8
int main() {
9
    int n, cnt = 0;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        for (int j = 1; j <= n; ++j) {
13
            scanf("%d", &a[i][j]);
14
            cnt += a[i][j];
15
        }
16
    }
17
    int x, y;
18
    while (scanf("%d%d", &x, &y), x) {
19
        if (a[x][y] == 1) {
20
            printf("GAME OVER!\n");
21
            return 0;
22
        }
23
        else if (a[x][y]) continue;
24
        for (int i = x - 1; i <= x + 1; ++i) {
25
            for (int j = y - 1; j <= y + 1; ++j) {
26
                if (a[i][j] == 0) a[i][j] = -1;
27
                else if (a[i][j] == 1) cnt--, a[i][j] = -2;
28
            }
29
        }
30
        if (!cnt) {
31
            printf("YOU ARE WINNER!\n");
32
            return 0;
33
        }
34
    }
35
    for (int i = 1; i <= n; ++i) {
36
        for (int j = 1; j <= n; ++j) {
37
            printf("%d ", a[i][j]);
38
        }
39
        printf("\n");
40
    }
41
    return 0;
42
}

B. 无根树#

如果数据大的话需要换根 dp，对每个点需要维护子树高度的最大值和次大值，换根时如果换到了最大值的那条链就用次大值，否则用最大值。

他数据范围很小，所以直接暴力以每个点为根 dp 一遍就可以了。

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

5
using namespace std;
6

7
const int N = 1010;
8
vector<int> ed[N];
9
int f[N];
10

11
void dp(int x, int fa) {
12
    for (int y : ed[x]) {
13
        if (y == fa) continue;
14
        f[y] = f[x] + 1;
15
        dp(y, x);
16
    }
17
    for (int y : ed[x]) {
18
        if (y == fa) continue;
19
        f[x] = max(f[x], f[y]);
20
    }
21
}
22

23
int main() {
24
    int n;
25
    scanf("%d", &n);
26
    for (int i = 1; i < n; ++i) {
27
        int x, y;
28
        scanf("%d%d", &x, &y);
29
        ed[x].push_back(y);
30
        ed[y].push_back(x);
31
    }
32
    for (int i = 1; i <= n; ++i) {
33
        // 数据太小直接暴力
34
        f[i] = 1;
35
        dp(i, 0);
36
        printf("%d\n", f[i]);
37
    }
38
    return 0;
39
}

C. 积木#

$n \le 10^9$ 所以 $\sqrt[3]{n} \le 10^3$ ，直接暴力枚举因式就可以。

~~为什么我当时还在拉格朗日乘数法求条件极值😭~~

1
#include <iostream>
2
#include <climits>
3
using namespace std;
4
typedef long long LL;
5

6
int main() {
7
    LL n;
8
    cin >> n;
9
    LL minv = LLONG_MAX, maxv = LLONG_MIN;
10
    for (LL x = 1; x * x * x <= n; ++x) {
11
        if (n % x != 0) continue;
12
        LL yz = n / x;
13
        for (LL y = 1; y * y <= yz; ++y) {
14
            if (yz % y != 0) continue;
15
            LL z = yz / y;
16
            LL A1 = x + 1, B1 = y + 2, C1 = z + 2;
17
            LL A2 = x + 1, B2 = z + 2, C2 = y + 2;
18
            LL A3 = y + 1, B3 = x + 2, C3 = z + 2;
19
            LL A4 = y + 1, B4 = z + 2, C4 = x + 2;
20
            LL A5 = z + 1, B5 = x + 2, C5 = y + 2;
21
            LL A6 = z + 1, B6 = y + 2, C6 = x + 2;
22
            LL vals[6] = {
23
                A1 * B1 * C1 - n,
24
                A2 * B2 * C2 - n,
25
                A3 * B3 * C3 - n,
26
                A4 * B4 * C4 - n,
27
                A5 * B5 * C5 - n,
28
                A6 * B6 * C6 - n
29
            };
30
            for (int i = 0; i < 6; ++i) {
31
                if (vals[i] < minv) minv = vals[i];
32
                if (vals[i] > maxv) maxv = vals[i];
33
            }
34
        }
35
    }
36
    cout << minv << ' ' << maxv << endl;
37
    return 0;
38
}

D. 幸运数III#

10 位的幸运数只有 $2^10 = 1024$ 个，所以直接暴力枚举所有的幸运数就可以解决问题。

1
#include <iostream>
2

3
using namespace std;
4

5
long long calc(int x) {
6
    if (!x) return 0;
7
    long long pre = 0, res = 0;
8
    for (int i = 1; i <= 10; ++i) {
9
        for (int mask = 0; mask < (1 << i); ++mask) {
10
            long long val = 0;
11
            for (int j = 0; j < i; ++j) {
12
                if (mask >> j & 1) val = val * 10 + 7;
13
                else val = val * 10 + 4;
14
            }
15
            if (x > val) res += val * (val - pre);
16
            else return (x - pre) * val + res;
17
            pre = val;
18
        }
19
    }
20
    return res;
21
}
22

23
int main() {
24
    int l, r;
25
    scanf("%d%d", &l, &r);
26
    printf("%lld\n", calc(r) - calc(l - 1)); // 用差分的思想可以简化左边界的处理
27
    return 0;
28
}

E. Run#

线性 dp，需要另外开一个状态表示上一次是否 run，其他的就和经典的爬楼梯问题完全一样了。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 100010;
6
const int MOD = 1000000007;
7
long long f[N][2], s[N];
8

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

G. Money#

最大的 profit 一定是能赚的都赚了，所以对于所有单调递增的子段都在开头买了在结尾卖了即可，这样能在保证最大 profit 的同时减少操作次数。

1
#include <iostream>
2

3
using namespace std;
4
const int N = 100010;
5
int a[N];
6

7
int main() {
8
    int T;
9
    scanf("%d", &T);
10
    while (T--) {
11
        int n, cnt = 0;
12
        long long res = 0;
13
        scanf("%d", &n);
14
        for (int i = 1; i <= n; ++i) {
15
            scanf("%d", &a[i]);
16
        }
17
        a[n + 1] = -11111;
18
        for (int l = 1, r = 1; r <= n; ++r) {
19
            if (a[r] <= a[r + 1]) continue;
20
            else {
21
                if (a[r] > a[l]) {
22
                    cnt++;
23
                    res += a[r] - a[l];
24
                }
25
                l = r + 1;
26
            }
27
        }
28
        printf("%lld %d\n", res, cnt * 2);
29
    }
30
    return 0;
31
}

Star's Blog