2024吉林省赛补题记录

GYM地址：2024吉林省赛

题目顺序按照从易到难排序。

I. The Easiest Problem

题意

数一数

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
void solve() {
6
    string s = "Scan the QR code to sign in now.";
7
    ll cnt = 0;
8
    for (auto c : s) {
9
        if (c <= 'z' && c >= 'a')cnt++;
10
    }
11
    cout << cnt << endl;
12
}
13

14
int main() {
15
    ios::sync_with_stdio(false);
16
    cin.tie(0);
17
    int _ = 1;
18
    // cin >> _;cin.get();
19
    while(_--)
20
        solve();
21

22
    return 0;
23
}

L. Recharge

题意

有 $x$ 次获得 $1$ 格能量的机会， $y$ 次获得 $2$ 格能量的机会，充满一个电池需要 $k$ 格能量，溢出的能量会被浪费，问最多能充满多少电池。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
void solve() {
6
    ll k, x, y;cin >> k >> x >> y;
7
    if (k == 1) { cout << x + y << "\n";return; }
8
    ll ans = 0;
9
    if (k & 1) {
10
        ll yi = k / 2;
11
        if (x <= y / yi) {
12
            ans += x;
13
            y -= x * yi;
14
            x = 0;
15
            ans += y / (yi + 1);
16
        }
17
        else {
18
            ans += y / yi;
19
            x -= (y / yi);
20
            y -= (y / yi) * yi;
21
            if (y * 2 + x >= k) {
22
                ans += 1;x -= (k - 2 * y);y = 0;
23
            }
24
            ans += x / k;
25
        }
26
    }
27
    else {
28
        ll tot = x + 2 * y;
29
        ans = tot / k;
30
    }
31
    cout << ans << "\n";
32
}
33

34
int main() {
35
    ios::sync_with_stdio(false);
36
    cin.tie(0);
37
    int _ = 1;
38
    cin >> _;cin.get();
39
    while(_--)
40
        solve();
41

42
    return 0;
43
}

G. Platform Game

题意

在二维平面中有 $n$ 个平台，每个平台有一个高度 $h_i$ ，以及一个左端点 $l_i$ 和右端点 $r_i$ 。机器人从 $(x,y)$ 出发，保持向右前进，如果遇到平台端点则会垂直下落，问机器人最终的落点。

思路

排序题，按照高度从高到低、左端点从小到大排序，遍历平台，如果机器人在平台上则更新机器人的位置。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
struct PLAT {
6
    ll l, r, y;
7
    operator<(const PLAT& P)const {
8
        if (y == P.y)return l < P.l;
9
        return y > P.y;
10
    }
11
};
12

13
void solve() {
14
    ll n;cin >> n;
15
    vector<PLAT>plats;
16
    for (ll i = 0;i < n;i++) {
17
        ll l, r, y;cin >> l >> r >> y;
18
        plats.push_back({ l,r,y });
19
    }
20
    sort(plats.begin(), plats.end());
21
    ll sx, sy;cin >> sx >> sy;
22
    for (auto p : plats) {
23
        if (p.l < sx && p.r >= sx && p.y < sy) {
24
            sy = p.y;
25
            sx = p.r;
26
        }
27
    }
28
    cout << sx << "\n";
29
}
30

31
int main() {
32
    ios::sync_with_stdio(false);
33
    cin.tie(0);
34
    int _ = 1;
35
    cin >> _;cin.get();
36
    while(_--)
37
        solve();
38

39
    return 0;
40
}

D. Parallel Lines

题意

二维平面上有 $k$ 条平行线，这些直线上有 $n$ 个点，已知每条直线上至少有 $2$ 个点。现在给出 $n$ 个点，找出这 $k$ 条平行线（用点表示）。

数据范围

$2 \leq n \leq 10^4$

$1 \leq k \leq \min(50, \frac{n}{2})$

思路

注意 $k$ 的范围， $k$ 最多为 $50$ ，可以枚举 $k$ 来选择平行线的斜率，对于 $k$ 条平行线，当我选择了 $k+1$ 个点时，这 $k+1$ 个点中必然至少有两个点之间的斜率是 $k$ 条平行线的斜率。

确定斜率 $k_i$ 之后，我们分别计算过每个点斜率为 $k_i$ 的直线在 $y$ 轴上的截距，并计数相同截距的点的数目，注意垂直于 $x$ 轴的情况。

只有同时符产生截距数目恰好为 $k$ ，且每个截距的点数目至少为 $2$ 时，我们才找到了所要的 $k$ 条平行线。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef double ld;
5

6
struct Point {
7
    ll x, y;
8
};
9

10
void solve() {
11
    ll n, k;cin >> n >> k;
12
    vector<Point>points(n);
13
    map<ll, vector<ll>>rx;
14
    for (ll i = 0;i < n;i++) {
15
        cin >> points[i].x >> points[i].y;
16
        rx[points[i].x].push_back(i + 1);
17
    }
18
    if (rx.size() == k) {
19
        bool f = true;
20
        for (auto i : rx) {
21
            if (i.second.size() < 2) { f = false;break; }
22
        }
23
        if (f) {
24
            for (auto i : rx) {
25
                cout << i.second.size() << " ";
26
                for (auto j : i.second) {
27
                    cout << j << " ";
28
                }
29
                cout << "\n";
30
            }
31
            return;
32
        }
33
    }
34
    ll b = 1000000;
35
    map<ll, bool>mpk;
36
    for (ll i = 0;i < k + 1;i++) {
37
        for (ll j = i + 1;j < k + 1;j++) {
38
            ll px = points[i].x, py = points[i].y, qx = points[j].x, qy = points[j].y;
39
            if (px == qx) {
40
                continue;
41
            }
42
            ld ki = 1.0 * (py - qy) / (px - qx);
43
            ll kk = (ll)(ki * b);
44
            if (mpk.count(kk) == 0)mpk[kk] = true;
45
        }
46
    }
47
    for (auto kk : mpk) {
48
        ld ki = 1.0 * kk.first / b;
49
        map<ll, vector<ll>>cnt;
50
        for (ll i = 0;i < n;i++) {
51
            ll x = points[i].x, y = points[i].y;
52
            ld bi = y - ki * x;
53
            ll bb = (ll)(bi * b);
54
            cnt[bb].push_back(i + 1);
55
            if (cnt.size() > k)break;
56
        }
57
        if (cnt.size() == k) {
58
            bool f = true;
59
            for (auto i : cnt) {
60
                if (i.second.size() < 2) { f = false;break; }
61
            }
62
            if (!f)continue;
63
            for (auto i : cnt) {
64
                cout << i.second.size() << " ";
65
                for (auto j : i.second) {
66
                    cout << j << " ";
67
                }
68
                cout << "\n";
69
            }
70
            return;
71
        }
72
    }
73
}
74

75
int main() {
76
    ios::sync_with_stdio(false);
77
    cin.tie(0);
78
    int _ = 1;
79
    // cin >> _;cin.get();
80
    while (_--)
81
        solve();
82

83
    return 0;
84
}

E. Connected Components

题意

有 $n$ 个王国，编号从 $1$ 到 $n$ ，每个王国有两个属性值 $a_i$ 和 $b_i$ ，如果两个王国的属性值满足 $a_i - a_j \leq i - j \leq b_i - b_j$ 或 $a_j - a_i \leq j - i \leq b_j - b_i$ ，则这两个王国是相连的。问有多少个连通块。

数据范围

$1 \leq n \leq 10^6$