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

A. 第一个X

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res++;
        if (s[(i + k) % n] == 'X') {
            break;
        }
    }
    cout << res << '\n';
    return 0;
}

B. AK47计数

• 动态规划dp

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 100010;
LL f[N][5];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        char c = s[i - 1];
        memcpy(f[i], f[i - 1], sizeof(LL) * 5);
        if (c == 'A') f[i][1] += f[i - 1][0];
        else if (c == 'K') f[i][2] += f[i - 1][1];
        else if (c == '4') f[i][3] += f[i - 1][2];
        else if (c == '7') f[i][4] += f[i - 1][3];
    }
    cout << f[n][4] << '\n';
    return 0;
}

C. A=B

• 数学math

诈骗题，我们只需要关注 abs(A - B), 先考虑加过这个值，在把前面的一部分改成减。设操作次数为 x，观察到每反转一个加号都会给已有的结果贡献 2 的倍数，所以 x 至少应该满足

$$\{\begin{array}{l}\frac{1}{2}x(x+1)\ge |A-B|\\ \frac{1}{2}x(x+1)\equiv |A-B|(\mathrm{mod}2)\end{array}$$

不难发现如果 x 取最小的一个，那么 $\frac{frac12x(x+1)-|A-B|}{2}$ 一定不会超过 $\frac{1}{2}x(x+1)$，所以在里面一定能选出一组数反转后正好就能表示出来 $|A-B|$.

#include <iostream>

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--) {
        LL a, b;
        cin >> a >> b;
        LL d = abs(a - b);
        LL t = 0;
        while (t * (t + 1) / 2 < d || abs((t * (t + 1) / 2 - d)) % 2 == 1) t++;
        cout << t << '\n';
    }
    return 0;
}

D. 数字面包卷

• 模拟simulation
• 前缀和prefix_sum

从外到里可能有的结构有

• 填满的外圈
• 一圈没填满的
• 中间好几圈空的

注意到上下边界一个在 + 一个在 -，只要是一个完整的圈的横线每列的贡献都是一致的，通过维护这个前缀和维护每列的公共部分，然后对于填满的列推一下式子可以直接算，对于每填满的仅可能有一个，直接暴力统计，最后求和一下。

#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, k, cur = 0, ps = 0;
    cin >> n >> k;
    vector<LL> a(n + 1);
    int f = 0;
    for (int i = 1; i <= n / 2; ++i) {
        if (cur + (n - i * 2 + 1) * 4 > k) {
            if (!f) {
                f = i;
                int len = n - i * 2 + 1;
                for (int j = 1; j <= len; ++j) {
                    if (++cur <= k) a[i + j - 1] += cur;
                }
                for (int j = 1; j <= len; ++j) {
                    if (++cur <= k) a[i + len] += cur;
                }
                for (int j = 1; j <= len; ++j) {
                    if (++cur <= k) a[i + len - j + 1] += cur;
                }
                for (int j = 1; j <= len; ++j) {
                    if (++cur <= k) a[i] += cur;
                }
                break;
            }
        }
        cur += (n - i * 2 + 1) * 4;
    }
    cur = 0;
    for (int i = 1; i <= n / 2; ++i) {
        if (!f || i < f) {
            int len = (n - i * 2 + 1);
            a[i] += ps + cur + 1 + (cur + len * 3 + 1 + cur + len * 4) * len / 2;
            a[n - i + 1] += ps + (cur + len + 1 + cur + len * 2 + 1) * (len + 1) / 2;
            ps += cur + 1 + cur + len * 3 + 1;
            cur += len * 4;
        }
        else {
            if (i == n - i + 1) a[i] += ps;
            else a[i] += ps, a[n - i + 1] += ps;
        }
    }
    if (n & 1) {
        if (!f && cur != k) a[(n + 1) / 2] += ps + cur + 1;
        else a[(n + 1) / 2] += ps;
    }
    for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
    cout << '\n';
    return 0;
}

/*
289 493 599 639 645 645 627 559 409 145
*/

K. free

• 最短路shortest_path
• Dijkstradijkstra

分层图最短路，直接跑 dijkstra 就行。

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, s, t, k;
    cin >> n >> m >> s >> t >> k;
    if (k >= n - 1) {
        cout << "0\n";
        return 0;
    }
    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[0], dis[0] + N * N, 0x3f3f3f3f);
    dis[s][0] = 0;
    q.emplace(dis[s][0], s, 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]) {
            if (dis[y][t] > dis[x][t] + w) {
                dis[y][t] = dis[x][t] + w;
                q.emplace(dis[y][t], y, t);
            }
            if (t != k && dis[y][t + 1] > dis[x][t]) {
                dis[y][t + 1] = dis[x][t];
                q.emplace(dis[y][t + 1], y, t + 1);
            }
        }
    }
    cout << dis[t][k] << '\n';
    return 0;
}

L. number nowcoder

• 数学math
• 字符串string

我们小学学过 3 的整数倍各位数字之和一定是 3 的倍数。然后在此基础上后面加两个 0，就成 300 的倍数了，统计前缀数字和对 3 取模的结果数量即可快速完成。

#include <iostream>

using namespace std;

typedef long long LL;

LL f[3];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    int n = s.length();
    LL res = 0;
    for (int i = 1; i <= n; ++i) {
        res += s[i - 1] == '0';
    }
    if (n > 1) res += s[0] == s[1] && s[0] == '0';
    for (int i = 3; i <= n; ++i) {
        LL g[3];
        for (int j = 0; j < 3; ++j) {
            g[(j + s[i - 3]) % 3] = f[j];
        }
        for (int j = 0; j < 3; ++j) f[j] = g[j];
        f[s[i - 3] % 3]++;
        if (s[i - 1] == '0' && s[i - 2] == '0') res += f[0] + 1;
    }
    cout << res << '\n';
    return 0;
}

其他没做的题

• 猫做梦
• Fantasy
• 无向图
• tree nowcoder
• RNGs
• string nowcoder