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

A. 分糖果

数学

python

n, x, m, k = map(int, input().split())

if n < k * m:
    print(-1)
else:
    print(x * (n - k * m))

B. 今夕是何年

二分查找
数学

cpp

#include <bits/stdc++.h>
#define int long long

using namespace std;

int calc(int a, int b, int c, int n) {
    return n / c + n / a - n / b;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int C, T;
    cin >> C >> T;
    while (T--) {
        int m, a, b, c, n;
        cin >> m >> a >> b >> c >> n;
        int cnt = c / a - c / b + 1;
        int t = (n - 1) / cnt;
        n = (n - 1) % cnt + 1;
        m += t * c;
        int l = m, r = m + c;
        while (l < r) {
            int mid = l + r >> 1;
            // cout << "qwq" << (calc(a, b, c, mid) - calc(a, b, c, m - 1)) << endl;
            if (calc(a, b, c, mid) - calc(a, b, c, m - 1) >= n) r = mid;
            else l = mid + 1;
        }
        cout << l << '\n';
    }
    return 0;
}

C. 乘积

暴力
数学

python

n, x = map(int, input().split())
a = list(map(int, input().split()))

L, R = n, n
for i in range(n):
    prod = 1
    for j in range(i, n):
        prod *= a[j]
        if prod > x:
            break
        elif prod == x:
            if i <= L:
                L = i
                R = min(R, j)
                
if L == n:
    print(-1)
else:
    print(L + 1, R + 1)

D. 倍数调整

暴力
数学

a 肯定不能大到变成 2a，因为之后就相当于没变了，直接暴力所有的 1~2a.

cpp

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

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    LL a, b;
    cin >> a >> b;
    if (a < b) {
        cout << abs(a - b) << '\n';
    }
    else {
        LL res = b - 1;
        for (int i = 2; i < b * 2; ++i) {
            res = min(res, abs(b - i) + min(a % i, i - a % i));
        }
        cout << res << '\n';
    }
    return 0;
}

E. 【树型DP】叶子的染色

树形 DP

又是重复的题

cpp

#include <iostream>

using namespace std;

const int N = 10010;
int head[N], ver[N * 2], ne[N * 2], tot;
int f[N][2], n, m, res;

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

void dp(int x, int fa) {
    if (x > m) f[x][1] = f[x][0] = 1;
    for (int i = head[x]; i; i = ne[i]) {
        int y = ver[i];
        if (y == fa) continue;
        dp(y, x);
        f[x][1] += min(f[y][1] - 1, f[y][0]);
        f[x][0] += min(f[y][0] - 1, f[y][1]);
    }
}

void dfs(int x, int fa) {
    res = min(res, min(f[x][0], f[x][1]));
    for (int i = head[x]; i; i = ne[i]) {
        int y = ver[i];
        if (y == fa || y <= m) continue;
        int bk[4] = {f[x][0], f[x][1], f[y][0], f[y][1]};
        f[x][0] -= min(f[y][0] - 1, f[y][1]);
        f[x][1] -= min(f[y][1] - 1, f[y][0]);
        f[y][1] += min(f[x][1] - 1, f[x][0]);
        f[y][0] += min(f[x][0] - 1, f[x][1]);
        f[x][0] = bk[0], f[x][1] = bk[1], f[y][0] = bk[2], f[y][1] = bk[3];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int c;
        cin >> c;
        f[i][c] = 1;
        f[i][c ^ 1] = m;
    }
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);
    }
    dp(m + 1, 0);
    res = m;
    dfs(m + 1, 0);
    cout << res << endl;
    return 0;
}

F. 聚会

最近公共祖先
树

两两 lca，如果都一样就直接找到了，如果不都一样，那就选那个不一样的（一样的那个是靠上的，下面两个往这里走还是会重复走几条边）

cpp

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

using namespace std;

typedef long long LL;
const int N = 500010;
vector<int> ed[N];
int f[N][30], dep[N];

void dfs(int x) {
    for (int i = 1; i < 30; ++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);
    }
}

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

int get_dis(int x, int y) {
    int res = 0;
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 29; i >= 0; --i) {
        if (dep[f[x][i]] >= dep[y]) x = f[x][i], res += 1 << i;
    }
    if (x == y) return res;
    for (int i = 29; i >= 0; --i) {
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i], res += 2 << i;
    }
    return res + 2;
}

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) {
        int x, y;
        cin >> x >> y;
        ed[x].emplace_back(y), ed[y].emplace_back(x);
    }
    dep[1] = 1;
    dfs(1);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        int f1 = lca(a, b), f2 = lca(a, c), f3 = lca(b, c);
        int m = 0;
        if (f1 == f2 && f2 == f3) m = f1;
        else if (f1 == f2) m = f3;
        else if (f1 == f3) m = f2;
        else m = f1;
        cout << m << ' ' << get_dis(m, a) + get_dis(m, b) + get_dis(m, c) << '\n';
    }
    return 0;
}

K. Fraction Comparision

数学
高精度

cpp

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

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    LL x, y, a, b;
    while (cin >> x >> y >> a >> b) {
        if ((__int128_t)x * b == (__int128_t)y * a) cout << "=\n";
        else if ((__int128_t)x * b > (__int128_t)y * a) cout << ">\n";
        else cout << "<\n";
    }
    return 0;
}

其他没做的题

Random Point in Triangle
Substrings 2
XOR 2019
Points Division

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

A. 分糖果 ​

B. 今夕是何年 ​

C. 乘积 ​

D. 倍数调整 ​

E. 【树型DP】叶子的染色 ​

F. 聚会 ​

K. Fraction Comparision ​

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

A. 分糖果

B. 今夕是何年

C. 乘积

D. 倍数调整

E. 【树型DP】叶子的染色

F. 聚会

K. Fraction Comparision