备战2025区域赛组队训练赛第 17 场

最红温的一天。

C. Insertion Sort#

特判 k >= n！特判 k >= n！特判 k >= n！

被 k > n 搞了，我们本以为他不会 > n 的，也没往那里想，真没想到是因为这里。

剩下的一共有三种情况

前 k 个数正好是 $1 \dots k$ ，那么后面的数（假设有 m 个）需要满足最长上升子序列长度不小于 m - 1，答案是 $k! \cdot ((n - k - 1)^2 + 1)$ ；
在第一种情况的基础上，把 k + 1 换到前面，那么后面的大数需要严格有序，换下的前面的数可以随意插空，答案是 $k! \cdot (n - k)$ ；
在第一种情况的基础上，把一个比 k + 1 更大的数换到前面，那么这个大数不能是最长上升子序列的元素，必须保证后面的严格有序，答案是 $k! \cdot (n - k - 1)$

求和就是最终答案。

1
#include <iostream>
2

3
using namespace std;
4

5
long long jc[60];
6
int n, k, q;
7

8
int main() {
9
    int T;
10
    scanf("%d", &T);
11
    for (int t = 1; t <= T; ++t) {
12
        scanf("%d%d%d", &n, &k, &q);
13
        jc[0] = 1;
14
        for (int i = 1; i <= k; ++i) {
15
            jc[i] = jc[i - 1] * i % q;
16
        }
17
        if (n <= k) {
18
            printf("Case #%d: %lld\n", t, jc[n]);
19
            continue;
20
        }
21
        else if (k == 1) {
22
            printf("Case #%d: %lld\n",t, 1LL * ((n - 1) * (n - 1) + 1) % q);
23
            continue;
24
        }
25
        printf("Case #%d: %lld\n", t, (((n - k - 1) * (n - k - 1) + 1) % q + 1LL * k * (n - k) % q + (n - k - 1) % q) % q * jc[k] % q);
26
    }
27
    return 0;
28
}

G. Best ACMer Solves the Hardest Problem#

当大模拟写就对了， $n^2 \sqrt{n}$ 能过，我不知道这道题为什么 WA 的这么多，我一次就过了，挺奇怪的。

代码复制粘贴冗余的非常严重，不建议这么做，因为虽然一时省事，万一挂了那就是另一个故事了。

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

5
using namespace std;
6

7
const int N = 6010;
8

9
bool vis[N][N];
10
int val[N][N];
11
int dx[] = {1, -1, 1, -1}, dy[] = {1, 1, -1, -1};
12

13
int main() {
14
    int T;
15
    scanf("%d", &T);
16
    for (int t = 1; t <= T; ++t) {
17
        memset(vis, 0, sizeof(vis));
18
        printf("Case #%d:\n", t);
19
        int n, m;
20
        scanf("%d%d", &n, &m);
21
        for (int i = 1; i <= n; ++i) {
22
            int x, y, z;
23
            scanf("%d%d%d", &x, &y, &z);
24
            vis[x][y] = true;
25
            val[x][y] = z;
26
        }
27
        long long lastans = 0;
28
        while (m--) {
29
            int op, x, y;
30
            scanf("%d%d%d", &op, &x, &y);
31
            x = (x + lastans) % 6000 + 1, y = (y + lastans) % 6000 + 1;
32
            if (op == 1) {
33
                int w;
34
                scanf("%d", &w);
35
                vis[x][y] = true;
36
                val[x][y] = w;
37
            }
38
            else if (op == 2) {
39
                vis[x][y] = false;
40
            }
41
            else if (op == 3) {
42
                int k, w;
43
                scanf("%d%d", &k, &w);
44
                int l = sqrt(k);
45
                for (int i = 0; i <= l; ++i) {
46
                    int j = sqrt(k - i * i);
47
                    if (i * i + j * j == k) {
48
                        if (i == 0 && j == 0) {
49
                            if (vis[x][y]) val[x][y] += w;
50
                        }
51
                        else if (i == 0) {
52
                            int tx = x, ty = y + j;
53
                            if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
54
                                if (vis[tx][ty]) val[tx][ty] += w;
55
                            }
56
                            tx = x, ty = y - j;
57
                            if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
58
                                if (vis[tx][ty]) val[tx][ty] += w;
59
                            }
60
                        }
61
                        else if (j == 0) {
62
                            int tx = x + i, ty = y;
63
                            if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
64
                                if (vis[tx][ty]) val[tx][ty] += w;
65
                            }
66
                            tx = x - i, ty = y;
67
                            if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
68
                                if (vis[tx][ty]) val[tx][ty] += w;
69
                            }
70
                        }
71
                        else
72
                            for (int d = 0; d < 4; ++d) {
73
                                int tx = x + i * dx[d], ty = y + j * dy[d];
74
                                if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
75
                                    if (vis[tx][ty]) val[tx][ty] += w;
76
                                }
77
                            }
78
                    }
79
                }
80
            }
81
            else {
82
                int k;
83
                scanf("%d", &k);
84
                int l = sqrt(k);
85
                long long res = 0;
86
                for (int i = 0; i <= l; ++i) {
87
                    int j = sqrt(k - i * i);
88
                    if (i * i + j * j == k) {
89
                        if (i == 0 && j == 0) {
90
                            if (vis[x][y]) res += val[x][y];
91
                        }
92
                        else if (i == 0) {
93
                            int tx = x, ty = y + j;
94
                            if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
95
                                if (vis[tx][ty]) res += val[tx][ty];
96
                            }
97
                            tx = x, ty = y - j;
98
                            if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
99
                                if (vis[tx][ty]) res += val[tx][ty];
100
                            }
101
                        }
102
                        else if (j == 0) {
103
                            int tx = x + i, ty = y;
104
                            if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
105
                                if (vis[tx][ty]) res += val[tx][ty];
106
                            }
107
                            tx = x - i, ty = y;
108
                            if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
109
                                if (vis[tx][ty]) res += val[tx][ty];
110
                            }
111
                        }
112
                        else
113
                            for (int d = 0; d < 4; ++d) {
114
                                int tx = x + i * dx[d], ty = y + j * dy[d];
115
                                if (tx > 0 && tx <= 6000 && ty > 0 && ty <= 6000) {
116
                                    if (vis[tx][ty]) res += val[tx][ty];
117
                                }
118
                            }
119
                    }
120
                }
121
                lastans = res;
122
                printf("%lld\n", res);
123
            }
124
        }
125
    }
126
    return 0;
127
}

J. How Much Memory Your Code Is Using?#

我又挂了一次签到题，原因是没想起来 long double 是 16 个字节。

type	memory(Byte)
bool / char	1
int / float	4
double / long long	8
long double / __int128	16

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

4
using namespace std;
5

6
int main() {
7
    ios::sync_with_stdio(0);
8
    string row;
9
    int T, n;
10
    getline(cin, row);
11
    T = stoi(row);
12
    for (int t = 0; t < T; ++t) {
13
        getline(cin, row);
14
        n = stoi(row);
15
        int res = 0;
16
        for (int i = 0; i < n; ++i) {
17
            getline(cin, row);
18
            int e = 0, c = 1;
19
            stringstream ss(row);
20
            ss >> row;
21
            if (row == "bool" || row == "char") e = 1;
22
            else if (row == "int" || row == "float") e = 4;
23
            else if (row == "double") e = 8;
24
            else if (row == "long") {
25
                ss >> row;
26
                if (row == "long") e = 8;
27
                else e = 16;
28
            }
29
            else if (row == "__int128") e = 16;
30
            else {
31
                cout << row << endl;
32
                cout << "invalidqwq" << endl;
33
            }
34
            ss >> row;
35
            int l = 0, r = 0;
36
            for (int j = 0; j < row.length(); ++j) {
37
                if (row[j] == '[') l = j;
38
                if (row[j] == ']') r = j;
39
            }
40
            if (l && r) {
41
                c = stoi(row.substr(l + 1, r - l - 1));
42
            }
43
            res += e * c;
44
        }
45
        cout << "Case #" << t + 1 << ": " << (res + 1023) / 1024 << endl;
46
    }
47
    return 0;
48
}

K. Let the Flames Begin^欠#

约瑟夫问题升级版，感觉能做。

L. Machining Disc Rotors^补#

这个当时急死我了，刚被 C 题卡了边界，又被这道题卡精度。

思路很简单

求出来所有交点；
检验是否有一条直径合法，根据旋转卡壳的结论，如果有合法的直径一定会有一个合法的并且一个一个端点是顶点的直径，枚举端点验证对称的一端有没有被切掉，如果有合法的直径直接输出；
没有合法的直径，还是根据旋转卡壳的结论，一定在端点能取到最大值，就 n² 枚举所有的端点，算距离即可。

但是，但是我被他卡精度卡疯了，算上赛时交的，一共错了 19 发，求极角的做法容易被卡，后续在 liuxx 佬的建议下绕过余弦定理算长度，全程不和反三角函数扯上关系，改完之后一次过了。

1
#include <iostream>
2
#include <cmath>
3
#define x first
4
#define y second
5
using namespace std;
6
typedef long double LD;
7
typedef long long LL;
8
typedef pair<LD, LD> PDD;
9
const LD eps = 1e-12;
10
const LD PI = acos(-1);
11
const int N = 110;
12

13
int dcmp(LD a, LD b) {
14
    if (fabs(a - b) < eps) return 0;
15
    else if (a < b) return -1;
16
    else return 1;
17
}
18

19
int sign(LD a) {
20
    if (fabs(a) < eps) return 0;
21
    else if (a < 0) return -1;
22
    else return 1;
23
}
24

25
PDD operator +(PDD a, PDD b) {
26
    return {a.x + b.x, a.y + b.y};
27
}
28

29
PDD operator -(PDD a, PDD b) {
30
    return {a.x - b.x, a.y - b.y};
31
}
32

33
PDD operator *(PDD a, LD t) {
34
    return {a.x * t, a.y * t};
35
}
36

37
PDD operator /(PDD a, LD t) {
38
    return {a.x / t, a.y / t};
39
}
40

41
LD operator *(PDD a, PDD b) {
42
    return a.x * b.y - a.y * b.x;
43
}
44

45
PDD rotate(PDD a, LD t) {
46
    return {a.x * cos(t) - a.y * sin(t), a.x * sin(t) + a.y * cos(t)};
47
}
48

49
LD getlen(PDD a) {
50
    return sqrt(a.x * a.x + a.y * a.y);
51
}
52

53
PDD normal(PDD a) {
54
    return a / getlen(a);
55
}
56

57
LD area(PDD a, PDD b, PDD c) {
58
    return (b - a) * (c - a);
59
}
60

61
PDD a[N][2];
62

63
void solve() {
64
    int n, R, l = 0;
65
    scanf("%d%d", &n, &R);
66
    for (int i = 1; i <= n; ++i) {
67
        int px, py, r;
68
        scanf("%d%d%d", &px, &py, &r);
69
        if ((LL)px * px + (LL)py * py < (LL)(r + R) * (r + R) && (LL)px * px + (LL)py * py > (LL)(r - R) * (r - R)) {
70
            // (R^2 + d^2 - r^2) / 2d = a
71
            PDD v = {px, py};
72
            LD d = getlen(v), b = (powl(R, 2) + powl(d, 2) - powl(r, 2)) / (d * 2), c = sqrt(powl(R, 2) - pow(b, 2));
73
            // cout << b << ' ' << c << endl;
74
            v = v / d;
75
            l++;
76
            a[l][0] = v * b + rotate(v, -PI / 2) * c;
77
            a[l][1] = v * b + rotate(v, PI / 2) * c;
78
            // printf("(%Lf, %Lf) (%Lf, %Lf)\n", a[l][0].x, a[l][0].y, a[l][1].x, a[l][1].y);
79
        }
80
    }
81
    if (l == 0) {
82
        printf("%d.000000\n", R * 2);
83
        return;
84
    }
85
    for (int i = 1; i <= l; ++i) {
86
        for (int tt = 0; tt < 2; ++tt) {
87
            auto t = a[i][tt] * -1;
88
            bool f = true;
89
            for (int j = 1; j <= l; ++j) {
90
                if (sign(area(a[j][0], a[j][1], t)) == -1) {
91
                    f = false;
92
                    break;
93
                }
94
            }
95
            if (f) {
96
                printf("%d.000000\n", R * 2);
97
                return;
98
            }
99
        }
100
    }
101
    LD res = 0.0;
102
    for (int i = 1; i <= l; ++i) {
103
        for (int j = i; j <= l; ++j) {
104
            for (int k = 0; k < 2; ++k) {
105
                for (int o = 0; o < 2; ++o) {
106
                    res = max(res, getlen(a[i][k] - a[j][o]));
107
                }
108
            }
109
        }
110
    }
111
    printf("%.10Lf\n", res);
112
}
113

114

115
int main() {
116
    int T;
117
    scanf("%d", &T);
118
    for (int i = 1; i <= T; ++i) {
119
        printf("Case #%d: ", i);
120
        solve();
121
    }
122
    return 0;
123
}

Star's Blog

C. Insertion Sort#

G. Best ACMer Solves the Hardest Problem#

J. How Much Memory Your Code Is Using?#

K. Let the Flames Begin欠#

L. Machining Disc Rotors补#

K. Let the Flames Begin^欠#

L. Machining Disc Rotors^补#