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

对不起，我们 45 min 没能 ak 小学组的题，我们比那两个 ak 了小学组的 5 年级学生菜，补药压力我们了😭

A. 星际密信

字符串

cpp

#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;
    for (char c : s) {
        if (isalpha(c)) cout << char('A' + ((c - 'A' + k) % 26 + 26) % 26);
        else cout << c;
    }
    cout << '\n';
    return 0;
}

B. 小兔子爬楼梯

动态规划

cpp

#include <iostream>

using namespace std;

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

LL f[N][2];

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

C. 城堡探险

图搜索

又是裸的倍增板子。

cpp

#include <iostream>

using namespace std;

const int N = 100010;

int f[N][30];

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 >> f[i][0];
    for (int j = 1; j < 30; ++j) {
        for (int i = 1; i <= n; ++i) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    while (m--) {
        int x, y;
        cin >> x >> y;
        for (int i = 0; i < 30; ++i) {
            if (y >> i & 1) x = f[x][i];
        }
        cout << x << '\n';
    }
    return 0;
}

D. 施肥

前缀和
差分数组

分三类差分前缀和。

cpp

#include <iostream>

using namespace std;

const int N = 100010;
typedef long long LL;

LL a[N], b[N][3];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        int l, r, x, y, z;
        cin >> l >> r >> x >> y >> z;
        b[l][0] += z, b[r + 1][0] -= z;
        b[l][1] += y, b[r + 1][1] -= y;
        b[l][2] += x, b[r + 1][2] -= x;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) b[i][j] += b[i - 1][j];
    }
    while (q--) {
        LL x;
        cin >> x;
        cout << x * x * b[x][2] + x * b[x][1] + b[x][0] + a[x] << '\n';
    }
    return 0;
}

E. 精选矿石

动态规划
背包

把所有的重量都先减掉一个最小的，然后 DP 同时统计选择的个数和用掉的（减完之后的）重量，

cpp

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 110, M = 1010;

LL f[N][M], w[N], v[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    LL m, mn = __LONG_LONG_MAX__;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
        mn = min(mn, w[i]);
    }
    fill(f[0], f[0] + N * M, -0x3f3f3f3f3f3f3f3f);
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        w[i] -= mn;
        for (int j = 10 * i; j >= w[i]; --j) {
            for (int k = i; k; --k) {
                f[k][j] = max(f[k][j], f[k - 1][j - w[i]] + v[i]);
            }
        }
    }
    LL res = 0;
    for (int i = 1; i <= n; ++i) {
        if (m < i * mn) break;
        else {
            for (int j = 0; j <= 10 * i; ++j) {
                if (m < mn * i + j) break;
                res = max(res, f[i][j]);
            }
        }
    }
    cout << res << '\n';
    return 0;
}

F. 中位数

排序

小的减多少都没意义，只需要尽可能少且均匀的减少从中位数及后面的数，中位数 -1，后面的依次 -2，-3 ... 把大的扣到前面的数那里，然后再求一遍中位数。

cpp

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;

LL a[N], n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) a[(i + (n + 1) / 2 - 2) % n + 1] -= i;
    sort(a + 1, a + n + 1);
    cout << a[n + 1 >> 1] << '\n';
    return 0;
}

G. meeting2019

树
深度优先搜索
树的直径

问题等价于求关键点构成的虚树的直径，不用真的建出来虚树，只考虑关键点跑两轮 dfs 就能确定。

cpp

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 100010;
int f[N], res = N;
bool g[N];
vector<int> adj[N];

void dfs(int x, int fa) {
    for (int y : adj[x]) {
        if (y == fa) continue;
        f[y] = f[x] + 1;
        dfs(y, x);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }
    int x;
    for (int i = 1; i <= k; ++i) {
        cin >> x;
        g[x] = true;
    }
    dfs(x, 0);
    for (int i = 1; i <= n; ++i) {
        if (g[i] && f[i] > f[x]) x = i;
    }
    f[x] = 0;
    dfs(x, 0);
    for (int i = 1; i <= n; ++i) {
        if (g[i] && f[i] > f[x]) x = i;
    }
    cout << (f[x] + 1 >> 1) << '\n';
    return 0;
}

H. xor nowcoder

异或线性基
线段树
数据结构

把原来的线性基求交集然后检查 x 是否能被表示等价于把线性基求正交补，然后或起来，查询是否和 x 正交等价。然后开线段树维护区间线性基的并。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef unsigned u32;
const int N = 50010;

struct LB {
    u32 b[32]{};

    void insert(u32 x) {
        for (int i = 31; i >= 0; --i) {
            if (x >> i & 1) {
                if (b[i]) x ^= b[i];
                else {
                    b[i] = x;
                    return;
                }
            }
        }
    }

    bool check(u32 x) {
        for (int i = 0; i < 32; ++i) {
            if (b[i] && __builtin_parity(x & b[i])) return false;
        }
        return true;
    }

    LB bu() {
        LB res;
        for (int i = 0; i < 32; ++i) {
            if (!b[i]) {
                u32 x = 1u << i;
                for (int j = 0; j < 32; ++j) {
                    if (b[j] && __builtin_parity(b[j] & x)) x ^= 1u << j;
                }
                res.insert(x);
            }
        }
        return res;
    }

    LB merge(LB t) {
        LB res = *this;
        for (int i = 0; i < 32; ++i) {
            res.insert(t.b[i]);
        }
        return res;
    }
};

LB tr[N * 4], a[N];

void build(int u, int l, int r) {
    if (l == r) tr[u] = a[l].bu();
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u] = tr[u << 1].merge(tr[u << 1 | 1]);
    }
}

bool query(int u, int l, int r, int ql, int qr, u32 x) {
    if (ql <= l && r <= qr) return tr[u].check(x);
    else {
        int mid = l + r >> 1;
        bool f = true;
        if (ql <= mid) f = query(u << 1, l, mid, ql, qr, x);
        if (qr > mid) f &= query(u << 1 | 1, mid + 1, r, ql, qr, x);
        return f;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int t;
        cin >> t;
        while (t--) {
            u32 x;
            cin >> x;
            a[i].insert(x);
        }
    }
    build(1, 1, n);
    while (q--) {
        int l, r;
        u32 x;
        cin >> l >> r >> x;
        cout << (query(1, 1, n, l, r, x) ? "YES" : "NO") << '\n';
    }
    return 0;
}

I. sequence nowcoder

树形 DP
笛卡尔树

考虑固定 a 里面的最小值，然后快速查询 b 能取的最小值和最大值统计答案。在笛卡尔树上做树形 DP 合并的时候统计答案即可。（单调栈 + 线段树 T 飞了才发现只用单调栈就天然的满足要求）

cpp

#include <iostream>
#include <climits>

using namespace std;

typedef long long LL;
const int N = 3000010;
int a[N], b[N];

struct Node {
    LL pre, suf, pm, sm, s;
};

struct Tree {
    int ls, rs;
    Node val;
} tr[N];

LL res = LLONG_MIN;

int st[N], tp;

const Node merge(const Node &l, const Node &r) {
    return {
        max(l.pre, l.s + r.pre),
        max(l.suf + r.s, r.suf),
        min(l.pm, l.s + r.pm),
        min(l.sm + r.s, r.sm),
        l.s + r.s
    };
}

void dfs(int x) {
    if (!x) return;
    dfs(tr[x].ls);
    dfs(tr[x].rs);
    Node &q1 = tr[tr[x].ls].val, q2 = tr[tr[x].rs].val;
    res = max(res, max(
        a[x] * (q1.suf + b[x] + q2.pre),
        a[x] * (q1.sm + b[x] + q2.pm))
    );
    tr[x].val = merge(
        merge(tr[tr[x].ls].val, {max(0, b[x]), max(0, b[x]), min(0, b[x]), min(0, b[x]), b[x]}),
        tr[tr[x].rs].val
    );
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    for (int i = 1; i <= n; ++i) {
        int k = tp;
        while (k && a[i] <= a[st[k]]) k--;
        if (k) tr[st[k]].rs = i;
        if (k < tp) tr[i].ls = st[k + 1];
        st[++k] = i;
        tp = k;
    }
    int rt = st[1];
    dfs(rt);
    cout << res << '\n';
    return 0;
}

其他没做的题

triples I
triples II
merge

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

A. 星际密信 ​

B. 小兔子爬楼梯 ​

C. 城堡探险 ​

D. 施肥 ​

E. 精选矿石 ​

F. 中位数 ​

G. meeting2019 ​

H. xor nowcoder ​

I. sequence nowcoder ​