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

前四道我没找到来源，后两道是 AtCoder 的 abc213c 和 abc229d。

A. 编程试题#

签到题，直接模拟就行。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    int n, res = 0;
9
    cin >> n;
10
    while (n--) {
11
        int t = 0;
12
        for (int i = 0; i < 5; ++i) {
13
            int f;
14
            cin >> f;
15
            t += f;
16
        }
17
        if (t >= 3) res++;
18
    }
19
    cout << res << endl;
20
    return 0;
21
}

B. 密码难题#

一共只有 $10^4$ 种可能，直接暴力所有的情况。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    string s;
9
    int res = 0;
10
    cin >> s;
11
    for (int i = 0; i < 10000; ++i) {
12
        int a[] = {i % 10, i / 10 % 10, i / 100 % 10, i / 1000};
13
        bool f = true;
14
        for (int j = 0; j < 10; ++j) {
15
            if (s[j] == 'y' && a[0] != j && a[1] != j && a[2] != j && a[3] != j || s[j] == 'n' && (a[0] == j || a[1] == j || a[2] == j || a[3] == j)) {
16
                f = false;
17
                break;
18
            }
19
        }
20
        res += f;
21
    }
22
    cout << res << endl;
23
    return 0;
24
}

C. 最少时间#

问题等价于首先每个订单都必须生产，在这个前提下我们有 $k - 1$ 次机会删掉任意两次生产之间的间隔，贪心删最大的一定最优。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    string s;
9
    int res = 0;
10
    cin >> s;
11
    for (int i = 0; i < 10000; ++i) {
12
        int a[] = {i % 10, i / 10 % 10, i / 100 % 10, i / 1000};
13
        bool f = true;
14
        for (int j = 0; j < 10; ++j) {
15
            if (s[j] == 'y' && a[0] != j && a[1] != j && a[2] != j && a[3] != j || s[j] == 'n' && (a[0] == j || a[1] == j || a[2] == j || a[3] == j)) {
16
                f = false;
17
                break;
18
            }
19
        }
20
        res += f;
21
    }
22
    cout << res << endl;
23
    return 0;
24
}

D. 最佳时段#

考虑 dp，维护 $f_{i, j}$ : 前 $i$ 个中选了 $j$ 段时的最大值，这道题的数据不太大可以 $O(n^2 k)$ 暴力更新，如果数据在开大一点就要考虑单调队列（栈）优化了。

我数组越界吃了 4 个罚时😇😇😇

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    string s;
9
    int res = 0;
10
    cin >> s;
11
    for (int i = 0; i < 10000; ++i) {
12
        int a[] = {i % 10, i / 10 % 10, i / 100 % 10, i / 1000};
13
        bool f = true;
14
        for (int j = 0; j < 10; ++j) {
15
            if (s[j] == 'y' && a[0] != j && a[1] != j && a[2] != j && a[3] != j || s[j] == 'n' && (a[0] == j || a[1] == j || a[2] == j || a[3] == j)) {
16
                f = false;
17
                break;
18
            }
19
        }
20
        res += f;
21
    }
22
    cout << res << endl;
23
    return 0;
24
}

E. Reorder Cards#

H 和 W 没有意义，只需要所有的横坐标离散化一下，所有的纵坐标离散化一下，然后输出。

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

5
using namespace std;
6

7
const int N = 100010;
8
int x[N], y[N];
9
vector<int> vx, vy;
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int h, w, n;
15
    cin >> h >> w >> n;
16
    for (int i = 1; i <= n; ++i) {
17
        cin >> x[i] >> y[i];
18
        vx.emplace_back(x[i]), vy.emplace_back(y[i]);
19
    }
20
    sort(vx.begin(), vx.end());
21
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
22
    sort(vy.begin(), vy.end());
23
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
24
    for (int i = 1; i <= n; ++i) {
25
        cout << lower_bound(vx.begin(), vx.end(), x[i]) - vx.begin() + 1 << ' ' << lower_bound(vy.begin(), vy.end(), y[i]) - vy.begin() + 1 << endl;
26
    }
27
    return 0;
28
}

F. Longest X#

问题等价于维护一个滑动窗口，需要保证窗口内的 . 的数量不多于 $k$ ，开个队列或者不开出来用双指针扫描都可以。

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

5
using namespace std;
6

7
const int N = 200010;
8
int q[N];
9
string s;
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int n, k;
15
    cin >> s >> k;
16
    n = s.length();
17
    s = " " + s;
18
    int hh = 0, tt = -1, t = 0, res = 0;
19
    for (int i = 1; i <= n; ++i) {
20
        q[++tt] = i;
21
        t += s[i] == '.';
22
        while (hh <= tt && t > k) t -= s[q[hh++]] == '.';
23
        res = max(res, tt - hh + 1);
24
    }
25
    cout << res << endl;
26
    return 0;
27
}

Star's Blog