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

A. 减去因子

博弈论
数论

打表观察一下。

cpp

#include <iostream>
#include <cmath>
#include <set>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    if (n & 1) cout << "Bob\n";
    else {
        for (int i = 1; i < 30; i += 2) {
            if ((1LL << i) == n) {
                cout << "Bob\n";
                return 0;
            }
        }
        cout << "Alice\n";
    }
    // for (int i = 1; i <= n; ++i) {
    //     set<int> s;
    //     for (int j = 2; j <= sqrt(i); ++j) {
    //         if (i % j == 0) s.insert(f[i - i / j]), s.insert(f[i - j]);
    //     }
    //     while (s.count(f[i])) f[i]++;
    //     if (!f[i] && !(i & 1)) cout << i << ' ';
    //     // cout << f[i] << endl;
    // }
    // cout << endl;
    return 0;
}

B. 袜子

贪心
前缀和

直接枚举丢弃哪个。

cpp

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 400010;
int a[N], b[N];
int pre[N], suf[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; ++i) {
        int t;
        cin >> t;
        a[t] = 1;
    }
    int m = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 2 - a[i]; ++j) {
            b[++m] = i;
        }
    }
    sort(a + 1, a + m + 1);
    for (int i = 2; i <= m; ++i) {
        pre[i] = pre[i - 2] + b[i] - b[i - 1];
    }
    if (m % 2 == 0) {
        cout << pre[m] << '\n';
        return 0;
    }
    for (int i = m - 1; i > 0; --i) {
        suf[i] = suf[i + 2] + b[i + 1] - b[i];
    }
    int res = 0x3f3f3f3f;
    for (int i = 1; i <= m; i += 2) {
        res = min(res, pre[i - 1] + suf[i + 1]);
    }
    cout << res << '\n';
    return 0;
}

C. 幻想机器人

模拟
哈希集合与映射

直接模拟。

cpp

#include <iostream>
#include <algorithm>
#include <unordered_map>
#define int long long
 
using namespace std;
 
unordered_map<int, bool> vis;
 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, k, len, x, y;
    cin >> n >> m >> k >> len >> x >> y;
    string s;
    cin >> s;
    vis[x * 1000000010 + y] = true;
    for (int i = 1; i <= len; ++i) {
        int tx, ty;
        if (s[i - 1] == 'L') tx = x, ty = y - 1;
        else if (s[i - 1] == 'R') tx = x, ty = y + 1;
        else if (s[i - 1] == 'U') tx = x - 1, ty = y;
        else tx = x + 1, ty = y;
 
        if (tx <= 0 || tx > n || ty <= 0 || ty > m) cout << "AWaDa!\n";
        else x = tx, y = ty;
 
        if (i % k == 0) {
            int t = x * 1000000010 + y;
            if (vis[t]) cout << "AKTang!\n";
            else vis[t] = true;
        }
    }
    cout << n * m - vis.size() << '\n';
    return 0;
}

D. 石头

动态规划
博弈论

DP 维护一下先手最多能取得的数量和这个前提下后手取的数量。

cpp

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int a[N], f[N], g[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (i - a[j] >= 0) {
                if (f[i] <= g[i - a[j]] + a[j]) {
                    f[i] = g[i - a[j]] + a[j];
                    g[i] = f[i - a[j]];
                }
            }
        }
    }
    cout << f[n] << '\n';
    return 0;
}

E. 传感器优化困境

二分查找
贪心

二分最小的那个步骤能处理的数量的最大值，每个步骤肯定都会优先选性价比最高的那一个，最后到边界了才会选另一个，直接暴力 100 个边界。

cpp

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

const int N = 110;
int a[N][2], b[N][2], n, x;

int calc(int tot, int i, int mid) {
    return a[i][1] * mid + max(0LL, (tot - a[i][0] * mid + b[i][0] - 1) / b[i][0]) * b[i][1];
}

bool check(int mid) {
    int cost = 0;
    for (int i = 1; i <= n; ++i) {
        int cur = 1e10;
        int l = 0, r = (mid + a[i][0] - 1) / a[i][0];
        int pos = 0;
        for (int j = l; j <= min(100LL, j); ++j) cur = min(cur, calc(mid, i, j));
        for (int j = max(0LL, r - 100); j <= r; ++j) cur = min(cur, calc(mid, i, j));
        cost += cur;
    }
    return cost <= x;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> x;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i][0] >> a[i][1] >> b[i][0] >> b[i][1];
    }
    // cout << check(894741) << endl;
    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';
    return 0;
}

F. 稳定婚姻

强连通分量
图论

夫妻的关系建正向边，其他情侣关系建反向边，成环就不安全，可以直接 tarjan。

cpp

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 8010, M = 24010;
unordered_map<string, int> mp;
int cnt;
int head[N], ne[M], ver[M], tot;
int dfn[N], low[N], t;
int st[N], ins[N], tp, id[N], scc_cnt;

void add(int x, int y) {
    ver[++tot] = y, ne[tot] = head[x], head[x] = tot;
}

int get_idx(string s) {
    if (mp.count(s)) return mp[s];
    else return mp[s] = ++cnt;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++t;
    st[++tp] = x;
    ins[x] = true;
    for (int i = head[x]; i; i = ne[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (ins[y]) low[x] = min(low[x], dfn[y]);
    }

    if (dfn[x] == low[x]) {
        int y;
        scc_cnt++;
        do {
            y = st[tp--];
            ins[y] = false;
            id[y] = scc_cnt;
        } while (y != x);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        string a, b;
        cin >> a >> b;
        int x = get_idx(a), y = get_idx(b);
        add(x, y);
    }
    int m;
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        string a, b;
        cin >> a >> b;
        int x = get_idx(a), y = get_idx(b);
        add(y, x);
    }
    for (int i = 1; i <= cnt; ++i) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 0; i < n; ++i) {
        if (id[i * 2 + 1] == id[i * 2 + 2]) cout << "Unsafe\n";
        else cout << "Safe\n";
    }
    return 0;
}

其他没做的题

补给计划
Equivalent Prefixes
Integration
Euclidean Distance
Parity of Tuples
ABBA

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

A. 减去因子 ​

B. 袜子 ​

C. 幻想机器人 ​

D. 石头 ​

E. 传感器优化困境 ​

F. 稳定婚姻 ​

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

A. 减去因子

B. 袜子

C. 幻想机器人

D. 石头

E. 传感器优化困境

F. 稳定婚姻