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

A. 瞬移

cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    int res = 0, cur = 0;
    for (int i = 1; i <= n; ++i) {
        int t;
        cin >> t;
        if (t == 0) cur++;
        else res = max(res, cur), cur = 0;
    }
    cout << max(res, cur) + 1 << '\n';
    return 0;
}

B. 回文串

优先让他变成回文串，然后在考虑

还剩两次: 直接找到第一个不是 a 的，带着和他对称的位置变成 a
还剩一次: 上次改掉的如果不是 a 把这两个都改成 a，否则如果是奇数把中间的位置改成 a

cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    int n = s.length(), l = s.length() >> 1, t = 2;
    vector<int> p;
    for (int i = 0; i < l; ++i) {
        if (s[i] != s[n - i - 1]) {
            p.emplace_back(i);
        }
    }
    if (p.empty()) {
        for (int i = 0; i < l; ++i) {
            if (s[i] != 'a') {
                s[i] = s[n - i - 1] = 'a';
                break;
            }
        }
    }
    else if (p.size() == 2) {
        for (int i : p) s[i] = s[n - i - 1] = min(s[i], s[n - i - 1]);
    }
    else {
        if (min(s[p[0]], s[n - p[0] - 1]) == 'a') {
            if (n & 1) s[l] = 'a';
        }
        s[p[0]] = s[n - p[0] - 1] = 'a';
    }
    cout << s << '\n';
    return 0;
}

C. 代价

左边的删除的部分可以拼到右边，这样就变成选一个分割点了，枚举起点（左边砍掉后留下的第一个的位置）二分左边 0 和右边 1 数量相等的位置。

cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int n = s.length();
        s = " " + s + s;
        int res = n;
        vector<int> ps(n * 2 + 1, 0);
        for (int i = 1; i <= n * 2; ++i) {
            ps[i] = ps[i - 1] + (s[i] == '1');
        }
        for (int i = 1; i <= n; ++i) {
            int l = i - 1, r = min(i + n - 1, n);
            while (l < r) {
                int mid = l + r >> 1;
                if (mid - i + 1 - (ps[mid] - ps[i - 1]) >= ps[i + n - 1] - ps[mid]) r = mid;
                else l = mid + 1;
            }
            // cout << l << ' ' << l - i + 1 - (ps[l] - ps[i - 1]) << ' ' << ps[i + n - 1] - ps[l] << '\n';
            res = min(res, max(l - i + 1 - (ps[l] - ps[i - 1]), ps[i + n - 1] - ps[l]));
        }
        cout << res << '\n';
    }
    return 0;
}

D. 异或

打表发现不合法的很少，n 到 2e5 的时候才只有 400 多，对于每一个不合法的值暴力处理，然后用总的减掉就好了。

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 400010;
int a[N], b[N], cnt[N], len;

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

    int lim = (1 << 18) - 1;
    for (int i = 1; i <= lim; ++i) {
        int t = i, l = sqrt(i);
        bool f = false;
        for (int j = 2; j <= l; ++j) {
            int cnt = 0;
            while (t % j == 0) cnt++, t /= j;
            if (cnt & 1) {
                f = true;
                break;
            }
        }
        if (t != 1) f = true;
        if (!f) b[++len] = i;
    }
    int cur = 0;
    long long res = (long long)n * (n + 1) / 2;
    cnt[cur] = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        cur ^= a[i];
        for (int j = 0; j <= len; ++j) {
            res -= cnt[cur ^ b[j]];
        }
        cnt[cur]++;
    }
    cout << res << '\n';
    return 0;
}

E. 赛车

[NOIP 2016 提高组] 天天爱跑步，我一眼认出来了，然后复制了之前的代码。一个维护非常多信息的树上差分。

cpp

#include <cstdio>
#include <vector>

using namespace std;

const int N = 300010;

struct Node{
    int val;
    bool op;
};

int nxt[N * 2], ver[N * 2], head[N];
int tot;

int w[N];
int n, m;

int f[N][21], dep[N];

vector<Node> u[N], d[N];
int uu[N * 2], dd[N * 2];
int res[N];

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

void init(int x) {
    for (int i = 1; i <= 20; ++i) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == f[x][0]) continue;
        f[y][0] = x;
        dep[y] = dep[x] + 1;
        init(y);
    }
}

int lca(int x, int y) {
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    for (int i = 20; i >= 0; --i) {
        if (dep[f[y][i]] >= dep[x]) y = f[y][i];
    }
    if (x == y) return x;
    for (int i = 20; i >= 0; --i) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i], y = f[y][i];
        }
    }
    return f[x][0];
}

void dfs(int x) {
    int cnt = uu[dep[x] + w[x]] + dd[w[x] - dep[x] + n];
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == f[x][0]) continue;
        dfs(y);
    }
    for (auto it : u[x]) {
        if (it.op) uu[it.val]++;
        else uu[it.val]--;
    }
    for (auto it : d[x]) {
        if (it.op) dd[it.val]++;
        else dd[it.val]--;
    }
    res[x] = uu[dep[x] + w[x]] + dd[w[x] - dep[x] + n] - cnt;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &w[i]);
    }
    dep[1] = 1;
    init(1);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        int fa = lca(x, y);
        u[x].push_back({dep[x], 1});
        u[f[fa][0]].push_back({dep[x], 0});
        d[y].push_back({dep[x] - 2 * dep[fa] + n, 1});
        d[fa].push_back({dep[x] - 2 * dep[fa] + n, 0});
    }
    dfs(1);
    for (int i = 1; i <= n; ++i) printf("%d ", res[i]);
    return 0;
}

其他没做的题

靶向药物治疗
消灭ISIS恐怖组织
maximum clique 1
subsequence 1
subsequence 2
three points 1
three points 2

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

A. 瞬移 ​

B. 回文串 ​

C. 代价 ​

D. 异或 ​