Star 的档案库

Appearance

2026夏个人训练赛第三十二场 ​

A. 位置对 ​

  • 哈希集合与映射
  • Ad Hoc
cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

map<int, int> a;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    long long res = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int t;
        cin >> t;
        res += a[t];
        a[-t]++;
    }
    cout << res << '\n';
    return 0;
}

B. 井字棋 ​

  • 分类讨论
  • 两个人不能都赢过
  • 一个人不能赢三次
  • 先手赢一定比后手多一个棋子
  • 后手赢一定和先手棋子一样
cpp
#include <bits/stdc++.h>

using namespace std;

char a[3][3];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int c1 = 0, c2 = 0;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                cin >> a[i][j];
                c1 += a[i][j] == 'x';
                c2 += a[i][j] == 'o';
            }
        }
        if (c1 < c2 || c1 > c2 + 1) {
            cout << "False\n";
            continue;
        }
        int win1 = 0, win2 = 0;
        char c = 'x';
        for (int i = 0; i < 3; ++i) {
            if (a[i][0] == c && a[i][1] == c && a[i][2] == c) win1 += 1;
            if (a[0][i] == c && a[1][i] == c && a[2][i] == c) win1 += 1;
        }
        if (a[0][0] == c && a[1][1] == c && a[2][2] == c) win1 += 1;
        if (a[2][0] == c && a[1][1] == c && a[0][2] == c) win1 += 1;
        c = 'o';
        for (int i = 0; i < 3; ++i) {
            if (a[i][0] == c && a[i][1] == c && a[i][2] == c) win2 += 1;
            if (a[0][i] == c && a[1][i] == c && a[2][i] == c) win2 += 1;
        }
        if (a[0][0] == c && a[1][1] == c && a[2][2] == c) win2 += 1;
        if (a[2][0] == c && a[1][1] == c && a[0][2] == c) win2 += 1;
        if (win1 && win2 || max(win1, win2) > 2 || win1 && c1 == c2 || win2 && c1 == c2 + 1) cout << "False\n";
        else cout << "True\n";
    }
    return 0;
}

C. 避开炸弹 ​

  • 动态规划

暴力 DP。

cpp
#include <bits/stdc++.h>

using namespace std;

int f[10010][11];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    memset(f, 0x3f, sizeof(f));
    f[1][1] = 0;
    for (int i = 1; i <= m; ++i) {
        int t;
        cin >> t;
        for (int j = 1; j <= n; ++j) {
            if (j != t) {
                for (int k = 1; k <= n; ++k) {
                    f[i][j] = min(f[i][j], f[i - 1][k] + (j != k));
                }
            }
        }
    }
    int res = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) res = min(res, f[m][i]);
    cout << res << '\n';
    return 0;
}

D. 01串 ​

  • 构造
  • Ad Hoc

我们知道连续的两个 1 一定构成一个 3 的倍数，然后剩下的找一下规律。

python
T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    if n == 0:
        print("0" * m)
        print("0" * m)
    elif n % 2 == 0:
        print("1" * n + "0" * m)
        if m % 2 == 0:
            print("1" + "0" * m + "1" * (n - 1))
        else:
            print("1" + "0" * (m - 1) + "1" + "0" + "1" * (n - 2))
    else:
        if n >= 3 and m >= 2:
            n -= 3
            print("1" * n + "10101" + "0" * (m - 2))
            if m % 2 == 0:
                print("1" + "0" * (m - 1) + "101" + "1" * n)
            else:
                print("1" + "0" * (m - 2) + "1010" + "1" * n)
        else:
            print("-1")
            print("-1")

E. 小鱼吃大鱼 ​

  • 排序
  • 二分查找

从大到小排序，枚举倍数，然后二分查找和他最接近的。去重后枚举倍数的均摊复杂度是调和级数求和约为 ln⁡n 是可以通过的。

cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 2000010;

int a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1, greater<int>());
    n = unique(a + 1, a + n + 1) - a - 1;
    int res = 0;
    for (int i = 2; i <= n; ++i) {
        for (int j = a[i]; j < a[1]; j += a[i]) {
            int k = j + a[i];
            int l = 1, r = i - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (a[mid] < k) r = mid;
                else l = mid + 1;
            }
            // cout << k << ' ' << a[l] << '\n';
            res = max(res, a[l] % a[i]);
        }
        if (res >= a[i]) break;
    }
    cout << res << '\n';
    return 0;
}

G. 大鱼吃小鱼 ​

  • 二分查找
  • 贪心

一定是一个等长的前缀和后缀按顺序吃，只要一个失败那么更长的都失败，直接二分这个长度。

cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 500010;

int a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);

    auto check = [&](int mid) {
        for (int i = 1; i <= mid; ++i) {
            if (a[i] * 2 > a[n - mid + i]) return false;
        }
        return true;
    };

    int l = 0, r = n / 2;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << n - l << '\n';
    return 0;
}

H. Garbage Classification ​

  • 模拟
cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 2000010;

int a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i) {
        cout << "Case #" << i << ": ";
        string s, t;
        cin >> s >> t;
        int d = 0, w = 0, h = 0;
        for (char &c : s) {
            char tt = t[c - 'a'];
            if (tt == 'd') d++;
            else if (tt == 'w') w++;
            else h++;
        }
        if (h * 4 >= d + w + h) cout << "Harmful\n";
        else if (h * 10 <= d + w + h) cout << "Recyclable\n";
        else if (d >= w * 2) cout << "Dry\n";
        else cout << "Wet\n";
    }
    return 0;
}

其他没做的题

  • 超级蚯蚓
  • Shorten IPv6 Address
  • Palindrome Mouse
  • Move
  • Androgynos