2026夏个人训练赛第五场

A. 拼车计划

cpp

#include <iostream>
#include <iomanip>
 
using namespace std;

const int N = 100010;
double a[N];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    double m, s = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s += a[i];
    }
    double t = (s - m) / n;
    for (int i = 1; i <= n; ++i) {
        cout << fixed << setprecision(2) << a[i] - t << ' ';
    }
    cout << endl;
    return 0;
}

B. 加密破解

cpp

#include <iostream>
#include <cstring>
 
using namespace std;

int a[128], b[128];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        string s, t;
        cin >> s >> t;
        bool f = true;
        for (int i = 0; i < s.length(); ++i) {
            if (a[s[i]] && a[s[i]] != t[i] || b[t[i]] && s[i] != b[t[i]]) {
                f = false;
                break;
            }
            a[s[i]] = t[i], b[t[i]] = s[i];
        }
        cout << (f ? "Yes" : "No") << endl;
    }
    return 0;
}

C. 双人对战

注意到

答案具有单调性，如果 k 个兵能成功，那么 k + 1 个兵一定也能成功
最优防守策略一定是让从根到叶子的最短路径最长
防守方优先在靠近根的边上增兵一定不劣：
- 一方面在靠近根的边上增兵能同时限制更多条路径（如果同时在分叉后的路径上增兵，增的兵一定比这种多）
- 另一方面优先在靠近根的边上增兵，能给每条路线单独增兵留更多机会

二分最长的最短路径的长度（最多能防守的兵力），下界是都放最少的兵的长度，上界是都放最多的兵的长度。对于每个长度从根到叶子树形 DP 计算开销，比较开销和 m 判断是否合法。

cpp

#include <iostream>
#include <cstring>
#include <tuple>
 
using namespace std;
 
typedef long long LL;
const int N = 200010;
 
int head[N], ne[N * 2], ver[N * 2], a[N * 2], b[N * 2], tot;
LL f[N], g[N], m;
tuple<int, int, LL> q[N];
int n;
 
void add(int x, int y, int l, int r) {
    ver[++tot] = y;
    ne[tot] = head[x];
    head[x] = tot;
    a[tot] = l, b[tot] = r - l;
}
 
LL sum, sl = 0;
 
void dfs1(int x, int fa) {
    bool gg = false;
    for (int i = head[x]; i; i = ne[i]) {
        int y = ver[i];
        if (y == fa) continue;
        gg = true;
        dfs1(y, x);
        f[x] = min(f[x], f[y] + a[i]);
        g[x] = min(g[x], g[y] + a[i] + b[i]);
    }
    if (!gg) f[x] = g[x] = 0;
}
 
bool check(LL mid) {
    sum = sl;
    int hh = 0, tt = -1;
    q[++tt] = {1, 0, mid};
    while (hh <= tt) {
        auto [x, fa, lim] = q[hh++];
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (y == fa) continue;
            if (lim - f[y] - a[i] > 0) {
                sum += min((LL)b[i], lim - f[y] - a[i]);
                q[++tt] = {y, x, lim - a[i] - min((LL)b[i], lim - f[y] - a[i])};
            }
        }
    }
    return sum <= m;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(f, 0x3f, sizeof(LL) * (n + 1));
    memset(g, 0x3f, sizeof(LL) * (n + 1));
    for (int i = 1; i < n; ++i) {
        int x, y, l, r;
        cin >> x >> y >> l >> r;
        add(x, y, l, r), add(y, x, l, r);
        sl += l;
    }
    dfs1(1, 0);
    LL l = f[1], r = g[1];
    while (l < r) {
        LL mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l + 1 << endl;
    return 0;
}

D. 英雄小队

注意到只要有一个（两个二进制位）都没有，那么比他们低的位不可能造成贡献，所以只有最后一个连续的不小于 1 的子段是有效的，而这个子段的长度不可能大于 $n$ 。

为什么不可能造成贡献

可以假设最大的情况: $l \dots r$ 每位都有两个，全加起来只能变成 $l + 1 \dots r + 1$ 每位一个，如果 $r + 1$ 位本来就是没有的，就不可能在造成进位了

对于最后一个连续段做线性 DP，维护 $f_{i}$ 表示通过进位得到第 $i$ 位的方案数， $c_{i}$ 表示第 $i$ 位的数量

f_{i} = f_{i - 1} (\binom{c_{i - 1}}{1}) + (\binom{c_{i - 1}}{2}) \overset{数量不大于 2}{=} f_{i - 1} c_{i - 1} + ⌊ \frac{c_{i - 1}}{2} ⌋

cpp

#include <iostream>
#include <algorithm>
 
using namespace std;

const int N = 100010;
const int MOD = 998244353;

typedef long long LL;
int a[N], b[N];
LL f[N];
 
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];
    sort(a + 1, a + n + 1);
    int l = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[i] - a[i - 1] > 1) l = i;
    }
    int m = a[n] - a[l] + 1;
    for (int i = l; i <= n; ++i) {
        b[a[i] - a[l] + 1]++;
    }
    f[0] = b[0] = 0;
    for (int i = 1; i <= m + 1; ++i) {
        f[i] = (f[i - 1] * b[i - 1] + b[i - 1] / 2) % MOD;
    }
    cout << f[m + 1] << endl;
    return 0;
}

E. 数组差异

答案是

\sum_{i, j} | a_{i} - a_{j} | (\binom{n - 2}{k - 2}) i, j = 1 \dots n, i < j

排序后用前缀和批量算 $| a_{i} - a_{j} |$ 即可做到 $O (n)$ 统计答案.

cpp

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;

const int MOD = 1000000007;

typedef long long LL;

LL power(LL n, LL p) {
    LL res = 1, base = n;
    while (p) {
        if (p & 1) res = res * base % MOD;
        base = base * base % MOD;
        p >>= 1;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    LL n, k;
    cin >> n >> k;
    if (k == 1) cout << 0 << endl;
    LL s = 0;
    vector<LL> a(n + 1), p(n + 1); // 数据范围是一个损坏的图片，只能这样了
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * i % MOD;
        cin >> a[i];
        s += a[i];
    }
    sort(a.begin() + 1, a.end());
    LL res = 0;
    // c(n - 2, k - 2)
    LL c = p[n - 2] * power(p[k - 2], MOD - 2) % MOD * power(p[n - k], MOD - 2) % MOD;
    for (int i = 1; i <= n; ++i) {
        res = (res + (s - a[i] * (n - i + 1)) % MOD) % MOD;
        s -= a[i];
    }
    cout << (res * c) % MOD << endl;
    return 0;
}

F. 消费计划

Meet in Middle. 折半搜索然后排序，利用单调性合并搜索结果。

我 答案错误9.1%，因为没有输出 No，不读题是这样的。

cpp

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL a[50];
int b[50], cnt[50], n, k, ls, lt;
pair<LL, int> s[1050000], t[1050000];
LL res, m;

void dfs(int x, int lim, LL sa, int sb, pair<LL, int>* s, int &ls) {
    if (x > lim) {
        s[ls++] = {sa, sb};
        if (sb == 0 && sa >= m) res++;
    }
    else {
        dfs(x + 1, lim, sa, sb, s, ls);
        dfs(x + 1, lim, sa + a[x], sb == -1 ? b[x] : (b[x] == sb ? sb : 0), s, ls);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }
    dfs(1, n / 2, 0, -1, s, ls), dfs(n / 2 + 1, n, 0, -1, t, lt);
    ls--, lt--;
    sort(s + 1, s + ls + 1), sort(t + 1, t + lt + 1);
    // for (int i = 1; i <= ls; ++i) cout << s[i].first << ' ' << s[i].second << endl;
    // cout << endl;
    // for (int i = 1; i <= lt; ++i) cout << t[i].first << ' ' << t[i].second << endl;
    // cout << endl;
    for (int i = 1, j = lt; i <= ls; ++i) {
        while (j && s[i].first + t[j].first >= m) cnt[t[j--].second]++;
        if (s[i].second == 0) res += lt - j;
        else res += lt - j - cnt[s[i].second];
    }
    if (res) cout << res << endl;
    else cout << "No" << endl;
    return 0;
}

G. Run

cpp

#include <iostream>

using namespace std;

typedef long long LL;

const int MOD = 1000000007;
const int N = 100010;

LL f[N][2], g[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int q, k;
    cin >> q >> k;
    f[0][0] = 1;
    for (int i = 1; i <= 100000; ++i) {
        f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
        if (i >= k) f[i][1] = f[i - k][0];
        g[i] = (g[i - 1] + f[i][0] + f[i][1]) % MOD;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ((g[r] - g[l - 1]) % MOD + MOD) % MOD << endl;
    }
    return 0;
}

H. Discount

I. Message

J. Money

贪心的卖，只要下一个比当前贵就买并立刻在下一个卖掉，这样卖到的收益一定最大。把连续的买和卖合并一下就可以得到最少交易数。需要注意特判相等的情况，如果是已经在一轮连续的买卖中了就接着买，否则不开始新的一轮。

cpp

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;

LL a[N];

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, cnt = 0;
        LL res = 0;
        bool f = false;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        if (n == 1) {
            cout << "0 0" << endl;
            continue;
        }
        for (int i = 2; i <= n; ++i) {
            if (a[i] > a[i - 1]) {
                if (!f) f = true, cnt++;
                res += a[i] - a[i - 1];
            }
            else if (a[i] < a[i - 1]) f = false;
        }
        cout << res << ' ' << cnt * 2 << endl;
    }
    return 0;
}

2026夏个人训练赛第五场 ​

A. 拼车计划 ​

B. 加密破解 ​

C. 双人对战 ​

D. 英雄小队 ​

E. 数组差异 ​

F. 消费计划 ​

G. Run ​

H. Discount ​

I. Message ​

J. Money ​

K. Tree VI ​