2025春训第十九场

A. 熊孩子打卡#

一道比较水的签到题，因为数据不算太大，直接开 map 统计就可以。

1
#include <cstdio>
2
#include <map>
3

4
using namespace std;
5

6
map<int, int> mp;
7

8
int main() {
9
    int n, res = 0, ls = __INT_MAX__; // 数据肯定到不了 __INT_MAX__
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        int t;
13
        scanf("%d", &t);
14
        if (ls == t) continue;
15
        else {
16
            mp[t]++;
17
            ls = t;
18
            res++;
19
        }
20
    }
21
    for (auto [a, b]: mp) {
22
        printf("%d %d\n", a, b);
23
    }
24
    return 0;
25
}

B. 最省力整理法#

不管怎么换最后体力应该是一样的，因为数据比较小，所以直接冒泡排序就可以。

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

4
using namespace std;
5

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

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

C. 穿心咒#

这是高中题，两圆的位置关系有内含、内切、相交、外切、外离，分别对应 0、1、2、1、0，根据圆心的距离和半径的关系判断即可。

1
#include <iostream>
2

3
using namespace std;
4

5
int p(int x) {
6
    return x * x;
7
}
8

9
int main() {
10
    int T;
11
    scanf("%d", &T);
12
    while (T--) {
13
        int x1, y1, r1, x2, y2, r2;
14
        scanf("%d%d%d%d%d%d", &x1, &y1, &r1, &x2, &y2, &r2);
15
        if (x1 == x2 && y1 == y2 && r1 == r2) printf("-1\n");
16
        else if (p(x1 - x2) + p(y1 - y2) > p(r1 + r2) || p(x1 - x2) + p(y1 - y2) < p(r1 - r2)) printf("0\n");
17
        else if (p(x1 - x2) + p(y1 - y2) == p(r1 + r2) || p(x1 - x2) + p(y1 - y2) == p(r1 - r2)) printf("1\n");
18
        else printf("2\n");
19
    }
20
    return 0;
21
}

D. 吃火锅#

之前某次训练赛的 A 题。

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

6
using namespace std;
7

8
const int N = 510;
9
const int M = 250010;
10
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
11
int a[N][N], n;
12
vector<int> ed[M];
13
int deg[M], f[M];
14

15
int calc(int x, int y) {
16
    return (x - 1) * n + y;
17
}
18

19
int main() {
20
    scanf("%d", &n);
21
    for (int i = 1; i <= n; ++i) {
22
        for (int j = 1; j <= n; ++j) {
23
            scanf("%d", &a[i][j]);
24
        }
25
    }
26
    for (int i = 1; i <= n; ++i) {
27
        for (int j = 1; j <= n; ++j) {
28
            for (int k = 0; k < 4; ++k) {
29
                int x = i + dx[k], y = j + dy[k];
30
                if (x > 0 && x <= n && y > 0 && y <= n && a[i][j] < a[x][y]) {
31
                    ed[calc(i, j)].push_back(calc(x, y));
32
                    deg[calc(x, y)]++;
33
                }
34
            }
35
        }
36
    }
37
    queue<int> q;
38
    for (int i = 1; i <= n * n; ++i) {
39
        if (deg[i] == 0) q.push(i), f[i] = 1;
40
    }
41
    while (!q.empty()) {
42
        int x = q.front();
43
        q.pop();
44
        for (int y : ed[x]) {
45
            f[y] = max(f[y], f[x] + 1);
46
            if (--deg[y] == 0) q.push(y);
47
        }
48
    }
49
    int res = 0;
50
    for (int i = 1; i <= n * n; ++i) {
51
        res = max(res, f[i]);
52
    }
53
    printf("%d\n", res);
54
    return 0;
55
}

E. 套路比赛#

可以用分块来做，把 $n$ 个数按照除以 $\lfloor \sqrt n \rfloor$ 的余数分成 $\lceil \sqrt n \rceil$ 块。

第 i 轮淘汰，需要找 $m\ \text{mod}\ (n - i)$ 个人，如果为零，就赋值成 n - i，我们把这个人数记为 t；
每次淘汰先从当前的人所在的块内开始暴力遍历，遇到未被淘汰的就 t -= 1；
如果成功在块内找到了下一个被淘汰的（t == 0），标记上，并把当前块的计数 - 1，进行下一轮淘汰；
否则按块遍历，t -= 块内剩余的人数（这个值可以预先维护好），直到某个块内剩余的人数比 t 多，暴力遍历该块，直到 t == 0，淘汰掉这个人。
以此类推，执行 n - 1 次，剩下的人就是答案。

1
/*
2
我这里把下标统一往前移了一位，为了方便取模
3
*/
4
#include <iostream>
5
#include <cmath>
6

7
using namespace std;
8

9
bool f[100010];
10
int siz[333];
11

12
int main() {
13
    int n, m;
14
    scanf("%d%d", &n, &m);
15
    int L = sqrt(n), cnt = n / L;
16
    for (int i = 0; i < n; ++i) {
17
        f[i] = true;
18
        siz[i / L]++;
19
    }
20
    int cur = 0;
21
    for (int i = 1; i < n; ++i) {
22
        int t = m % (n - i + 1), cur_bk = cur / L;
23
        if (!t) t = n - i + 1;
24
        while (cur / L == cur_bk && t) {
25
            t -= f[cur];
26
            cur++;
27
            cur %= n;
28
        }
29
        if (!t) {
30
            int tt = (cur - 1 + n) % n;
31
            f[tt] = false;
32
            siz[tt / L]--;
33
        }
34
        else {
35
            cur_bk = cur / L;
36
            while (siz[cur_bk] < t) {
37
                t -= siz[cur_bk];
38
                cur_bk++;
39
                cur_bk %= cnt + 1;
40
            }
41
            cur = cur_bk * L;
42
            while (t) {
43
                t -= f[cur];
44
                cur++;
45
                cur %= n;
46
            }
47
            int tt = (cur - 1 + n) % n;
48
            f[tt] = false;
49
            siz[tt / L]--;
50
        }
51
    }
52
    for (int i = 0; i < n; ++i) {
53
        if (f[i]) {
54
            printf("%d\n", i + 1);
55
            return 0;
56
        }
57
    }
58
    return 0;
59
}
60

61
/*
62
0 1 2 3 4 5 6 7 8 9
63
0 1 _ 3 4 5 6 7 8 9
64
0 1 _ 3 4 _ 6 7 8 9
65
0 1 _ 3 4 _ 6 7 _ 9
66
0 _ _ 3 4 _ 6 7 _ 9
67
0 _ _ 3 4 _ _ 7 _ 9
68
_ _ _ 3 4 _ _ 7 _ 9
69
_ _ _ 3 4 _ _ _ _ 9
70
_ _ _ 3 _ _ _ _ _ 9
71
_ _ _ 3 _ _ _ _ _ _
72
*/

F. 石子合并#

如果数据小的话，直接用 STL 的堆就可以做，但是他没给数据范围，所以我采取了打表 + 找规律的做法。

答案 = $1 · 0 + 2^0 · 2 + 2^1 · 3 + 2^2 · 4 + \dots + (n - 1 - 2^0 - 2^1 - 2^2 - \dots) · k$ .

代码中注释掉的是打表的过程。

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

4
using namespace std;
5

6
// priority_queue<int, vector<int>, greater<int>> q;
7
// long long res[101], t[101];
8

9
int main() {
10
    unsigned long long n, res = 0;
11
    cin >> n;
12
    int i = 0;
13
    n--;
14
    while (n) {
15
        if (n >= (1ull << i)) res += (1ull << i) * (i + 2), n -= (1ull << i);
16
        else res += n * (i + 2), n = 0;
17
        i++;
18
    }
19
    cout << res << endl;
20

21
    // for (int t = 1; t <= 100; ++t) {
22
    //     int i = 0;
23
    //     n = t - 1;
24
    //     while (n) {
25
    //         if (n >= (1ull << i)) res += (1ull << i) * (i + 2), n -= (1ull << i);
26
    //         else res += n * (i + 2), n = 0;
27
    //         i++;
28
    //     }
29
    //     cout << res << ' ';
30
    //     res = 0;
31
    //     // for (int i = 1; i <= n; ++i) q.push(1);
32
    //     // while (q.size() > 1) {
33
    //     //     int x = q.top(); q.pop();
34
    //     //     int y = q.top(); q.pop();
35
    //     //     q.push(x + y);
36
    //     //     res[n] += x + y;
37
    //     // }
38
    //     // q.pop();
39
    // }
40
    // for (int i = 1; i <= 100; ++i) t[i] = res[i] - res[i - 1];
41
    // for (int i = 1; i <= 100; ++i) cout << res[i] << ' ';
42
    // cout << endl;
43
    return 0;
44
}

Star's Blog