Star 的档案库

Appearance

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

A. 复制-粘贴 ​

  • 数学
cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    LL n;
    cin >> n;
    cout << (LL)(ceil(log2(n)) + 0.5) << '\n';
    return 0;
}

B. 足球联赛 ​

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

using namespace std;

typedef long long LL;
const int N = 60;
LL res[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) {
        for (int j = 1; j <= n; ++j) {
            char c;
            cin >> c;
            if (c == 'W') res[i] += 3;
            else if (c == 'L') res[j] += 3;
            else if (c == 'D') res[i] += 1, res[j] += 1;
        }
    }
    LL mx = 0;
    for (int i = 1; i <= n; ++i) mx = max(mx, res[i]);
    for (int i = 1; i <= n; ++i) {
        if (mx == res[i]) cout << i << ' ';
    }
    cout << '\n';
    return 0;
}

C. 捕食关系 ​

  • 排序
  • 双指针

排序之后双指针扫一下统计答案。

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

using namespace std;

typedef long long LL;
const int N = 20010;
int a[N], b[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> b[i];
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    LL res = 0;
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j < m && b[j + 1] < a[i]) j++;
        res += j;
    }
    cout << res << '\n';
    return 0;
}

D. 幻方 ​

  • 数学
python
n = int(input())
print((n + 1) * (n - 2) // 2)

E. WZK 的减肥计划 ​

  • 动态规划
  • 背包

多重背包。

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

using namespace std;

const int N = 1000010;
int f[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k, m = 1000000;
    cin >> n >> k;
    fill(f + 1, f + m + 1, 0x3f3f3f3f);
    for (int i = 1; i <= n; ++i) {
        int cost, cnt, cal;
        cin >> cost >> cnt >> cal;
        int cur = 1;
        while (cur <= cnt) {
            cnt -= cur;
            for (int j = m; j >= cur * cal; --j) {
                f[j] = min(f[j], f[j - cur * cal] + cost * cur);
            }
            cur <<= 1;
        }
        if (cnt) {
            for (int j = m; j >= cnt * cal; --j) {
                f[j] = min(f[j], f[j - cnt * cal] + cost * cnt);
            }
        }
    }
    for (int i = k + 1; i <= m; ++i) {
        if (f[i] != 0x3f3f3f3f) {
            cout << i << ' ' << f[i] << '\n';
            break;
        }
    }
    return 0;
}

F. 行程 ​

  • 图论
  • 最短路
  • Dijkstra

分层图最短路。

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

using namespace std;

const int N = 200010;
vector<pair<int, int>> adj[N];
int dis[N][2], vis[N][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].emplace_back(z, y);
        adj[y].emplace_back(z, x);
    }
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
    fill(dis[1], dis[1] + N * 2, 0x3f3f3f3f);
    dis[1][0] = 0;
    q.emplace(dis[1][0], 1, 0);
    while (!q.empty()) {
        auto [_, x, t] = q.top();
        q.pop();
        if (vis[x][t]) continue;
        vis[x][t] = true;
        for (auto [w, y] : adj[x]) {
            int nt = t ^ (w & 1);
            if (dis[y][nt] > dis[x][t] + w) {
                dis[y][nt] = dis[x][t] + w;
                q.emplace(dis[y][nt], y, nt);
            }
        }
    }
    if (dis[n][1] == 0x3f3f3f3f) cout << 0 << '\n';
    else cout << dis[n][1] << '\n';
    return 0;
}

其他没做的题

  • 排列之美
  • 重生