2024吉林省赛补题记录

阿巴阿巴
啊,省赛,怎么两个月过去了才整理题解,这一定是在复习(确信 502c28827d927240463a58b8a49e94c3

GYM地址:2024吉林省赛

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

数一数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _ = 1;
    // cin >> _;cin.get();
    while(_--)
        solve();

    return 0;
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    ll k, x, y;cin >> k >> x >> y;
    if (k == 1) { cout << x + y << "\n";return; }
    ll ans = 0;
    if (k & 1) {
        ll yi = k / 2;
        if (x <= y / yi) {
            ans += x;
            y -= x * yi;
            x = 0;
            ans += y / (yi + 1);
        }
        else {
            ans += y / yi;
            x -= (y / yi);
            y -= (y / yi) * yi;
            if (y * 2 + x >= k) {
                ans += 1;x -= (k - 2 * y);y = 0;
            }
            ans += x / k;
        }
    }
    else {
        ll tot = x + 2 * y;
        ans = tot / k;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _ = 1;
    cin >> _;cin.get();
    while(_--)
        solve();

    return 0;
}

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct PLAT {
    ll l, r, y;
    operator<(const PLAT& P)const {
        if (y == P.y)return l < P.l;
        return y > P.y;
    }
};

void solve() {
    ll n;cin >> n;
    vector<PLAT>plats;
    for (ll i = 0;i < n;i++) {
        ll l, r, y;cin >> l >> r >> y;
        plats.push_back({ l,r,y });
    }
    sort(plats.begin(), plats.end());
    ll sx, sy;cin >> sx >> sy;
    for (auto p : plats) {
        if (p.l < sx && p.r >= sx && p.y < sy) {
            sy = p.y;
            sx = p.r;
        }
    }
    cout << sx << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _ = 1;
    cin >> _;cin.get();
    while(_--)
        solve();

    return 0;
}

二维平面上有$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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;

struct Point {
    ll x, y;
};

void solve() {
    ll n, k;cin >> n >> k;
    vector<Point>points(n);
    map<ll, vector<ll>>rx;
    for (ll i = 0;i < n;i++) {
        cin >> points[i].x >> points[i].y;
        rx[points[i].x].push_back(i + 1);
    }
    if (rx.size() == k) {
        bool f = true;
        for (auto i : rx) {
            if (i.second.size() < 2) { f = false;break; }
        }
        if (f) {
            for (auto i : rx) {
                cout << i.second.size() << " ";
                for (auto j : i.second) {
                    cout << j << " ";
                }
                cout << "\n";
            }
            return;
        }
    }
    ll b = 1000000;
    map<ll, bool>mpk;
    for (ll i = 0;i < k + 1;i++) {
        for (ll j = i + 1;j < k + 1;j++) {
            ll px = points[i].x, py = points[i].y, qx = points[j].x, qy = points[j].y;
            if (px == qx) {
                continue;
            }
            ld ki = 1.0 * (py - qy) / (px - qx);
            ll kk = (ll)(ki * b);
            if (mpk.count(kk) == 0)mpk[kk] = true;
        }
    }
    for (auto kk : mpk) {
        ld ki = 1.0 * kk.first / b;
        map<ll, vector<ll>>cnt;
        for (ll i = 0;i < n;i++) {
            ll x = points[i].x, y = points[i].y;
            ld bi = y - ki * x;
            ll bb = (ll)(bi * b);
            cnt[bb].push_back(i + 1);
            if (cnt.size() > k)break;
        }
        if (cnt.size() == k) {
            bool f = true;
            for (auto i : cnt) {
                if (i.second.size() < 2) { f = false;break; }
            }
            if (!f)continue;
            for (auto i : cnt) {
                cout << i.second.size() << " ";
                for (auto j : i.second) {
                    cout << j << " ";
                }
                cout << "\n";
            }
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _ = 1;
    // cin >> _;cin.get();
    while (_--)
        solve();

    return 0;
}

有$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$

相关内容