小花生

study & life record.

Hello 2025

发表于 分类于 ，

1月4日 Codeforces 实战记录。（1722 -> 1777）

新年第一场，打上1750了！挖个坑，期末周过完整理一下。

比赛地址：Hello 2025。

A. MEX Table

实际上只有 0 存在的行和列取 mex 后非零。

要使这一行一列的和最大，又由于其中必有一个是 1（因为 1 只有 1 个），要使另一个最大，直接使该行/列为从 0 开始的连续数列即可。

因此结果为 max(n, m) + 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, m; cin >> n >> m;
    cout << max(n, m) + 1 << '\n';  
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while(t--) solve();
  return 0;
}

B. Gorilla and the Exam

先给定 k 次修改，然后多次选区间将其中所有最小数删取。

不难发现，修改后，删除的最小次数即为数组中去重数的个数。

因此 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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, k; cin >> n >> k;
    map<int, int>cnt;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        cnt[a]++;
    }
    vector<int>c;
    for(auto [_, x] : cnt){
            c.emplace_back(x);
    }
    sort(c.begin(), c.end());
    int ans = c.size();
    for(int i = 0; i < c.size() - 1; i++){
        	if(k >= c[i]){
        			ans--;
        			k -= c[i];	
        	}
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

C. Trip to the Olympiad

要使 (a ^ b) + (a ^ c) + (b ^ c) 最大，逐位观察，发现当 a, b, c 三个数在某一位上不全为 0 或 1 时，这一位是最理想的。

这样构造：从高位开始，l 和 r 的相同位是不能改变的（为了保证结果在 l 到 r 之间），一旦出现不同位后，让 a 为 1000... , b 为 0111...，就能保证尽可能地使后续位不相同。c 取 l 到 r 之间任意不与 a，b 相同的值即可。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int l, r; cin >> l >> r;
    int a = 0, b = 0, c = 0;
    for(int i = 29; i >= 0; i--){
        if((l ^ r) >> i & 1){
            b |= 1 << i;
            a |= (1 << i) - 1;
            break;
        }
        else{
            a |= l & (1 << i);
            b |= l & (1 << i);
        }
    }
    c = l;
    while(c == a || c == b){
        c++;
    }
    cout << a << " " << b << " " << c << "\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

D. Gifts Order

动态维护：（极差 - 区间长度）的最大值

赛时写了一个非常丑陋的线段树维护两个差分序列的最大连续子段和做过去了，不够优雅，这里用jiangly的思路 orz。

数组传入线段树节点时，做处理（加索引值 或 减索引值），这样（极差 - 区间长度）就变成两种处理后的直接做差了。递增的极差对应减索引值的情况，递减的极差对应加索引值的情况。

线段树每个节点维护 5 个信息：

  • 极差的两点大小递增的，最大值 inc_max
  • 极差的两点大小递增的，最小值 inc_min
  • 极差的两点大小递减的，最大值 dec_max
  • 极差的两点大小递减的，最小值 dec_min
  • 所求答案 ans

合并操作时：

  • 四个极值直接取极值。
  • ans 三种情况：
    • 只用左侧区间，a.ans
    • 只用右侧区间，b.ans
    • 同时使用两侧区间，递增的极差 b.inc_max - a.inc_min，递减的极差 a.dec_max - b.dec_min
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
#define int long long
using namespace std;

template<class Info>
struct SegmentTree {
    int n;
    vector<Info> info;

    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }

    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }

    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
    }
};

constexpr int inf = 1e18;
struct Info {
    int inc_max;
    int inc_min;
    int dec_max;
    int dec_min;
    int ans;
    Info() : inc_max(-inf), dec_max(-inf), dec_min(inf), inc_min(inf), ans(0) {}
    Info(int x, int i) : inc_max(x - i), inc_min(x - i), dec_max(x + i), dec_min(x + i), ans(0) {}
};

Info operator+(const Info &a, const Info &b){
    Info c;
    c.inc_max = max(a.inc_max, b.inc_max);
    c.inc_min = min(a.inc_min, b.inc_min);
    c.dec_max = max(a.dec_max, b.dec_max);
    c.dec_min = min(a.dec_min, b.dec_min);
    c.ans = max({a.ans, b.ans, b.inc_max - a.inc_min, a.dec_max - b.dec_min});
    return c;
}

void solve(){
    int n, q; cin >> n >> q;
    SegmentTree<Info> seg(n);
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        seg.modify(i, Info(a, i));
    }
    cout << seg.query(0, n).ans << '\n';
    while(q--){
        int p, x; cin >> p >> x; p--;
        seg.modify(p, Info(x, p));
        cout << seg.query(0, n).ans << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}