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

终于让我 AK 了一次，不会又是小学组吧，该嘲讽我三个小时才 AK 不如小学生了妈😭。

A. 迷惑时间

模拟

cpp

#include <iostream>

using namespace std;

int main() {
    int a, b, c;
    scanf("%d:%d", &a, &b);
    c = (a * 60 + b + 1) % (24 * 60);
    auto check = [](int c) {
        int a = c / 60, b = c % 60;
        if (b <= 23) return true;
        else return false;
    };
    while (!check(c)) c = (c + 1) % (24 * 60);
    printf("%02d:%02d\n", c / 60, c % 60);
    return 0;
}

B. 回文方格图

暴力
字符串

距离对称中心 $(- x, - y), (- x, y), (x, - y), (x, y)$ 的这四个点需要相等，直接暴力枚举 26 个变化后的结果取最小的。如果对称中心是整点，所在的行 / 列要注意去重。

cpp

#include <iostream>

using namespace std;

const int N = 1010;
char a[N][N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    auto dis = [](char a, char b) -> int {
        return min((a + 26 - b) % 26, (b + 26 - a) % 26);
    };
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    int res = 0;
    for (int i = 1; i <= n / 2; ++i) {
        for (int j = 1; j <= m / 2; ++j) {
            char c[] = {a[i][j], a[n - i + 1][j], a[i][m - j + 1], a[n - i + 1][m - j + 1]};
            int t = 10000;
            for (char k = 'a'; k <= 'z'; ++k) {
                int cur = 0;
                for (int l = 0; l < 4; ++l) {
                    cur += dis(c[l], k);
                }
                t = min(t, cur);
            }
            res += t;
        }
    }
    if (n & 1) {
        for (int i = (n + 1) / 2, j = 1; j <= m / 2; ++j) {
            char c[] = {a[i][j], a[i][m - j + 1]};
            int t = 10000;
            for (char k = 'a'; k <= 'z'; ++k) {
                int cur = 0;
                for (int l = 0; l < 2; ++l) {
                    cur += dis(c[l], k);
                }
                t = min(t, cur);
            }
            res += t;
        }
    }
    if (m & 1) {
        for (int i = 1, j = (m + 1) / 2; i <= n / 2; ++i) {
            char c[] = {a[i][j], a[n - i + 1][j]};
            int t = 10000;
            for (char k = 'a'; k <= 'z'; ++k) {
                int cur = 0;
                for (int l = 0; l < 2; ++l) {
                    cur += dis(c[l], k);
                }
                t = min(t, cur);
            }
            res += t;
        }
    }
    cout << res << '\n';
    return 0;
}

C. 美味蛋糕

数学
组合数学

可以形象的理解为，沿着立方体对角线枚举面积，然后找到答案所在的一个面之后在面上枚举行，找到对应行之后枚举列。

立方体沿着对角线的切面是有对称性的，可以利用这个简化一下计算，用隔板法:

前半段和后半段每个面是 $(\binom{x + y + z}{2})$
中间是 $(\binom{x + y + z}{2}) - (\binom{3}{1}) (\binom{x + y + z - n - 1}{2})$ ，直接选择一个位置给他绑定 n 个然后其他的用隔板法算出来不合法的扣掉。

之后就到一个平面上了就好枚举了。

cpp

#include <iostream>

using namespace std;

typedef long long LL;

LL comb2(LL n) {
    return n * (n - 1) / 2;
}

LL getd1(LL n, LL l) {
    // cout << n << ' ' << l << '\n';
    if (n * 3 - l + 3 <= n + 2) return getd1(n, n * 3 - l + 3);
    else if (l <= n + 2) return comb2(l - 1);
    else return comb2(l - 1) - comb2(l - n - 1) * 3;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    LL n, x;
    cin >> n >> x;

    if (n == 1 && x == 1) {
        cout << "1 1 1\n";
        return 0;
    }

    LL l = 3, s = 1;
    while (true) {
        LL d = getd1(n, l);
        if (s + d > x) break;
        else s += d;
        l++;
    }

    // cout << l << ' ' << s << '\n';

    LL i = max(1LL, l - n * 2);
    while (true) {
        LL d = min(n, l - i - 1) - max(l - i - n, 1LL) + 1;
        // cout << d << ' ';
        if (s + d > x) break;
        else s += d;
        i++;
    }
    // cout << '\n';
    
    LL j = x - s + max(1LL, l - i - n);
    LL k = l - i - j;
    cout << i << ' ' << j << ' ' << k << '\n';
    return 0;
}

D. 最小权值

动态规划
背包

n = 1 直接特判掉，其他的

\begin{aligned} \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} (x_{i} + x_{j})^{2} & = (n - 1) \sum_{i = 1}^{n} x_{i}^{2} + \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} 2 x_{i} x_{j} \\ = (n - 2) \sum x_{i}^{2} + {(\sum_{i = 1}^{n} x_{i})}^{2} \end{aligned}

第一项是定死的，只用考虑第二项，显然两组的求和越接近越好，于是可以用分组背包算出来所有的可能值然后暴力枚举。

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);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        if (n == 1) {
            cin >> n >> n;
            cout << "0\n";
            continue;
        }
        vector<int> f(10001), g(10001), a(n + 1), b(n + 1);
        f[0] = 1;
        LL res = 0, s = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            res += (LL)(a[i] * a[i]) * (n - 2);
            s += a[i];
        }
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
            res += (LL)(b[i] * b[i]) * (n - 2);
            s += b[i];
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 10000; j; --j) {
                if (j >= a[i]) g[j] |= f[j - a[i]];
                if (j >= b[i]) g[j] |= f[j - b[i]];
            }
            swap(f, g);
            fill(g.begin(), g.end(), 0);
        }
        int t = s / 2;
        while (!f[t]) t--;
        cout << res + t * t + (s - t) * (s - t) << '\n';
    }
    return 0;
}

E. 友谊值

位掩码

按位统计。

cpp

#include <iostream>

using namespace std;

int a[20][2];

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;
        for (int j = 0; j < 20; ++j) {
            res += (long long)a[j][(t >> j & 1) ^ 1] << j;
        }
        for (int j = 0; j < 20; ++j) {
            a[j][t >> j & 1]++;
        }
    }
    cout << res << '\n';
    return 0;
}

F. 分割金币

动态规划
背包

经典的背包问题。

cpp

#include <iostream>

using namespace std;

const int MOD = 1000000;
const int N = 250, M = 2000 * 250 + 10;

int a[N], f[M];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, s = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s += a[i];
    }
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = s; j >= a[i]; --j) {
            f[j] = (f[j] + f[j - a[i]]) % MOD;
        }
    }
    int mnd = s;
    for (int i = 1; i <= s / 2; ++i) {
        if (f[i]) mnd = min(mnd, abs(s - i * 2));
    }
    int res = 0;
    for (int i = 1; i <= s / 2; ++i) {
        if (abs(s - i * 2) == mnd) res = (res + f[i]) % MOD;
    }
    cout << mnd << '\n' << res << '\n';
    return 0;
}

G. 魔法传输

线段树
懒标记线段树

线段树维护首项和公差，因为只有单点查询，可以不用 pushup 了，直接用标记永久化比较方便。

cpp

#include <iostream>

using namespace std;

typedef long long LL;
const int MOD = 1000000007;
const int N = 100010;

struct Node {
    LL a, d;
} tr[N * 4];

Node merge(const Node &a, const Node &b) {
    return {(a.a + b.a) % MOD, (a.d + b.d) % MOD};
}

void modify(int u, int l, int r, int ql, int qr, LL a, LL d) {
    if (ql <= l && r <= qr) tr[u] = merge(tr[u], {(a + (l - ql) * d) % MOD, d});
    else {
        int mid = l + r >> 1;
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, a, d);
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, a, d);
    }
}

LL query(int u, int l, int r, int p) {
    if (l == r) return tr[u].a;
    else {
        int mid = l + r >> 1;
        LL res = 0;
        if (l <= p && p <= r) res = tr[u].a + tr[u].d * (p - l);
        if (p <= mid) return (res + query(u << 1, l, mid, p)) % MOD;
        else return (res + query(u << 1 | 1, mid + 1, r, p)) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    while (q--) {
        char op;
        cin >> op;
        if (op == 'C') {
            int l, r;
            cin >> l >> r;
            modify(1, 1, n, l, r, 1, 1);
            // for (int i = 1; i <= n; ++i) cout << query(1, 1, n, i) << ' ';
            // cout << '\n';
        }
        else {
            int x;
            cin >> x;
            cout << query(1, 1, n, x) << '\n';
        }
    }
    return 0;
}

H. 保存名画

图论
拓扑排序
动态规划

显然只要起点定了，运输次数是所有路径运输次数的最大值（小的可以插入到大的空隙里面不影响次数），枚举两个起点各试一次，用拓扑排序 DP 即可。

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int deg[N], bkdeg[N], odeg[N], a[N], f[N];
vector<int> adj[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) {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y), bkdeg[y]++, odeg[x]++;
    }
    auto work = [&](int bg) -> int {
        memcpy(deg, bkdeg, sizeof(int) * (n + 1));
        memset(f, 0, sizeof(int) * (n + 1));
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (!deg[i]) {
                q.emplace(i);
                f[i] = a[i] == bg ? 0 : 1;
            }
        }
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int &y : adj[x]) {
                f[y] = max(f[y], f[x] + (a[x] != a[y]));
                if (--deg[y] == 0) q.emplace(y);
            }
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) if (odeg[i] == 0) res = max(res, f[i]);
        return res;
    };
    cout << min(work(1), work(2)) << '\n';
    return 0;
}

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

A. 迷惑时间 ​

B. 回文方格图 ​

C. 美味蛋糕 ​

D. 最小权值 ​

E. 友谊值 ​

F. 分割金币 ​

G. 魔法传输 ​

H. 保存名画 ​