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

A. 约数个数#

又是一个数论分块，不标数据范围害我 TLE 了一发。

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

4
using namespace std;
5

6
typedef long long LL;
7

8
LL cnt(LL n) {
9
    LL l = 1, res = 0;
10
    while (l <= n) {
11
        LL r = n / (n / l);
12
        res += (r - l + 1) * (n / l);
13
        l = r + 1;
14
    }
15
    return res;
16
}
17

18
int main() {
19
    ios::sync_with_stdio(0);
20
    cin.tie(0), cout.tie(0);
21
    int a, b;
22
    cin >> a >> b;
23
    cout << cnt(b) - cnt(a - 1) << endl;
24
    return 0;
25
}

B. 二哥找宝箱#

类似分层图最短路，因为宝箱很少，可以用一个 bitmask 存状态，然后 BFS 一遍。

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

5
using namespace std;
6

7
const int N = 110;
8
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
9
int a[N][N];
10
bool vis[N][N][1 << 5];
11

12
int main() {
13
    ios::sync_with_stdio(0);
14
    cin.tie(0), cout.tie(0);
15
    int n, m, t = 0;
16
    cin >> n >> m;
17
    queue<tuple<int, int, int, int>> q;
18
    for (int i = 1; i <= n; ++i) {
19
        for (int j = 1; j <= m; ++j) {
20
            cin >> a[i][j];
21
            if (a[i][j] == 2) q.emplace(0, 0, i, j), a[i][j] = 0;
22
            else if (a[i][j] == 1) a[i][j] <<= t++;
23
        }
24
    }
25
    while (!q.empty()) {
26
        auto [dis, msk, x, y] = q.front();
27
        q.pop();
28
        if (vis[x][y][msk]) continue;
29
        vis[x][y][msk] = true;
30
        if (msk == (1 << t) - 1) {
31
            cout << dis << endl;
32
            return 0;
33
        }
34
        for (int i = 0; i < 4; ++i) {
35
            int tx = x + dx[i], ty = y + dy[i];
36
            if (tx > 0 && tx <= n && ty > 0 && ty <= m && a[tx][ty] != -1) q.emplace(dis + 1, msk | a[tx][ty], tx, ty);
37
        }
38
    }
39
    cout << -1 << endl;
40
    return 0;
41
}

C. 整数去位#

贪心，尽可能让最高位的小即可。提前存一下对于某一个位置下一个 0 ~ 9 的位置，这样就可以 $O(n)$ 维护了。

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

4
using namespace std;
5

6
const int N = 1000010;
7

8
int ne[N][10], h[10];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    string num;
14
    int n, m;
15
    cin >> num >> m;
16
    n = num.length();
17
    if (n == m) cout << 0 << endl;
18
    else {
19
        num = " " + num;
20
        memset(h, 0x3f, sizeof(h));
21
        for (int i = n; i; --i) {
22
            h[num[i] - '0'] = i;
23
            for (int j = 0; j < 10; ++j) ne[i][j] = h[j];
24
        }
25
        for (int i = 1; i <= n; ++i) {
26
            for (int j = 0; j < 10; ++j) {
27
                if (m >= ne[i][j] - i) {
28
                    m -= ne[i][j] - i;
29
                    i = ne[i][j];
30
                    break;
31
                }
32
            }
33
            cout << num[i];
34
        }
35
        cout << endl;
36
    }
37
    return 0;
38
}

D. 柠檬汽水#

从大到小排序，然后按他说的模拟一边即可，把容易放弃的放到最后一定不劣。

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

4
using namespace std;
5

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

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n;
13
    cin >> n;
14
    for (int i = 1; i <= n; ++i) cin >> a[i];
15
    sort(a + 1, a + n + 1, greater<int>());
16
    int res = n;
17
    for (int i = 1; i <= n; ++i) {
18
        if (a[i] < i - 1) {
19
            res = i - 1;
20
            break;
21
        }
22
    }
23
    cout << res << endl;
24
    return 0;
25
}

E. Crane#

这个题似乎是两个题的缝合，拼尽全力无法看懂，题面和样例不一样……

F. Cow Dance Show 【Easy】#

已有答案检查是否合法很容易，答案具有单调性，二分答案。

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

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 10010;
8
int a[N], n, t;
9
priority_queue<int, vector<int>, greater<int>> q;
10

11
bool check(int mid) {
12
    for (int i = 1; i <= mid; ++i) q.emplace(a[i]);
13
    for (int i = mid + 1; i <= n; ++i) {
14
        int x = q.top();
15
        q.pop();
16
        q.emplace(x + a[i]);
17
    }
18
    int mx = 0;
19
    while (!q.empty()) mx = max(mx, q.top()), q.pop();
20
    return mx <= t;
21
}
22

23

24
int main() {
25
    ios::sync_with_stdio(0);
26
    cin.tie(0), cout.tie(0);
27
    cin >> n >> t;
28
    for (int i = 1; i <= n; ++i) cin >> a[i];
29
    int l = 1, r = n;
30
    while (l < r) {
31
        int mid = l + r >> 1;
32
        if (check(mid)) r = mid;
33
        else l = mid + 1;
34
    }
35
    cout << l << endl;
36
    return 0;
37
}

G. The Tower of Babylon#

不难发现每一种方块的一种朝向只会用一次（上面的要严格小于下面的）。先排个序保证一个维度的单调性，这样一个状态的后继就一定在他后面了，满足了无后效性，然后跑给类似 LIS 的 DP 即可。

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

5
using namespace std;
6
typedef long long LL;
7
const int N = 200;
8
tuple<LL, LL, LL> a[N];
9
LL f[N];
10
int m;
11

12
int main() {
13
    ios::sync_with_stdio(0);
14
    cin.tie(0), cout.tie(0);
15
    int n, T = 0;
16
    while (cin >> n, n) {
17
        m = 0;
18
        for (int i = 1; i <= n; ++i) {
19
            int b[3];
20
            cin >> b[0] >> b[1] >> b[2];
21
            for (int j = 0; j < 3; ++j) {
22
                for (int k = 0; k < 3; ++k) {
23
                    for (int l = 0; l < 3; ++l) {
24
                        if (j == k || k == l || l == j) continue;
25
                        a[++m] = {b[j], b[k], b[l]};
26
                    }
27
                }
28
            }
29
        }
30
        sort(a + 1, a + m + 1);
31
        LL res = 0;
32
        for (int i = 1; i <= m; ++i) {
33
            f[i] = get<2>(a[i]);
34
            for (int j = 1; j < i; ++j) {
35
                if (get<0>(a[j]) < get<0>(a[i]) && get<1>(a[j]) < get<1>(a[i])) f[i] = max(f[i], f[j] + get<2>(a[i]));
36
            }
37
            res = max(res, f[i]);
38
        }
39
        cout << "Case " << ++T << ": maximum height = " << res << endl;
40
    }
41
    return 0;
42
}

Star's Blog