2026夏个人训练赛第三十七场

A. 弗雷德的困惑

• 几何geometry
• 数学math

竟然还卡精度。

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    long double x, y;
    cin >> x >> y;
    cout << max(0LL, (long long)ceill(acosl(-1) * (x * x + y * y) / 100) - 1) << '\n';
    return 0;
}

B. 亲情号码

• 数据结构data_structures
• 哈希集合与映射hash_set

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int val(char c) {
    if (isalpha(c)) return c - 'A' + 10;
    else return c - '0';
}

int pre[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        int cur = 0;
        for (int j = s.length() - 5; j < s.length(); ++j) {
            cur += val(s[j]);
        }
        res += pre[cur];
        pre[cur]++;
    }
    cout << res << '\n';
    return 0;
}

C. 癃场辐射下的电视

• 图搜索graph_traversal
• 位掩码bitmask
• 广度优先搜索bfs

爆搜。

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int msk[N], vis[1 << N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, s = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        s |= t << i;
    }
    for (int i = 0; i < n; ++i) {
        int k, t;
        cin >> k;
        msk[i] = (1 << n) - 1;
        for (int j = 0; j < k; ++j) {
            cin >> t;
            msk[i] ^= 1 << t - 1;
        }
    }
    queue<pair<int, int>> q;
    q.emplace(0, s);
    vis[s] = true;
    while (!q.empty()) {
        auto [d, x] = q.front();
        q.pop();
        if (x == 4) {
            cout << d << '\n';
            break;
        }
        for (int i = 0; i < n; ++i) {
            if (x >> i & 1) continue;
            int y = x & msk[i] ^ (1 << i);
            // cout << i << ' ' << bitset<5>(x) << ' ' << bitset<5>(y) << '\n';
            if (!vis[y]) {
                vis[y] = true;
                q.emplace(d + 1, y);
            }
        }
    }
    return 0;
}

/*
1 1 0 0 1
*/

D. WZK 吃小鸡腿

• 动态规划dp
• 背包knapsack

又来多重背包。

#include <bits/stdc++.h>

using namespace std;

const int M = 10010;
int f[M];

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) {
        int cnt, w, v;
        cin >> cnt >> w >> v;

        int cur = 1;
        while (cur <= cnt) {
            cnt -= cur;
            for (int j = m; j >= cur * w; --j) {
                f[j] = max(f[j], f[j - cur * w] + v * cur);
            }
            cur <<= 1;
        }
        if (cnt) {
            for (int j = m; j >= cnt * w; --j) {
                f[j] = max(f[j], f[j - cnt * w] + v * cnt);
            }
        }
    }
    cout << f[m] << '\n';
    return 0;
}

E. 塔

• 数位 DPdp_digit
• 动态规划dp

数位 DP 统计有一位 4 或有连续的 13 的数的个数，然后减掉。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL a[15], f[15][10][2][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        LL n, k;
        cin >> n >> k;
        int len = 0;
        LL cnt = n;
        while (n) {
            a[++len] = n % 10;
            n /= 10;
        }
        memset(f, 0, sizeof(f));
        f[len + 1][0][1][0] = 1;
        for (int i = len; i; --i) {
            for (int j = 0; j < 10; ++j) {
                for (int k = 0; k < 10; ++k) {
                    if (j <= a[i]) {
                        f[i][j][j == a[i]][j == 4 || j == 3 && k == 1] += f[i + 1][k][1][0];
                        f[i][j][j == a[i]][1] += f[i + 1][k][1][1];
                    }
                    f[i][j][0][j == 4 || j == 3 && k == 1] += f[i + 1][k][0][0];
                    f[i][j][0][1] += f[i + 1][k][0][1];
                }
            }
        }
        for (int i = 0; i < 10; ++i) {
            cnt -= f[1][i][0][1] + f[1][i][1][1];
        }
        cout << cnt * k << '\n';
    }
    return 0;
}

F. Check

• 图论graphs
• 拓扑排序topological_sorting
• 动态规划dp

拓扑排序一下，按照拓扑序一段一段算。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 210;
vector<int> adj[N];
LL f[N];
int a[N], b[N], deg[N], rnk[N], len;

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;
        cin >> x >> y;
        adj[x].emplace_back(y);
        deg[y]++;
    }
    int s, t, k;
    cin >> s >> t >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> a[i];
    }
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!deg[i]) q.emplace(i);
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        b[++len] = x;
        rnk[x] = len;
        for (int &y : adj[x]) {
            if (--deg[y] == 0) q.emplace(y);
        }
    }
    a[++k] = s, a[++k] = t;
    sort(a + 1, a + k + 1, [&](int x, int y) {
        return rnk[x] < rnk[y];
    });
    LL res = 1;
    k = unique(a + 1, a + k + 1) - a - 1;
    for (int i = 1; i < k; ++i) {
        fill(f, f + n + 1, 0);
        f[a[i]] = 1;
        for (int j = 1; j <= n; ++j) {
            int x = b[j];
            for (int &y : adj[x]) {
                f[y] += f[x];
            }
        }
        // for (int j = 1; j <= n; ++j) cout << f[j] << ' ';
        // cout << '\n';
        res *= f[a[i + 1]];
    }
    cout << res << '\n';
    return 0;
}

其他没做的题

• 发电站网络
• 陶庵梦忆
• 植物大战僵尸
• 镜像拆分