2026寒假集训个人训练赛第十八场

A. 间隔#

不可能当且仅当有相邻相等的且不是全部相等，否则最小间隔就是所有间隔的 gcd。

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

4
using namespace std;
5

6
int gcd(int a, int b) {
7
    return b ? gcd(b, a % b) : a;
8
}
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int T;
14
    cin >> T;
15
    while (T--) {
16
        bool f = true;
17
        int n;
18
        cin >> n;
19
        vector<int> a(n + 1);
20
        for (int i = 1; i <= n; ++i) {
21
            cin >> a[i];
22
        }
23
        int g = 0;
24
        for (int i = 2; i <= n; ++i) {
25
            if (a[i] - a[i - 1] == 0 && a[i] != a[1]) {
26
                cout << -1 << endl;
27
                f = false;
28
                break;
29
            }
30
            g = gcd(g, a[i] - a[i - 1]);
31
        }
32
        if (!f) continue;
33
        if (g == 0) {
34
            cout << 0 << endl;
35
            continue;
36
        }
37
        long long cnt = 0;
38
        for (int i = 2; i <= n; ++i) {
39
            cnt += (a[i] - a[i - 1]) / g - 1;
40
        }
41
        cout << cnt << endl;
42
    }
43
    return 0;
44
}

B. 密码锁#

直接暴力枚举 DP 即可。

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6
const int N = 30, M = 1010, MOD = 1000000007;
7
LL f[M][N][N];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n, m, t;
13
    cin >> n >> m >> t;
14
    for (int i = 1; i <= n; ++i) {
15
        for (int j = 1; j <= m; ++j) {
16
            f[1][i][j] = 1;
17
        }
18
    }
19
    for (int i = 2; i <= t; ++i) {
20
        int dis;
21
        cin >> dis;
22
        for (int j = 1; j <= n; ++j) {
23
            for (int k = 1; k <= m; ++k) {
24
                for (int x = 1; x <= n; ++x) {
25
                    for (int y = 1; y <= m; ++y) {
26
                        if (abs(x - j) + abs(y - k) <= dis) f[i][j][k] = (f[i][j][k] + f[i - 1][x][y]) % MOD;
27
                    }
28
                }
29
            }
30
        }
31
    }
32
    LL res = 0;
33
    for (int i = 1; i <= n; ++i) {
34
        for (int j = 1; j <= m; ++j) {
35
            res = (res + f[t][i][j]) % MOD;
36
        }
37
    }
38
    cout << res << endl;
39
    return 0;
40
}

C. 上街#

这是一个非常非常恶心的大模拟 + Dijkstra，题目基本上是纯板子，但是写着真恶心。

1
#include <iostream>
2
#include <queue>
3
#include <cstring>
4
#include <tuple>
5

6
using namespace std;
7

8
typedef long long LL;
9
const int N = 210, M = 60;
10
const int deltx[] = {1, 0, -1, 0}, delty[] = {0, -1, 0, 1};
11

12
int a[N][N], b[N][N], d[N][N], e[N][N];
13
int dis[N][N][4][M];
14
bool vis[N][N][4][M];
15

16
int main() {
17
    ios::sync_with_stdio(0);
18
    cin.tie(0), cout.tie(0);
19
    int n, m, t, xe, ye;
20
    cin >> n >> m >> t >> xe >> ye;
21
    for (int i = 1; i <= n; ++i) {
22
        for (int j = 1; j <= m; ++j) {
23
            cin >> a[i][j] >> b[i][j] >> d[i][j] >> e[i][j];
24
        }
25
    }
26
    memset(dis, 0x3f, sizeof(dis));
27
    priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> q;
28
    dis[1][1][0][0] = 0;
29
    q.emplace(dis[1][1][0][0], 0, 0, 1, 1);
30
    while (!q.empty()) {
31
        auto [_, ct, dir, x, y] = q.top();
32
        q.pop();
33
        if (vis[x][y][dir][ct]) continue;
34
        vis[x][y][dir][ct] = true;
35
        int &dx = dis[x][y][dir][ct];
36
        if (x == xe && y == ye) {
37
            cout << dx << endl;
38
            return 0;
39
        }
40
        int tx, ty, ndir, nt, w;
41
        if (a[x][y] == 0 && b[x][y] == 0) {
42
            for (int tt = dir - 1; tt <= dir + 1; ++tt) {
43
                ndir = (tt + 4) % 4, tx = x + deltx[ndir], ty = y + delty[ndir];
44
                if (tx <= 0 || tx > n || ty <= 0 || ty > m) continue;
45
                if (ndir == 0) w = d[x][y];
46
                else if (ndir == 1) w = e[tx][ty];
47
                else if (ndir == 2) w = d[tx][ty];
48
                else w = e[x][y];
49
                if (t == 0) nt = 0;
50
                else nt = (ct + w) % t;
51
                int &dy = dis[tx][ty][ndir][nt];
52
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
53
            }
54
        }
55
        else if (dir == 0) {
56
            if (y > 1) { // you
57
                ndir = 1, tx = x, ty = y - 1, w = e[tx][ty], nt = (ct + e[tx][ty]) % t;
58
                int &dy = dis[tx][ty][ndir][nt];
59
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
60
            }
61
            if (x < n) { // qian
62
                ndir = 0, tx = x + 1, ty = y, w = (ct < a[x][y] ? a[x][y] - ct : 0) * 10 + d[x][y], nt = (max(ct, a[x][y]) + d[x][y]) % t;
63
                int &dy = dis[tx][ty][ndir][nt];
64
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
65
            }
66
            if (y < m) { // zuo
67
                ndir = 3, tx = x, ty = y + 1, w = (ct < a[x][y] ? a[x][y] - ct : 0) * 10 + e[x][y], nt = (max(ct, a[x][y]) + e[x][y]) % t;
68
                int &dy = dis[tx][ty][ndir][nt];
69
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
70
            }
71
        }
72
        else if (dir == 1) {
73
            if (x > 1) { // you
74
                ndir = 2, tx = x - 1, ty = y, w = d[tx][ty], nt = (ct + d[tx][ty]) % t;
75
                int &dy = dis[tx][ty][ndir][nt];
76
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
77
            }
78
            if (y > 1) { // qian
79
                ndir = 1, tx = x, ty = y - 1, w = ct < a[x][y] ? e[tx][ty] : (t - ct) * 10 + e[tx][ty], nt = ((ct < a[x][y] ? ct : 0) + e[tx][ty]) % t;
80
                int &dy = dis[tx][ty][ndir][nt];
81
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
82
            }
83
            if (x < n) { // zuo
84
                ndir = 0, tx = x + 1, ty = y, w = ct < a[x][y] ? d[x][y] : (t - ct) * 10 + d[x][y], nt = ((ct < a[x][y] ? ct : 0) + d[x][y]) % t;
85
                int &dy = dis[tx][ty][ndir][nt];
86
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
87
            }
88
        }
89
        else if (dir == 2) {
90
            if (y < m) { // zuo
91
                ndir = 3, tx = x, ty = y + 1, w = e[x][y], nt = (ct + e[x][y]) % t;
92
                int &dy = dis[tx][ty][ndir][nt];
93
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
94
            }
95
            if (x > 1) { // qian
96
                ndir = 2, tx = x - 1, ty = y, w = (ct < a[x][y] ? a[x][y] - ct : 0) * 10 + d[tx][ty], nt = (max(ct, a[x][y]) + d[tx][ty]) % t;
97
                int &dy = dis[tx][ty][ndir][nt];
98
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
99
            }
100
            if (y > 1) { // zuo
101
                ndir = 1, tx = x, ty = y - 1, w = (ct < a[x][y] ? a[x][y] - ct : 0) * 10 + e[tx][ty], nt = (max(ct, a[x][y]) + e[tx][ty]) % t;
102
                int &dy = dis[tx][ty][ndir][nt];
103
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
104
            }
105
        }
106
        else { // dir == 3
107
            if (x < n) { // you
108
                ndir = 0, tx = x + 1, ty = y, w = d[x][y], nt = (ct + d[x][y]) % t;
109
                int &dy = dis[tx][ty][ndir][nt];
110
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
111
            }
112
            if (y < m) { // qian
113
                ndir = 3, tx = x, ty = y + 1, w = ct < a[x][y] ? e[x][y] : (t - ct) * 10 + e[x][y], nt = ((ct < a[x][y] ? ct : 0) + e[x][y]) % t;
114
                int &dy = dis[tx][ty][ndir][nt];
115
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
116
            }
117
            if (x > 1) { // zuo
118
                ndir = 2, tx = x - 1, ty = y, w = ct < a[x][y] ? d[tx][ty] : (t - ct) * 10 + d[tx][ty], nt = ((ct < a[x][y] ? ct : 0) + d[tx][ty]) % t;
119
                int &dy = dis[tx][ty][ndir][nt];
120
                if (dy > dx + w) dy = dx + w, q.emplace(dy, nt, ndir, tx, ty);
121
            }
122
        }
123
    }
124
    return 0;
125
}

D. 联通数#

所有两位及以上的全是 1 的数都能用 111 和 11 表示出来，先全用 111，然后一个一个反悔。显然反悔的步数不会超过 110 就一定能找到答案 / 判定不合法。

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6

7
int main() {
8
    ios::sync_with_stdio(0);
9
    cin.tie(0), cout.tie(0);
10
    int T;
11
    cin >> T;
12
    while (T--) {
13
        LL n, k;
14
        cin >> n >> k;
15
        if (n % k == 0) {
16
            n /= k;
17
            LL t = n / 111;
18
            bool f = false;
19
            for (int i = 1; i <= t; ++i) {
20
                if ((n - (LL)i * 111) % 11 == 0) {
21
                    f = true;
22
                    break;
23
                }
24
            }
25
            if (f) cout << "YES" << endl;
26
            else cout << "NO" << endl;
27
        }
28
        else cout << "NO" << endl;
29
    }
30
    return 0;
31
}

E. 赛博朋克#

F. 凌云渡#

G. 圣迹再临#

H. Wooden Sticks#

和导弹拦截问题一样，把一个维度排序，然后另一个维度贪心取。

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

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 5010;
9

10
pair<LL, LL> a[N];
11
vector<LL> b;
12

13
int main() {
14
    ios::sync_with_stdio(0);
15
    cin.tie(0), cout.tie(0);
16
    int T;
17
    cin >> T;
18
    while (T--) {
19
        int n;
20
        cin >> n;
21
        for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
22
        sort(a + 1, a + n + 1);
23
        for (int i = 1; i <= n; ++i) {
24
            int p = -1;
25
            for (int j = 0; j < b.size(); ++j) {
26
                if (b[j] <= a[i].second) {
27
                    if (p == -1) p = j;
28
                    else if (b[j] > b[p]) p = j;
29
                }
30
            }
31
            if (p == -1) b.emplace_back(a[i].second);
32
            else b[p] = a[i].second;
33
        }
34
        cout << b.size() << endl;
35
        b.clear();
36
    }
37
    return 0;
38
}

I. Shipping containers#

如果间隔大于 $\sqrt{n}$ 那么单次修改次数不会超过 $\lfloor\sqrt{n}\rfloor$ ，暴力修改，反之维护前缀和只会占用 $O(n\sqrt{n})$ 的空间。分开做即可。

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

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 100010;
8

9
int s[N][320], a[N];
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int n, k, l;
15
    cin >> n >> k;
16
    l = sqrt(n);
17
    for (int i = 1; i <= k; ++i) {
18
        int p, cnt, d;
19
        cin >> p >> cnt >> d;
20
        if (d > l) for (int j = 0; j < cnt; ++j) a[p + j * d]++;
21
        else s[p][d]++, s[min(n + 1, p + d * cnt)][d]--;
22
    }
23
    for (int i = 1; i <= n; ++i) {
24
        int t = a[i];
25
        for (int j = 1; j <= l; ++j) {
26
            if (i - j >= 0) s[i][j] += s[i - j][j];
27
            t += s[i][j];
28
        }
29
        cout << t << ' ';
30
    }
31
    cout << endl;
32
    return 0;
33
}

Star's Blog