2025春训第二十三场

昨天栽在二分了，今天写了四个二分一个也没挂，爽😋

A. 互质划分#

事实上，只需要 n / 2 即可，如果所有 2 的倍数都能分开了，那其他的更能分开。

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

4
using namespace std;
5

6
int main() {
7
    long long n;
8
    cin >> n;
9
    cout << max(1LL, n >> 1) << endl;
10
    return 0;
11
}

B. 出租车#

对于每一个居民二分最短距离，在根据最短距离二分出来左右边界的位置，然后检查边界是否合法，最后更新答案； $\Theta(n\log^2 n)$ 完全够了。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 200010;
6

7
int p[N], id[N], s[N], res[N];
8
int n, m;
9

10
int findl(long long val) {
11
    int l = 1, r = n + m;
12
    while (l < r) {
13
        int mid = (l + r) >> 1;
14
        if (p[mid] >= val) r = mid;
15
        else l = mid + 1;
16
    }
17
    return l;
18
}
19

20
int findr(int val) {
21
    int l = 1, r = n + m;
22
    while (l < r) {
23
        int mid = (l + r + 1) >> 1;
24
        if (p[mid] <= val) l = mid;
25
        else r = mid - 1;
26
    }
27
    return l;
28
}
29

30

31
int main() {
32
    scanf("%d%d", &n, &m);
33
    for (int i = 1; i <= n + m; ++i) {
34
        scanf("%d", &p[i]);
35
    }
36
    for (int i = 1; i <= n + m; ++i) {
37
        scanf("%d", &id[i]);
38
        s[i] = s[i - 1] + id[i];
39
    }
40
    for (int i = 1; i <= n + m; ++i) {
41
        if (!id[i]) {
42
            int l = 0, r = 1000000000;
43
            while (l < r) {
44
                int mid = (l + r) >> 1;
45
                if (s[findr((long long)p[i] + mid)] - s[findl((long long)p[i] - mid) - 1]) r = mid;
46
                else l = mid + 1;
47
            }
48
            int L = findl((long long)p[i] - l), R = findr((long long)p[i] + l);
49
            // cout << L << ' ' << R << endl;
50
            if (id[L] && id[R])
51
                if (p[i] - p[L] <= p[R] - p[i]) res[L]++;
52
                else res[R]++;
53
            else if (id[L]) res[L]++;
54
            else if (id[R]) res[R]++;
55
            else return 213;
56
        }
57
    }
58
    for (int i = 1; i <= n + m; ++i) {
59
        if (id[i]) printf("%d ", res[i]);
60
    }
61
    printf("\n");
62
    return 0;
63
}

C. 木雕玩具#

继续二分，二分答案，然后验证需要的人数是否 ≥ 3 即可。以普遍理性而论，应该可以线性 dp 解决，但是这不影响我一直写挂……

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

5
using namespace std;
6

7
const int N = 200010;
8

9
int a[N], n;
10

11
bool check(int mid) {
12
    int t = 0, cur = -0x3f3f3f3f;
13
    for (int i = 1; i <= n; ++i) {
14
        if (a[i] - cur > mid) {
15
            t++;
16
            cur = a[i] + mid;
17
        }
18
    }
19
    return t <= 3;
20
}
21

22
int main() {
23
    scanf("%d", &n);
24
    for (int i = 1; i <= n; ++i) {
25
        scanf("%d", &a[i]);
26
    }
27
    sort(a + 1, a + n + 1);
28
    int l = 0, r = 1000000000;
29
    while (l < r) {
30
        int mid = (l + r) >> 1;
31
        if (check(mid)) r = mid;
32
        else l = mid + 1;
33
    }
34
    printf("%d\n", l);
35
    return 0;
36
}

E. 足球联赛#

It is a 签到题。

1
#include <iostream>
2

3
using namespace std;
4

5
int res[30];
6

7
int main() {
8
    int n, m;
9
    cin >> n >> m;
10
    for (int i = 1; i <= m; ++i) {
11
        int a, b, c, d;
12
        cin >> a >> b >> c >> d;
13
        if (c > d) res[a] += 3;
14
        else if (c == d) res[a]++, res[b]++;
15
        else res[b] += 3;
16
    }
17
    for (int i = 1; i <= n; ++i) {
18
        cout << res[i] << ' ';
19
    }
20
    cout << endl;
21
    return 0;
22
}

F. 果汁#

用贪心的思想，尽可能的往右边倒，给后面更多的可能；同时这么做不影响前面的收益，因为想喝到必须全倒满，如果可以喝到的话先倒前面的和先倒后面的收益一样。

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

4
using namespace std;
5

6
const int N = 30010;
7

8
int v[N];
9

10
void solve() {
11
    int n, m;
12
    scanf("%d%d", &n, &m);
13
    for (int i = 1; i <= m; ++i) {
14
        scanf("%d", &v[i]);
15
    }
16
    v[m + 1] = 0x3f3f3f3f;
17
    map<int, int> mp;
18
    for (int i = 1; i <= n; ++i) {
19
        int t;
20
        scanf("%d", &t);
21
        mp[t]++;
22
    }
23
    int res = 0;
24
    for (auto [i, t] : mp) {
25
        if (v[i + 1] >= t) v[i + 1] -= t;
26
        else {
27
            t -= v[i + 1], v[i + 1] = 0;
28
            res += max(0, t - v[i]);
29
        }
30
    }
31
    printf("%d\n", res);
32
}
33

34
int main() {
35
    int T;
36
    scanf("%d", &T);
37
    while (T--) {
38
        solve();
39
    }
40
    return 0;
41
}

Star's Blog

A. 互质划分#

B. 出租车#

C. 木雕玩具#

E. 足球联赛#

F. 果汁#