2025春训第四场 - Star's Blog

因为后面有一场校赛，这场训练赛没什么印象了。

A. 美丽数#

先考虑合法情况，从高位到低位从小到大试填。该位填 i 合法当且仅当 i 和上一位不相等且用掉一次 i 之后剩下的状态是合法状态（即个数最大的数的个数不大于 $\lceil \frac{总数}{2} \rceil$ ）
如果填到某一位时，任何 i 都不合法，那么整体就不合法，输出 -1.

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

4
using namespace std;
5

6
int cnt[10];
7

8
int main() {
9
    int T;
10
    cin >> T;
11
    while (T--) {
12
        vector<int> res;
13
        int s = 0;
14
        for (int i = 0; i < 10; ++i) {
15
            cin >> cnt[i];
16
            s += cnt[i];
17
        }
18
        int pre = 0;
19
        while (s) {
20
            bool flag = false;
21
            for (int i = 0; i < 10; ++i) {
22
                if (i != pre && cnt[i]) {
23
                    int mx = 0;
24
                    for (int j = 0; j < 10; ++j) {
25
                        if (i == j) continue;
26
                        mx = max(mx, cnt[j]);
27
                    }
28
                    if (s - 1 - 2 * mx >= -1 && s - 1 - 2 * (cnt[i] - 1) >= 0) {
29
                        flag = true;
30
                        res.push_back(i);
31
                        s--;
32
                        cnt[i]--;
33
                        pre = i;
34
                        break;
35
                    }
36
                }
37
            }
38
            if (!flag) break;
39
        }
40
        if (s) cout << -1;
41
        for (int i : res) cout << i;
42
        cout << endl;
43
    }
44
    return 0;
45
}

B. 军训#

大水题，如果相邻两个位置的数相差不为 1，就需要切割一次。

1
#include <iostream>
2

3
using namespace std;
4

5
int a[1000010];
6

7
int main() {
8
    int n, t = 0;
9
    scanf("%d", &n);
10
    a[0] = -1;
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%d", &a[i]);
13
        if (a[i] != a[i - 1] + 1 && a[i] != a[i - 1] - 1) t++;
14
    }
15
    printf("%d\n", t - 1);
16
    return 0;
17
}

D. 发工资#

经典的贪心问题，把区间按照右端点排序，对于每一个区间，查找区间内最靠左的金砖给他，找不到就跳过。

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

5
using namespace std;
6

7
pair<int, int> a[1000010];
8
map<int, int> s;
9

10
int main() {
11
    int n, m;
12
    scanf("%d%d", &n, &m);
13
    for (int i = 1; i <= n; ++i) {
14
        scanf("%d%d", &a[i].first, &a[i].second);
15
    }
16
    for (int i = 1; i <= m; ++i) {
17
        int c;
18
        scanf("%d", &c);
19
        s[c]++;
20
    }
21
    sort(a + 1, a + n + 1, [](pair<int, int> a, pair<int, int> b) {
22
        return a.second < b.second;
23
    });
24
    int res = 0;
25
    for (int i = 1; i <= n; ++i) {
26
        auto it = s.lower_bound(a[i].first);
27
        if (it != s.end() && it->first <= a[i].second) {
28
            it->second--;
29
            if (it->second == 0) s.erase(it);
30
            res++;
31
        }
32
    }
33
    printf("%d\n", res);
34
    return 0;
35
}

E. 筹备计划#

最优解应该是开两个权值线段树，分别维护中位数和合法位置。对于每次查询，查询第一个线段树找到中位数，然后在第二个线段树中查左侧第一个和右侧第一个合法位置，比较两个位置的结果即可；比较时还需要再开一个线段树维护前缀和和后缀和。

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

4
using namespace std;
5

6
const int N = 200010;
7

8
struct SegmentTree
9
{
10
    long long tr[N * 4];
11
    int tag[N * 4];
12

13
    SegmentTree() {
14
        memset(tag, -1, sizeof(tag));
15
    }
16

17
    void pushup(int u) {
18
        tr[u] = tr[u << 1] + tr[u << 1 | 1];
19
    }
20

21
    void pushdown(int u, int l, int r) {
22
        if (~tag[u]) {
23
            int mid = l + r >> 1;
24
            tag[u << 1] = tag[u << 1 | 1] = tag[u];
25
            if (tag[u]) tr[u << 1] = mid - l + 1, tr[u << 1 | 1] = r - mid;
26
            else tr[u << 1] = tr[u << 1 | 1] = 0;
27
            tag[u] = -1;
28
        }
29
    }
30

31
    void modify(int u, int l, int r, int p, long long v) {
32
        if (l == r) tr[u] += v;
33
        else {
34
            pushdown(u, l, r);
35
            int mid = l + r >> 1;
36
            if (p <= mid) modify(u << 1, l, mid, p, v);
37
            else modify(u << 1 | 1, mid + 1, r, p, v);
38
            pushup(u);
39
        }
40
    }
41

42
    void modify(int u, int l, int r, int ql, int qr, int v) {
43
        if (ql <= l && r <= qr) {
44
            if (v) tr[u] = r - l + 1;
45
            else tr[u] = 0;
46
            tag[u] = v;
47
        }
48
        else {
49
            pushdown(u, l, r);
50
            int mid = l + r >> 1;
51
            if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
52
            if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
53
            pushup(u);
54
        }
55
    }
56

57
    long long query(int u, int l, int r, int ql, int qr) {
58
        if (ql <= l && r <= qr) return tr[u];
59
        else {
60
            pushdown(u, l, r);
61
            long long res = 0;
62
            int mid = l + r >> 1;
63
            if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
64
            if (qr > mid) res += query(u << 1 | 1, mid + 1, r, ql, qr);
65
            return res;
66
        }
67
    }
68

69
    int kth_element(int u, int l, int r, long long k) {
70
        if (l == r) return l;
71
        else {
72
            pushdown(u, l, r);
73
            int mid = l + r >> 1;
74
            if (tr[u << 1] >= k) return kth_element(u << 1, l, mid, k);
75
            else return kth_element(u << 1 | 1, mid + 1, r, k - tr[u << 1]);
76
        }
77
    }
78
} cnt, pos, sum;
79
int n, q;
80

81
long long calc(int p) {
82
    long long res = 0;
83
    if (p > 1) res = (long long)p * cnt.query(1, 1, n, 1, p - 1) - sum.query(1, 1, n, 1, p - 1);
84
    if (p < n) res += (long long)(-p) * cnt.query(1, 1, n, p + 1, n) + sum.query(1, 1, n, p + 1, n);
85
    return res;
86
}
87

88
int main() {
89
    scanf("%d%d", &n, &q);
90
    for (int i = 1; i <= n; ++i) {
91
        int t;
92
        scanf("%d", &t);
93
        cnt.modify(1, 1, n, i, t);
94
        sum.modify(1, 1, n, i, (long long)t * i);
95
    }
96
    pos.modify(1, 1, n, 1, n, 1);
97
    while (q--) {
98
        int t, a, b;
99
        scanf("%d%d%d", &t, &a, &b);
100
        if (t == 1) {
101
            cnt.modify(1, 1, n, a, b);
102
            sum.modify(1, 1, n, a, (long long)a * b);
103
        }
104
        else if (t == 2) {
105
            cnt.modify(1, 1, n, a, -b);
106
            sum.modify(1, 1, n, a, -(long long)a * b);
107
        }
108
        else if (t == 3) {
109
            pos.modify(1, 1, n, a, b, 1);
110
        }
111
        else {
112
            pos.modify(1, 1, n, a, b, 0);
113
        }
114
        int p = cnt.kth_element(1, 1, n, cnt.query(1, 1, n, 1, n) + 1 >> 1);
115
        int pre_cnt = pos.query(1, 1, n, 1, p), l = -1, r = -1;
116
        if (pre_cnt) l = pos.kth_element(1, 1, n, pre_cnt);
117
        if (pre_cnt < pos.query(1, 1, n, 1, n)) r = pos.kth_element(1, 1, n, pre_cnt + 1);
118
        if (~l && ~r) {
119
            if (calc(l) <= calc(r)) printf("%lld\n", l);
120
            else printf("%lld\n", r);
121
        }
122
        else if (~l) printf("%lld\n", l);
123
        else if (~r) printf("%lld\n", r);
124
        else printf("-1\n");
125
    }
126
    return 0;
127
}

我当时用的更暴力的两个 log 的做法卡过去了——线段树只打标记，用二分查找找到合法位置，浪费了线段树本身的分治结构。

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

4
using namespace std;
5

6
const int N = 200010;
7
long long tr[N], sum[N];
8
int s[N * 4], lazy[N * 4];
9
int n, q;
10

11
inline void pushup(int u) {
12
    s[u] = s[u << 1] + s[u << 1 | 1];
13
}
14

15
inline void pushdown(int u, int l, int r) {
16
    if (~lazy[u]) {
17
        int mid = l + r >> 1;
18
        s[u << 1] = lazy[u] * (mid - l + 1), s[u << 1 | 1] = lazy[u] * (r - mid);
19
        lazy[u << 1] = lazy[u << 1 | 1] = lazy[u];
20
        lazy[u] = -1;
21
    }
22
}
23

24
inline void modify(int u, int l, int r, int ql, int qr, int v) {
25
    if (ql <= l && r <= qr) {
26
        s[u] = (r - l + 1) * v;
27
        lazy[u] = v;
28
    }
29
    else {
30
        pushdown(u, l, r);
31
        int mid = l + r >> 1;
32
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
33
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
34
        pushup(u);
35
    }
36
}
37

38
inline int smt_query(int u, int l, int r, int ql, int qr) {
39
    if (ql <= l && r <= qr) return s[u];
40
    else {
41
        pushdown(u, l, r);
42
        int mid = l + r >> 1, res = 0;
43
        if (ql <= mid) res = smt_query(u << 1, l, mid, ql, qr);
44
        if (qr > mid) res += smt_query(u << 1 | 1, mid + 1, r, ql, qr);
45
        return res;
46
    }
47
}
48

49
inline void add(int u, int k) {
50
    int tmp = u;
51
    for (; u <= n; u += u & -u) {
52
        tr[u] += k;
53
        sum[u] += (long long)tmp * k;
54
    }
55
}
56

57
inline long long query(int u) {
58
    long long res = 0;
59
    for (; u; u -= u & -u) {
60
        res += tr[u];
61
    }
62
    return res;
63
}
64

65
inline long long qs(int u) {
66
    long long res = 0;
67
    for (; u; u -= u & -u) {
68
        res += sum[u];
69
    }
70
    return res;
71
}
72

73
inline long long f(int p) {
74
    return (long long)p * query(p) * 2 - qs(p) * 2 + qs(n) - (long long)query(n) * p;
75
}
76

77
void smt_print() {
78
    for (int i = 1; i <= n; ++i) {
79
        printf("%d ", smt_query(1, 1, n, i, i));
80
    }
81
    printf("\n");
82
}
83

84
void print() {
85
    for (int i = 1; i <= n; ++i) {
86
        printf("%d ", query(i) - query(i - 1));
87
    }
88
    printf("\n");
89
    for (int i = 1; i <= n; ++i) {
90
        printf("%d ", qs(i) - qs(i - 1));
91
    }
92
    printf("\n");
93
}
94

95
int main() {
96
    scanf("%d%d", &n, &q);
97
    for (int i = 1; i <= n; ++i) {
98
        int t;
99
        scanf("%d", &t);
100
        add(i, t);
101
    }
102
    memset(lazy, -1, sizeof(lazy));
103
    while (q--) {
104
        int t, a, b;
105
        scanf("%d%d%d", &t, &a, &b);
106
        if (t == 1) {
107
            add(a, b);
108
        }
109
        else if (t == 2) {
110
            add(a, -b);
111
        }
112
        else if (t == 3) {
113
            modify(1, 1, n, a, b, 0);
114
        }
115
        else {
116
            modify(1, 1, n, a, b, 1);
117
        }
118
        int l = 1, r = n;
119
        long long s = query(n);
120
        while (l < r) {
121
            int mid = l + r >> 1;
122
            if (query(mid) * 2 >= s) r = mid;
123
            else l = mid + 1;
124
        }
125
        if (smt_query(1, 1, n, l, l) == 0) printf("%d\n", l);
126
        else {
127
            int L, R;
128
            int p = l;
129
            l = 0, r = p;
130
            while (l < r) {
131
                int mid = l + r + 1 >> 1;
132
                if (smt_query(1, 1, n, mid, p) < p - mid + 1) l = mid;
133
                else r = mid - 1;
134
            }
135
            L = l;
136
            l = p, r = n + 1;
137
            while (l < r) {
138
                int mid = l + r >> 1;
139
                if (smt_query(1, 1, n, p, mid) < mid - p + 1) r = mid;
140
                else l = mid + 1;
141
            }
142
            R = l;
143
            if (L == 0 && R == n + 1) printf("-1\n");
144
            else if (L == 0) printf("%d\n", R);
145
            else if (R == n + 1) printf("%d\n", L);
146
            else if (f(L) <= f(R)) printf("%d\n", L);
147
            else printf("%d\n", R);
148
        }
149
    }
150
    return 0;
151
}