2026夏个人训练赛第十九场

A. 试吃

贪心

只要相邻三个里有两个就可以把所有人都弄成一样的。

cpp

#include <iostream>

using namespace std;

const int N = 200010;
int a[N];
bool f[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        fill(f + 1, f + n + 1, 0);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        if (n == 2) cout << (a[1] == a[2] ? a[1] : -1) << endl;
        else {
            for (int i = 3; i <= n; ++i) {
                if (a[i] == a[i - 1] || a[i] == a[i - 2]) f[a[i]] = true;
                else if (a[i - 1] == a[i - 2]) f[a[i - 1]] = true;
            }
            int t = 0;
            for (int i = 1; i <= n; ++i) if (f[i]) cout << i << ' ', t = 1;
            if (!t) cout << -1;
            cout << endl;
        }
    }
    return 0;
}

B. 工作任务

双指针

cpp

#include <iostream>

using namespace std;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, res = 0;
    LL k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i], a[i] += a[i - 1];
    for (int i = 1; i <= m; ++i) cin >> b[i], b[i] += b[i - 1];
    for (int i = 0, j = m; i <= n; ++i) {
        while (j >= 0 && a[i] + b[j] > k) j--;
        if (j >= 0 && a[i] + b[j] <= k) res = max(res, i + j);
    }
    cout << res << '\n';
    return 0;
}

C. 学习计划

二分查找
排序

只用考虑目标名次相邻的人达成目标需要的时间范围，二分一下交点确定范围（有的恒成立，有的卡上界，有的卡下界，有的恒不成立），如果能同时满足就可以，然后输出下界，否则就 -1.

cpp

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

typedef long long LL;
const int N = 200010;
LL h[N], a[N];
pair<int, int> t[N];

LL solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> t[i].first, t[i].second = i;
    LL l = 0, r = LLONG_MAX;
    sort(t + 1, t + n + 1);
    for (int i = 2; i <= n; ++i) {
        // need: h[pre] > h[cur]
        int pre = t[i - 1].second, cur = t[i].second;
        if (a[pre] == a[cur]) {
            if (h[pre] <= h[cur]) return -1;
        }
        else if (a[pre] > a[cur]) {
            if (h[pre] <= h[cur]) {
                LL L = 0, R = 2000000000LL;
                while (L < R) {
                    LL mid = L + R >> 1;
                    if (h[pre] + (__int128_t)mid * a[pre] > h[cur] + (__int128_t)mid * a[cur]) R = mid;
                    else L = mid + 1;
                }
                l = max(l, L);
            }
        }
        else {
            if (h[pre] <= h[cur]) return -1;
            else {
                LL L = 0, R = 2000000000LL;
                while (L < R) {
                    LL mid = L + R + 1 >> 1;
                    if (h[pre] + mid * a[pre] > h[cur] + mid * a[cur]) L = mid;
                    else R = mid - 1;
                }
                r = min(r, L);
            }
        }
    }
    return l <= r ? l : -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cout << solve() << '\n';
    }
    return 0;
}

D. 魔法井字棋

大模拟，不想写……

G. Palindromic Partitions

字符串
贪心
哈希

贪心的分段，只要前后缀相等就拿掉，检查字符串相等可以直接用哈希。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

uint64_t h1[N], h2[N], p1[N], p2[N];

uint64_t get1(int l, int r) {
    return h1[l - 1] * p1[r - l + 1] - h1[r];
}

uint64_t get2(int l, int r) {
    return h2[l - 1] * p2[r - l + 1] - h2[r];
}

bool eq(int l, int r, int len) {
    return get1(l, l + len - 1) == get1(r, r + len - 1) && get2(l, l + len - 1) == get2(r, r + len - 1);
}

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();
        p1[0] = p2[0] = 1;
        for (int i = 1; i <= n; ++i) {
            p1[i] = p1[i - 1] * 131;
            p2[i] = p2[i - 1] * 1331;
            h1[i] = h1[i - 1] * 131 + s[i - 1];
            h2[i] = h2[i - 1] * 1331 + s[i - 1];
        }
        int res = 0;
        int l = 1;
        for (int i = 1; i <= (n >> 1); ++i) {
            int len = i - l + 1;
            if (eq(l, n - i + 1, len)) l = i + 1, res += 2;
        }
        if ((n & 1) || (l != (n >> 1) + 1)) res++;
        cout << res << '\n';
    }
    return 0;
}

H. Preserve Connectivity

树
最近公共祖先
深度优先搜索

求虚树的边数，直接套模板就行。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;
vector<int> ed[N], ved[N];
int f[N][20], dep[N], qs[N];
int v[N * 2], len;
int dfn[N], t;

void dfs(int x) {
    dfn[x] = ++t;
    for (int i = 1; i < 20; ++i) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int y : ed[x]) {
        if (y == f[x][0]) continue;
        dep[y] = dep[x] + 1;
        f[y][0] = x;
        dfs(y);
    }
}

bool cmp(int x, int y) {
    return dfn[x] < dfn[y];
}

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

int dfs2(int x, int fa) {
    int res = 0;
    for (int y : ved[x]) {
        if (y == fa) continue;
        res += dfs2(y, x) + dep[y] - dep[x];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        ed[x].emplace_back(y), ed[y].emplace_back(x);
    }
    dep[1] = 1;
    dfs(1);
    int q;
    cin >> q;
    while (q--) {
        int k, res = 0;
        cin >> k;
        for (int i = 1; i <= k; ++i) cin >> qs[i];
        len = 0;
        sort(qs + 1, qs + k + 1, cmp);
        for (int i = 1; i < k; ++i) {
            v[++len] = qs[i];
            v[++len] = lca(qs[i], qs[i + 1]);
        }
        v[++len] = qs[k];
        sort(v + 1, v + len + 1, [](int x, int y) {
            return dfn[x] < dfn[y];
        });
        len = unique(v + 1, v + len + 1) - v - 1;
        for (int i = 1; i <= len; ++i) ved[v[i]].clear();
        for (int i = 1; i < len; ++i) {
            ved[lca(v[i], v[i + 1])].emplace_back(v[i + 1]);
        }
        cout << dfs2(v[1], 0) << '\n';
    }
    return 0;
}

M. Music Game

动态规划
概率论

令 $f_{i, j}$ 表示前 i 场已经连胜 j 场的概率， $g_{i, j}$ 表示期望。

\begin{aligned} f_{i, j} & = {\begin{cases} \sum_{j \in [0, i - 1]} (1 - p_{i}) f_{i - 1, j} & j = 0 \\ p_{i} f_{i - 1, j - 1} & others \end{cases} \\ g_{i, j} & = {\begin{cases} \sum_{j \in [0, i - 1]} (1 - p_{i}) g_{i - 1, j} & j = 0 \\ p_{i} (g_{i - 1, j - 1} + f_{i - 1, j - 1} (j^{m} - (j - 1)^{m})) & others \end{cases} \end{aligned}

答案是 $\sum g_{n, i}$ .

cpp

#include <iostream>

using namespace std;

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

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

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 inv100 = power(100, MOD - 2);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = a[i] * inv100 % MOD;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        LL win = a[i], lose = (MOD + 1 - a[i]) % MOD;
        f[i][0] = f[i - 1][0] * lose % MOD;
        g[i][0] = g[i - 1][0] * lose % MOD;
        for (int j = 1; j <= i; ++j) {
            f[i][j] = f[i - 1][j - 1] * win % MOD;
            f[i][0] = (f[i][0] + f[i - 1][j] * lose) % MOD;

            g[i][j] = (g[i - 1][j - 1] + f[i - 1][j - 1] * ((power(j, m) - power(j - 1, m) + MOD) % MOD) % MOD) * win % MOD;
            g[i][0] = (g[i][0] + g[i - 1][j] * lose) % MOD;
        }
    }
    LL res = 0;
    for (int i = 0; i <= n; ++i) res = (res + g[n][i]) % MOD;
    cout << res << '\n';
    return 0;
}

2026夏个人训练赛第十九场

A. 试吃

B. 工作任务

C. 学习计划

D. 魔法井字棋

G. Palindromic Partitions

H. Preserve Connectivity

M. Music Game

E. 邮票收集

F. 音符序列

I. Circulant Matrix

J. Enumeration not optimization

K. Gambling

L. The number of circuits

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

A. 试吃 ​

B. 工作任务 ​

C. 学习计划 ​

D. 魔法井字棋 ​

G. Palindromic Partitions ​

H. Preserve Connectivity ​

M. Music Game ​

E. 邮票收集 ​

F. 音符序列 ​

I. Circulant Matrix ​

J. Enumeration not optimization ​

K. Gambling ​

L. The number of circuits ​

2026夏个人训练赛第十九场

A. 试吃

B. 工作任务

C. 学习计划

D. 魔法井字棋

G. Palindromic Partitions

H. Preserve Connectivity

M. Music Game

E. 邮票收集

F. 音符序列

I. Circulant Matrix

J. Enumeration not optimization

K. Gambling

L. The number of circuits