2026寒假集训个人训练赛第四场

A. 分组#

排序之后贪心的能取尽取一定不会变劣，而且还更有可能给后面留出配对的机会。

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

4
using namespace std;
5

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

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

B. 促销#

直接暴力模拟，时间复杂度是 log 级的。

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

4
using namespace std;
5
typedef long long LL;
6

7
int main() {
8
    ios::sync_with_stdio(0);
9
    cin.tie(0), cout.tie(0);
10
    LL n, m, res;
11
    cin >> n >> m;
12
    res = n;
13
    while (n >= m) {
14
        res += n / m;
15
        n = n / m + n % m;
16
    }
17
    cout << res << endl;
18
    return 0;
19
}

C. 凹区间#

经典的单调栈问题，找到一个数左右第一个比他大的位置。可以只跑一轮解决，维护一个（严格）单调递减的单调栈，对于一个数，入栈前栈顶是左侧第一个大于他的，弹掉他的那个是右侧第一个不小于他的。需要注意一个边界问题，如果只跑一轮单调栈不可避免边界取等的问题，需要特判，如果维护的是严格递减的，需要特判右边界取等，不严格递减需要特判左边界取等，否则会算多，例如 1 1 0 1 1，如果不特判边界会输出 4（分别会右侧和左侧多取一个 1），但是实际是 3。

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

4
using namespace std;
5
const int N = 1000010;
6
int a[N], st[N], tp;
7
// 单调递减
8
int main() {
9
    ios::sync_with_stdio(0);
10
    cin.tie(0), cout.tie(0);
11
    int n, res = 1;
12
    cin >> n;
13
    for (int i = 1; i <= n; ++i) {
14
        cin >> a[i];
15
        while (tp && a[i] >= a[st[tp]]) {
16
            if (tp > 1 && a[i] != a[st[tp]]) res = max(res, i - st[tp - 1] + 1);
17
            tp--;
18
        }
19
        st[++tp] = i;
20
    }
21
    cout << res << endl;
22
    return 0;
23
}

D. 好路径#

a 很小，考虑枚举所有下界，求出对应的最小上界，然后作差取 min。枚举到下界 k 时，在所有权值不小于 k 的位置构成的图上跑最小生成树找到从 (1, 1) 到 (n, n) 的路径上的最大权值，如果不存在路径说明 k 不合法，直接忽略掉。

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

6
using namespace std;
7
const int N = 110;
8
int a[N][N], f[N][N];
9
bool vis[N][N];
10
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};
11

12
int main() {
13
    ios::sync_with_stdio(0);
14
    cin.tie(0), cout.tie(0);
15
    int n;
16
    cin >> n;
17
    for (int i = 1; i <= n; ++i) {
18
        for (int j = 1; j <= n; ++j) {
19
            cin >> a[i][j];
20
        }
21
    }
22
    int res = 0x3f3f3f3f;
23
    for (int k = 0; k <= a[1][1]; ++k) {
24
        memset(vis, 0, sizeof(vis));
25
        memset(f, 0x3f, sizeof(f));
26
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
27
        f[1][1] = a[1][1];
28
        q.emplace(f[1][1], 1, 1);
29
        while (!q.empty()) {
30
            auto [_, x, y] = q.top();
31
            q.pop();
32
            if (vis[x][y]) continue;
33
            vis[x][y] = true;
34
            for (int t = 0; t < 4; ++t) {
35
                int tx = x + dx[t], ty = y + dy[t];
36
                if (tx > 0 && tx <= n && ty > 0 && ty <= n && a[tx][ty] >= k && f[tx][ty] > max(a[tx][ty], f[x][y])) {
37
                    f[tx][ty] = max(a[tx][ty], f[x][y]);
38
                    q.emplace(f[tx][ty], tx, ty);
39
                }
40
            }
41
        }
42
        // cout << f[n][n] << endl;
43
        res = min(res, f[n][n] - k);
44
    }
45
    cout << res << endl;
46
    return 0;
47
}

E. Shapes#

朴实无华的大模拟，我想到了一个能稍微好写一点的办法。首先不妨固定 s，枚举 t 的 4 个旋转角度，我们知道如果在一个恰当的角度下可以通过平移得到，那么所有的 # 的坐标的相对位置一定都是一样的，把 s 的 # 的坐标排序，把 t 的 # 的坐标也排序，偏移量应该是一个定值，检查这个即可。

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

5
using namespace std;
6
const int N = 210;
7
char a[N][N], b[N][N];
8
vector<pair<int, int>> va, vb;
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n;
14
    cin >> n;
15
    for (int i = 1; i <= n; ++i) {
16
        for (int j = 1; j <= n; ++j) {
17
            cin >> a[i][j];
18
            if (a[i][j] == '#') va.emplace_back(i, j);
19
        }
20
    }
21
    for (int i = 1; i <= n; ++i) {
22
        for (int j = 1; j <= n; ++j) {
23
            cin >> b[i][j];
24
            if (b[i][j] == '#') vb.emplace_back(i, j);
25
        }
26
    }
27
    if (va.size() != vb.size()) {
28
        cout << "No" << endl;
29
        return 0;
30
    }
31
    sort(va.begin(), va.end());
32
    for (int i = 0; i < 4; ++i) {
33
        for (auto &[x, y] : vb) {
34
            int tx = x, ty = y;
35
            x = ty, y = -tx + n + 1;
36
        }
37
        bool f = true;
38
        sort(vb.begin(), vb.end());
39
        for (int i = 1; i < va.size(); ++i) {
40
            if (vb[i].first - va[i].first != vb[0].first - va[0].first || vb[i].second - va[i].second != vb[0].second - va[0].second) {
41
                f = false;
42
                break;
43
            }
44
            // cout << vb[i].first << ' ' << vb[i].second << endl;
45
        }
46
        if (f) {
47
            cout << "Yes" << endl;
48
            return 0;
49
        }
50
    }
51
    cout << "No" << endl;
52
    return 0;
53
}

F. Ubiquity#

可以考虑容斥或者线性 DP 两种做法。

容斥#

答案 = 不限制 - 限制不选 9 - 限制不选 0 + 限制不选 9 和 0

cnt = 10^n - 2 \cdot 9^n + 8^n

写个快速幂（暴力求幂也行），然后套公式即可。

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

5
using namespace std;
6
typedef long long LL;
7
const int N = 1000010, MOD = 1000000007;
8

9
LL power(LL n, LL p) {
10
    LL res = 1, base = n;
11
    while (p) {
12
        if (p & 1) res = res * base % MOD;
13
        base = base * base % MOD;
14
        p >>= 1;
15
    }
16
    return res;
17
}
18

19
int main() {
20
    ios::sync_with_stdio(0);
21
    cin.tie(0), cout.tie(0);
22
    int n;
23
    cin >> n;
24
    cout << ((power(10, n) - power(9, n) - power(9, n) + power(8, n)) % MOD + MOD) % MOD << endl;
25
    return 0;
26
}

线性 DP#

无非只有四种状态

没有出现过 0 和 9
只出现过 0
只出现过 0
0 和 9 都出现过

通过枚举最后一位选什么进行状态转移，时间复杂度是 $O(n)$ 没有快速幂快。

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

5
using namespace std;
6
typedef long long LL;
7
const int N = 1000010, MOD = 1000000007;
8
LL f[N][4];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n;
14
    cin >> n;
15
    f[0][0] = 1;
16
    for (int i = 1; i <= n; ++i) {
17
        f[i][0] = f[i - 1][0] * 8 % MOD;
18
        f[i][1] = (f[i - 1][0] + f[i - 1][1] * 9) % MOD;
19
        f[i][2] = (f[i - 1][0] + f[i - 1][2] * 9) % MOD;
20
        f[i][3] = (f[i - 1][1] + f[i - 1][2] + f[i - 1][3] * 10) % MOD;
21
    }
22
    cout << f[n][3] << endl;
23
    return 0;
24
}

Star's Blog