2025春个人训练赛第四场

一大堆的签到题和模板题。

cpp

#include <iostream>

using namespace std;

int main() {
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    if (max(0, (e - a) * b) >= max(0, (e - c) * d)) cout << 1 << endl;
    else cout << 2 << endl;
    return 0;
}

B. Judge Meetings

cpp

#include <iostream>

using namespace std;

int a[200];

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 t;
        cin >> t;
        for (int j = 1; j <= t; ++j) {
            int l, r;
            cin >> l >> r;
            for (int k = l; k <= r; ++k) a[k]++;
        }
    }
    int res = 0;
    for (int i = 1; i <= m; ++i) {
        if (n - a[i] >= 3) res++;
    }
    cout << res << endl;
    return 0;
}

C. Single-Elimination Tournament

cpp

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 21; i >= 0; --i) {
        if ((1 << i) <= n) {
            cout << (n - (1 << i)) * 2 << endl;
            break;
        }
    }
    return 0;
}

D. Simplified Dart Game

100 - 到中心点的切比雪夫距离 * 10

cpp

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, r, c;
    cin >> n >> r >> c;
    n = (n + 1) >> 1;
    cout << 100 - max(abs(r - n), abs(c - n)) * 10 << endl;
    return 0;
}

E. Cover Your Bases

cpp

#include <iostream>

using namespace std;

int get(string a, int b) {
    int res = 0;
    for (char c : a) {
        if (c - 48 >= b) return -1;
        res = res * b + c - 48;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string a, b;
    int c;
    cin >> a >> b >> c;
    for (int i = 2; i <= 10; ++i) {
        for (int j = 2; j <= 10; ++j) {
            int aa = get(a, i), bb = get(b, j);
            if (aa != -1 && bb != -1 && aa + bb == c) {
                cout << i << ' ' << j << endl;
                exit(0);
            }
        }
    }
    return 0;
}

F. Country Roads

把所有的已有的和还没有的边全放一起跑最小生成树

cpp

#include <iostream>
#include <algorithm>
#include <tuple>

using namespace std;

typedef long long LL;
const int N = 100010, M = 400010;
tuple<int, int, int> ed[M];
int fa[N];

int getfa(int x) {
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, r;
    cin >> n >> m >> r;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        auto &[_, x, y] = ed[i];
        cin >> x >> y;
    }
    for (int i = 1; i <= r; ++i) {
        auto &[v, x, y] = ed[i + m];
        cin >> x >> y >> v;
    }
    m += r;
    sort(ed + 1, ed + m + 1);
    LL res = 0;
    for (int i = 1; i <= m; ++i) {
        auto [v, x, y] = ed[i];
        x = getfa(x), y = getfa(y);
        if (x == y) continue;
        else res += v, fa[y] = x;
    }
    cout << res << endl;
    return 0;
}

G. World Population

线段树

cpp

#include <iostream>
#include <algorithm>
#include <tuple>

using namespace std;

typedef long long LL;
const int N = 500010;

LL tr[N * 4];

void modify(int u, int l, int r, int p, LL v) {
    if (l == r) tr[u] += v;
    else {
        int mid = l + r >> 1;
        if (p <= mid) modify(u << 1, l, mid, p, v);
        else modify(u << 1 | 1, mid + 1, r, p, v);
        tr[u] = tr[u << 1] + tr[u << 1 | 1];
    }
}

LL query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[u];
    else {
        int mid = l + r >> 1;
        LL res = 0;
        if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
        if (qr > mid) res += query(u << 1 | 1, mid + 1, r, ql, qr);
        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 v;
        cin >> v;
        modify(1, 1, n, i, v);
    }
    int q;
    cin >> q;
    while (q--) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'U') modify(1, 1, n, a, b);
        else cout << query(1, 1, n, a, b) << endl;
    }
    return 0;
}

H. Who wants to be a Millionaire?

线性 dp，开一个 $f_{i, j}$ 表示连续答对前 i 个题并且用了 j 次提问机会的概率，每次枚举当前题是否提问。每道题都统计一次答案。

cpp

#include <iostream>
#include <iomanip>

using namespace std;

typedef long long LL;
typedef long double LD;
const int N = 110;
LD f[N][3], a[N], b[N];
LL c[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 >> c[i];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    f[0][0] = f[0][1] = f[0][2] = 1.0;
    LD res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j >= 0; --j) {
            if (j > 0) f[i][j] = max(f[i - 1][j] * a[i], f[i - 1][j - 1] * b[i]);
            else f[i][j] = f[i - 1][j] * a[i];
        }
        res = max(res, f[i][2] * c[i]);
    }
    cout << fixed << setprecision(10) << res << endl;
    return 0;
}

I. Farmers’ Market

cpp

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a * b + 11) / 12 * c << endl;
    return 0;
}

J. Basketball Score

cpp

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    int g = a + b * 2 + c * 3, h = d + e * 2 + f * 3;
    if (g == h) cout << 0 << endl;
    else if (g > h) cout << 1 << endl;
    else cout << 2 << endl;
    return 0;
}

K. Injured Shoulder

直接暴力

cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> m;
    for (int i = 0; i < m; ++i) {
        string t;
        cin >> t;
        bool one = false;
        for (string s : a) {
            if (s == t) {
                one = true;
                break;
            }
        }
        if (one) cout << 1 << endl;
        else {
            bool two = false;
            for (string s : a) {
                for (string ss : a) {
                    if (s + ss == t) {
                        two = true;
                        break;
                    }
                }
            }
            if (two) cout << 2 << endl;
            else cout << 0 << endl;
        }
    }
    return 0;
}

L. Income Inequality

从大到小排个序，然后暴力所有的情况。

cpp

#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef long double LD;
const int N = 1000010;

LL a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    LL s = 0, cur = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s += a[i];
    }
    sort(a + 1, a + n + 1, greater<LL>());
    LD res = 0;
    for (int i = 1; i <= n; ++i) {
        cur += a[i];
        res = max(res, ((LD)cur / s - (LD)i / n) * 100);
    }
    cout << fixed << setprecision(10) << res << endl;
    return 0;
}

M. What's the Order Anyway?

直接暴力所有的排列依次检查

cpp

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

using namespace std;

const int N = 20;
int a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, c;
    cin >> n >> c;
    int t = 1;
    for (int i = 1; i <= n; ++i) a[i] = i, t *= i;
    vector<tuple<int, int, int>> b(c);
    for (auto &[a, b, c] : b) {
        char c1, c2;
        cin >> a >> c1 >> c2;
        b = c1 - 'A' + 1, c = c2 - 'A' + 1;
    }
    int res = 0;
    for (int tt = 0; tt < t; ++tt) {
        bool f = true;
        for (auto [op, x, y] : b) {
            if (op == 1) {
                if (a[x] > a[y]) {
                    f = false;
                    break;
                }
            }
            else if (op == 2) {
                if (a[x] < a[y]) {
                    f = false;
                    break;
                }
            }
            else if (op == 3) {
                if (abs(a[x] - a[y]) == 1) {
                    f = false;
                    break;
                }
            }
        }
        res += f;
        next_permutation(a + 1, a + n + 1);
    }
    cout << res << endl;
    return 0;
}

N. Rectangular Dry Land

确定一个矩形需要四个限制（两个角的横纵坐标），枚举其中三个，然后二分最后一个， $O (n \log n)$ 正好可以过。

cpp

#include <iostream>

using namespace std;

const int N = 210;
int s[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            s[i][j] = (c == '0') + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            for (int L = 1; L <= m; ++L) {
                int l = L - 1, r = m;
                while (l < r) {
                    int R = l + r + 1 >> 1;
                    if (s[j][R] - s[i - 1][R] - s[j][L - 1] + s[i - 1][L - 1] == 0) l = R;
                    else r = R - 1;
                }
                res = max(res, (l - L + 1) * (j - i + 1));
            }
        }
    }
    cout << res << endl;
    return 0;
}

O. Picture Caption

二分答案

cpp

#include <iostream>

using namespace std;

const int N = 100010;
int a[N], n, k;

bool check(int mid) {
    int t = 1, cur = -1;
    for (int i = 1; i <= n; ++i) {
        if (a[i] > mid) return false;
        else if (a[i] + cur + 1 <= mid) cur += a[i] + 1;
        else t++, cur = a[i]; 
    }
    return t <= k;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int l = 0, r = 1000100000;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

Q. Weekend Gardening

主要难点在于不重不漏，所有的选择可以抽象的理解成一颗树。暴力从小到大枚举 c, n, e 各自的个数，可以发现只要有一步走到了 $[L, H]$ 之间，那么这整个子树都是合法的，直接在这里结算结果，后续如果遇到了子树上的也合法的点直接忽略。检验是否已经被算过也很简单，因为我们是从小到大枚举的，检验是不是第一个合法的只需要判断撤销最后一步后能不能回到一个小于 L 的位置，如果能说明他就是这棵合法的子树的根，需要统计；反之就直接忽略。只有最后一步是有影响的，其他的顺序是不重要的，所以枚举个数是可行的，统计答案时只需要枚举一下最后一步是从哪里来的。

假定三种花一共有 $c_{1}, c_{2}, c_{3}$ 个，你分别选了 $i, j, k$ 个，且最后一步选了第一种花，那么走进这棵子树的概率是

p = \frac{(\binom{c_{1}}{i}) (\binom{c_{2}}{j}) (\binom{c_{3}}{k}) \cdot (\binom{i}{1}) \cdot A_{i + j + k - 1}^{i + j + k - 1}}{A_{c_{1} + c_{2} + c_{3}}^{i + j + k}} = \frac{(\binom{c_{1}}{i}) (\binom{c_{2}}{j}) (\binom{c_{3}}{k}) \cdot (\binom{i}{1}) \cdot}{(\binom{c_{1} + c_{2} + c_{3}}{i + j + k}) \cdot (i + j + k)}

其他的同理，因为数太大了，建议 python 或者 java

python

import math

L, H = map(int, input().split())
c, n, e = map(int, input().split())
c1, c2, c3 = map(int, input().split())

res = 0

for i in range(c1 + 1):
    for j in range(c2 + 1):
        for k in range(c3 + 1):
            t = i * c + j * n + k * e
            if t in range(L, H + 1):
                if i and t - c < L:
                    res += math.comb(c1, i) * math.comb(c2, j) * math.comb(c3, k) * i / math.comb(c1 + c2 + c3, i + j + k) / (i + j + k)
                if j and t - n < L:
                    res += math.comb(c1, i) * math.comb(c2, j) * math.comb(c3, k) * j / math.comb(c1 + c2 + c3, i + j + k) / (i + j + k)
                if k and t - e < L:
                    res += math.comb(c1, i) * math.comb(c2, j) * math.comb(c3, k) * k / math.comb(c1 + c2 + c3, i + j + k) / (i + j + k)

print(f"{res :.10f}")

2025春个人训练赛第四场 ​

A. Social Security Benefits ​

B. Judge Meetings ​

C. Single-Elimination Tournament ​

D. Simplified Dart Game ​

E. Cover Your Bases ​

F. Country Roads ​

G. World Population ​

H. Who wants to be a Millionaire? ​

I. Farmers’ Market ​

J. Basketball Score ​

K. Injured Shoulder ​

L. Income Inequality ​

M. What's the Order Anyway? ​

N. Rectangular Dry Land ​

O. Picture Caption ​

Q. Weekend Gardening ​