2025春训第十六场

差点就 ak 了，有点可惜，感谢学姐手下留情😭。

A. Number Maximization#

签到题 * 1

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
int main() {
7
    string s;
8
    cin >> s;
9
    sort(s.begin(), s.end(), greater<char>());
10
    cout << s << endl;
11
    return 0;
12
}

B. Simplified Calendar System#

签到题 * 2

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int a, b, c, d, e, f, g;
7
    cin >> a >> b >> c >> d >> e >> f >> g;
8
    cout << (d - 1 + (e - a) + (f - b) * 30 + (g - c) * 360) % 7 + 1 << endl;
9
    return 0;
10
}

C. Letter Frequency#

签到题 * 3

1
#include <iostream>
2
#include <map>
3

4
using namespace std;
5

6
string s[30];
7

8
int main() {
9
    int n, len = 0;
10
    cin >> n;
11
    for (int i = 1; i <= n; ++i) {
12
        cin >> s[i];
13
        len = max(len, (int)s[i].length());
14
    }
15
    for (int i = 1; i <= len; ++i) {
16
        cout << i << ":";
17
        map<char, int> mp;
18
        for (int j = 1; j <= n; ++j) {
19
            if (s[j].length() >= i) mp[s[j][i - 1]]++;
20
        }
21
        int mx = 0;
22
        for (auto [a, b] : mp) mx = max(mx, b);
23
        for (auto [a, b] : mp) if (b == mx) cout << ' ' << a;
24
        cout << endl;
25
    }
26
    return 0;
27
}

D. Pseudo Pseudo Random Numbers#

数据非常的小，所以直接暴力枚举检查就行，签到题 * 4

1
#include <iostream>
2

3
using namespace std;
4

5
int n, k;
6

7
bool check(int mask) {
8
    int ls = -1, len = 0;
9
    for (int i = 0; i < n; ++i) {
10
        if ((mask >> i & 1) != ls) len = 1;
11
        else len++;
12
        ls = mask >> i & 1;
13
        if (len > k) return false;
14
    }
15
    return true;
16
}
17

18
int main() {
19
    int t = 0;
20
    cin >> n >> k;
21
    for (int i = 0; i < (1 << n); ++i) {
22
        if (check(i)) t++;
23
    }
24
    cout << t << endl;
25
    return 0;
26
}

E. Word Tree#

没什么特别的，就是最小生成树。

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4

5
using namespace std;
6

7
string s[1010];
8
int fa[1010];
9
vector<pair<int, pair<int, int>>> ed;
10

11
int dis(string a, string b) {
12
    int n = a.length();
13
    int d = 0;
14
    for (int i = 0; i < n; ++i) {
15
        d += abs(a[i] - b[i]);
16
    }
17
    return d;
18
}
19

20
int getfa(int x) {
21
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
22
}
23

24
int main() {
25
    ios::sync_with_stdio(0);
26
    cin.tie(0), cout.tie(0);
27
    int n, l;
28
    cin >> n >> l;
29
    for (int i = 1; i <= n; ++i) {
30
        cin >> s[i];
31
        fa[i] = i;
32
        for (int j = 1; j < i; ++j) {
33
            ed.push_back({dis(s[i], s[j]), {i, j}});
34
        }
35
    }
36
    int res = 0;
37
    sort(ed.begin(), ed.end());
38
    for (auto [w, p] : ed) {
39
        int x = getfa(p.first), y = getfa(p.second);
40
        if (x == y) continue;
41
        else {
42
            fa[y] = x;
43
            res = max(res, w);
44
        }
45
    }
46
    cout << res << endl;
47
    return 0;
48
}

F. House Prices Going Up#

树状数组（线段树）模板题。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 500010;
6
long long tr[N];
7
int n;
8
void add(int u, int v) {
9
    for (; u <= n; u += u & -u) {
10
        tr[u] += v;
11
    }
12
}
13

14
long long query(int u) {
15
    long long res = 0;
16
    for (; u; u -= u & -u) {
17
        res += tr[u];
18
    }
19
    return res;
20
}
21

22
int main() {
23
    scanf("%d", &n);
24
    for (int i = 1; i <= n; ++i) {
25
        int t;
26
        scanf("%d", &t);
27
        add(i, t);
28
    }
29
    int q;
30
    scanf("%d", &q);
31
    while (q--) {
32
        char s[2];
33
        int x, y;
34
        scanf("%s%d%d", s, &x, &y);
35
        if (s[0] == 'U') add(x, y);
36
        else printf("%lld\n", query(y) - query(x - 1));
37
    }
38
    return 0;
39
}

G. Which Number#

到这里难度开始正常了，这道题是二分答案+容斥原理，先二分答案，然后用容斥原理检查前面合法的数的个数。

我不慎 WA 了一次好像是爆 long long 了。

1
#include <iostream>
2

3
using namespace std;
4

5
long long a[20], k;
6
long long n;
7

8
bool check(long long mid) {
9
    __int128_t cnt = 0;
10
    for (int mask = 0; mask < (1 << k); ++mask) {
11
        __int128_t t = 1;
12
        int op = 0;
13
        for (int j = 0; j < k; ++j) {
14
            if (mask >> j & 1) {
15
                op++;
16
                t *= a[j];
17
            }
18
        }
19
        op = (op & 1) ? -1 : 1;
20
        cnt += (mid / t) * op;
21
    }
22
    return cnt >= n;
23
}
24

25
int main() {
26
    scanf("%lld%d", &n, &k);
27
    for (int i = 0; i < k; ++i) {
28
        scanf("%lld", &a[i]);
29
    }
30
    __int128_t l = 1, r = __LONG_LONG_MAX__;
31
    while (l < r) {
32
        long long mid = l + r >> 1;
33
        if (check(mid)) r = mid;
34
        else l = mid + 1;
35
    }
36
    printf("%lld\n", (long long)l);
37
    return 0;
38
}

又是一道二分题，考虑这样一个问题，对于一个 lot 如果一块一块的 bid 每一块的收益都会逐渐减小，目标状态是使得最后 bid 了 v 之后目标状态是一个相对均匀的状态。具体来说是让其中的一部分（有可能是全部）在投了 v 之后再投 1 时或者的收益在误差允许的范围内尽可能相等，这样就能最大程度保证每次投的都是最优解。

于是可以二分最终投一块钱的收益，然后计算想把收益压到 ≤ mid 的时候需要 bid 多少，和 v 比较，找到一个尽可能接近 v 的（可以稍微大一点，因为有的情况最后好几个都相等，一降低每个都得 bid 1，无法到 v，但是不影响最后计算，因为都一样，最后投哪个都行）。找到之后按二分的 check 函数的逻辑再跑一次，这一次要加上最大限制 v，跑的过程中记录收益累加即可。

1
#include <iostream>
2
#include <queue>
3

4
using namespace std;
5

6
const int N = 100010;
7

8
struct Node {
9
    double rate;
10
    int tot_val;
11
    int voted = 0, other_vote;
12

13
    bool operator <(const Node &_) const {
14
        return rate < _.rate;
15
    }
16

17
    double vote(int t) {
18
        double r = (double)voted / (voted + other_vote) * tot_val;
19
        voted += t;
20
        rate = (double)(voted + 1) / (voted + other_vote + 1) * tot_val - (double)voted / (voted + other_vote) * tot_val;
21
        return (double)voted / (voted + other_vote) * tot_val - r;
22
    }
23
} a[N];
24
int n, v;
25

26
long long check(double val) {
27
    long long res = 0;
28
    for (int i = 1; i <= n; ++i) {
29
        int l = 0, r = 100000000;
30
        while (l < r) {
31
            int mid = l + r >> 1;
32
            auto bk = a[i];
33
            bk.vote(mid);
34
            if (bk.rate < val) r = mid;
35
            else l = mid + 1;
36
        }
37
        res += l;
38
    }
39
    return res;
40
}
41

42
int main() {
43
    double L = 0, R = 0;
44
    scanf("%d%d", &n, &v);
45
    for (int i = 1; i <= n; ++i) {
46
        scanf("%d%d", &a[i].tot_val, &a[i].other_vote);
47
        a[i].vote(0);
48
        R = max(R, a[i].rate);
49
    }
50
    while (R - L > 1e-9) {
51
        double mid = (L + R) / 2;
52
        if (check(mid) >= v) L = mid;
53
        else R = mid;
54
    }
55
    double res = 0;
56
    for (int i = 1; i <= n; ++i) {
57
        int l = 0, r = v;
58
        while (l < r) {
59
            int mid = l + r >> 1;
60
            auto bk = a[i];
61
            bk.vote(mid);
62
            if (bk.rate < L) r = mid;
63
            else l = mid + 1;
64
        }
65
        res += a[i].vote(l);
66
        v -= l;
67
    }
68
    if (v) return 123;
69
    else printf("%f\n", res);
70
    return 0;
71
}

J. Desert Travel#

基本功大考核，最小生成树 + 树上倍增，思维难度不是很大，但是比较有操作难度，这中间炸了死哪都不知道。

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
#include <vector>
5

6
using namespace std;
7

8
const int N = 5010;
9

10
struct Edge {
11
    int x, y;
12
    double w;
13
} a[N * (N - 1) / 2];
14

15
int x[N], y[N];
16
int fa[N];
17
int f[N][15], dep[N];
18
double g[N][15];
19
vector<pair<double, int>> ed[N];
20

21
int getfa(int x) {
22
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
23
}
24

25
void dfs(int x) {
26
    for (int i = 1; i < 15; ++i) {
27
        f[x][i] = f[f[x][i - 1]][i - 1];
28
        g[x][i] = max(g[x][i - 1], g[f[x][i - 1]][i - 1]);
29
    }
30
    for (auto [w, y] : ed[x]) {
31
        if (y == f[x][0]) continue;
32
        g[y][0] = w;
33
        f[y][0] = x;
34
        dep[y] = dep[x] + 1;
35
        dfs(y);
36
    }
37
}
38

39
int main() {
40
    int n, m = 0;
41
    scanf("%d", &n);
42
    for (int i = 1; i <= n; ++i) {
43
        fa[i] = i;
44
        scanf("%d%d", &x[i], &y[i]);
45
        for (int j = 1; j < i; ++j) {
46
            a[++m] = {j, i, sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2))};
47
        }
48
    }
49
    sort(a + 1, a + m + 1, [](Edge a, Edge b) {
50
        return a.w < b.w;
51
    });
52
    for (int i = 1; i <= m; ++i) {
53
        int x = getfa(a[i].x), y = getfa(a[i].y);
54
        if (x == y) continue;
55
        fa[y] = x;
56
        ed[a[i].x].push_back({a[i].w, a[i].y});
57
        ed[a[i].y].push_back({a[i].w, a[i].x});
58
    }
59
    dep[1] = 1;
60
    dfs(1);
61
    int q;
62
    scanf("%d", &q);
63
    while (q--) {
64
        int x, y;
65
        double res = 0;
66
        scanf("%d%d", &x, &y);
67
        if (dep[x] < dep[y]) swap(x, y);
68
        for (int i = 14; i >= 0; --i) {
69
            if (dep[f[x][i]] >= dep[y]) {
70
                res = max(res, g[x][i]);
71
                x = f[x][i];
72
            }
73
        }
74
        if (x != y) {
75
            for (int i = 14; i >= 0; --i) {
76
                if (f[x][i] != f[y][i]) {
77
                    res = max(res, max(g[x][i], g[y][i]));
78
                    x = f[x][i], y = f[y][i];
79
                }
80
            }
81
            res = max(res, max(g[x][0], g[y][0]));
82
        }
83
        printf("%f\n", res);
84
    }
85
    return 0;
86
}

Star's Blog