尝试打打 $abc$ 写写题解。
只写了 $A-E$ 的，后两题一点思路没有也就没补了（）。
题目链接：https://atcoder.jp/contests/abc457/tasks

A - Array#

按照题目要求写即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<int, int> pii;
8

9
int a[110];
10

11
void solved(){
12
    int n, x;
13
    cin >> n;
14
    for(int i = 1; i <= n;i++){
15
        cin >> a[i];
16
    }
17
    cin >> x;
18
    cout << a[x] << endl;
19
}
20

21
int main(){
22
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
23
    int t = 1;
24
    while(t--){
25
        solved();
26
    }
27
    return 0;
28
}

B - Arrays#

这里其实是要输入一个每行元素数量不同的特殊二维数组，然后输出对应索引的元素，我这里用了 $map$ 。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<int, int> pii;
8

9
map<int, vector<int>> mp;
10

11
void solved(){
12
    int n;
13
    cin >> n;
14
    for(int i = 1; i <= n;i++){
15
        int t;
16
        cin >> t;
17
        while(t--){
18
            int x;
19
            cin >> x;
20
            mp[i].push_back(x);
21
        }
22
    }
23
    int x, y;
24
    cin >> x >> y;
25
    cout << mp[x][y - 1] << endl;
26
}
27

28
int main(){
29
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
30
    int t = 1;
31
    while(t--){
32
        solved();
33
    }
34
    return 0;
35
}

C - Long Sequence#

这里构造的二维数组跟上一题一样。然后要我们构造一个由每个 $A_i$ 序列的元素按 $C_i$ 个轮次反复压入数组而成 $B$ 数组。我们按它的要求真的压入就会超时。所以我们的选择是判断 $K$ 落在哪个 $A_i$ 序列压入的范围。让( $K -$ 前面压入的总范围)，再对这个序列的元素个数取模，求出具体在单个 $A_i$ 序列中这个 $K$ 的索引是多少。然后输出这个索引对应的元素即可。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<int, int> pii;
8

9
map<int, vector<ll>> mp;
10
ll c[200010];
11

12
void solved(){
13
    ll n, k;
14
    cin >> n >> k;
15
    for(int i = 1; i <= n;i++){
16
        int t;
17
        cin >> t;
18
        while(t--){
19
            int x;
20
            cin >> x;
21
            mp[i].push_back(x);
22
        }
23
    }
24
    for(int i = 1; i <= n;i++){
25
        cin >> c[i];
26
    }
27
    for(int i = 1; i <= n;i++){
28
        ll size = mp[i].size();
29
        if(k > size * c[i]){
30
            k -= size * c[i];
31
        }
32
        else if(k == size * c[i]){
33
            cout << mp[i][size - 1]  << endl;
34
            break;
35
        }
36
        else{
37
            ll temp = k % size;
38
            if(temp == 0){ k = size - 1;}
39
            else {k = temp - 1;}
40
            cout << mp[i][k] << endl;
41
            break;
42
        }
43
    }
44
}
45

46
int main(){
47
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
48
    int _ = 1;
49
    while(_--){
50
        solved();
51
    }
52
    return 0;
53
}

D - Raise Minimum#

这题我们需要转变一下思路。我们如果想要去模拟这个操作的过程肯定是会超时的。但是我们完全可以不去模拟，而是尝试去猜答案，看这个答案是否能够符合条件，然后不断找到一个能满足条件的最大值。而这其实就是二分法。
我们这里用的贪心 $＋$ 二分答案。这里的检查逻辑是如果 $A_i$ 小于目前猜的最小值就进行操作计数。我这里的判断逻辑不是 $i$ 的倍数的就取商加 $1$ ，是就直接取商。（其实还可以写简便一点）然后比较需要的操作次数是否小于等于最大的操作次数限制，是就继续往大的值猜，否就往小的猜。
$tips：$ 这里的二分法右端最大值应该取 $maxa + k$ 。我们考虑一个极端情况。对于 $A_1$ ，假设它和最大值 $maxa$ 相同，然后全部操作 $k$ 都用在它上面，那么最大值也只能去到 $maxa + k$ 。而这就是序列最小值的能达到的极限最大值了。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<int, int> pii;
8

9
ll a[200010];
10
ll n, k;
11
ll mina = 1e18 + 10, maxa = 0;
12

13
bool check(ll x){
14
    ll cnt = 0;
15
    for(int i = 1; i <= n;i++){
16
        if(a[i] < x){
17
            if((x - a[i]) % i != 0){
18
                cnt += ((x - a[i]) / i + 1);
19
            }
20
            else{
21
                cnt += ((x - a[i]) / i);
22
            }
23
            if(cnt > k) return false;
24
        }
25
    }
26
    return cnt <= k;
27
}
28

29
void solved(){
30
    cin >> n >> k;
31
    for (int i = 1; i <= n;i++){
32
        cin >> a[i];
33
        if(a[i] > maxa) {maxa = a[i];}
34
        if(a[i] < mina) {mina = a[i];}
35
    }
36
    ll l = mina, r = maxa + k;
37
    ll ans = mina;
38
    while(l <= r){
39
        ll mid = l + (r - l) / 2;
40
        if(check(mid)){
41
            ans = mid;
42
            l = mid + 1;
43
        }
44
        else{
45
            r = mid - 1;
46
        }
47
    }
48
    cout << ans << endl;
49
}
50

51
int main(){
52
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
53
    int _ = 1;
54
    while(_--){
55
        solved();
56
    }
57
    return 0;
58
}

E - Crossing Table Cloth#

这题依旧是二分题。但是要复杂很多。
核心思路是对于每一次查询时的左(右)端点，我们用一个数组存入它所有右(左)端点的下标。然后通过二分查找找到第一个满足条件的右(左)端点。也就是进行两次查找。(一次以左端点为准，找满足条件的右端点，另一次以右端点为准，找满足条件的左端点)然后通过条件判断。
$1.$ 找不到满足条件的右(左)端点。
$2.$ 两个区间断开了。
$3.$ 满足条件的只有一个区间(这个区间的左端点就是 $s$ ，右端点就是 $t$ ，且没有完全包含在内的子区间)。
这三种情况就直接 $no$ 掉，如果满足就是 $yes$ 了。
这里的前两个条件都很好判断，详细都写在注释里了。
但是这里的判断是否有子区间就比较困难。如果正常地循环去找子区间就是 $O(n^2)$ 会直接超时，这里我们引入了树状数组来优化这种区间查询的情况(可以实现 $O(logN)$ )。最终我们时间复杂度可以压到 $O((M + Q)logN)$ 可以通过题目。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7
typedef pair<int, int> pii;
8

9
int n, m;
10

11
// 树状数组
12
struct BIT {
13
    int n;
14
    vector<int> bit;
15
    BIT(int n_) : n(n_), bit(n_ + 2, 0) {}     //初始化结构体
16
    void add(int i, int v) {
17
        for(; i <= n; i += i & -i) bit[i] += v;   //先给当前的区间加值，然后不断给父区间（包含这个区间的大区间）也加值
18
    }
19
    int sum(int i){
20
        int s = 0;
21
        for (; i > 0; i -= i & -i) s += bit[i];  //从最大区间开始，不断查找小区间，累加小区间的值计入总和，然后返回这个总和
22
        return s;
23
    }
24
};
25

26
void solved(){
27
    cin >> n >> m;
28
    vector<vector<int>> L(n + 1), R(n + 1);       //对应每一个左(右)端点，向数组中存入对应右(左)端点的下标
29

30
    for(int i = 0; i < m;i++){
31
        int l, r;
32
        cin >> l >> r;
33
        L[l].push_back(r);
34
        R[r].push_back(l);
35
    }
36

37
    //保证二分的单调性
38
    for(int i = 1; i <= n;i++){
39
        sort(L[i].begin(), L[i].end());
40
        sort(R[i].begin(), R[i].end());
41
    }
42

43
    //查询
44
    int q;
45
    cin >> q;
46
    vector<array<int, 3>> Q(q);
47
    //对应的每次查询i，Q[i][0]表示左端点，Q[i][0]右端点，Q[i][2]为此时对应的下标i
48
    for (int i = 0; i < q; i++){
49
        cin >> Q[i][0] >> Q[i][1];
50
        Q[i][2] = i;     //保存下标的原因是因为后续要用树状数组需要重新排序，但对应结果要存入正确的下标。
51
    }
52

53
    vector<array<int, 3>> sorted_Q = Q;           //复制一个排序的Q方便树状数组操作
54
    sort(sorted_Q.begin(), sorted_Q.end(), [](auto& a, auto& b){
55
        return a[0] > b[0];   //对Q[i][0]从大到小排序，后续我们记录右端点要从大到小进行。
56
    });
57

58
    BIT bit(n);         //创建树状数组
59
    int cur = n;        //cur记录当前操作到的下标。
60
    vector<int> cnt_within(q, 0);   //记录每次查询时，对应给出的区间内含有多少个子区间(包含它给出的这个区间本身)
61

62

63
    for(auto & [s, t, idx] : sorted_Q){
64
        while(cur >= s){          //当目前操作到的cur比目前的s大的话就继续向L[cur]里存有的右端点记入树状数组中，因为此时左端点>=cur的值都已经被加入BIT里了。
65
            for (int r : L[cur]){
66
                bit.add(r, 1);     //往r下标在树状数组中的区间加1(也就是bit[r]的值加1)，然后会在BIT里面继续也给父区间加1。
67
            }
68
            cur--;                 //当前cur的右端点都计入了之后就下一个cur
69
        }
70
        cnt_within[idx] = bit.sum(t);     //对于一个已经完成的查询内的s(所有右端点已经计入)，我们就计算它和它的子区间的总个数和(也就是我们存入的值)
71
    }
72

73
    //针对原来正常顺序的每一次查询进行二分
74
    for(auto & [s, t, idx] : Q){
75
        auto& vecL = L[s];
76
        auto itR = upper_bound(vecL.begin(), vecL.end(), t);   //找到第一个大于t的右端点itR，后续会itR--(也就是对应小于或者等于t的那个下标)
77
        if(itR == vecL.begin()) {   //说明第一个元素就比t大，没有符合条件的itR，直接no掉
78
            cout << "No" << endl;
79
            continue;
80
        }
81
        itR--;
82
        int maxR = *itR;   //存入此时itR对应的值(也就是满足条件的最大的右端点t的下标)
83

84
        auto& vecR = R[t];
85
        auto itL = lower_bound(vecR.begin(), vecR.end(), s);      //找到第一个大于等于左端点s的itL，所以不用减。
86
        if(itL == vecR.end()){         //如果最后一个元素都不能满足就直接no掉
87
            cout << "No" << endl;
88
            continue;
89
        }
90
        int minL = *itL;  //存入此时的itL的值(也就是满足条件的最小的左端点的s的下标)
91

92
        //如果两个区间没有连接在一起就no掉
93
        if(maxR < minL - 1) {
94
            cout << "No" << endl;
95
            continue;
96
        }
97

98
        //判断我们找到的两个区间是否最左端点是S，最右端点是T，并且区间内有两个及以上的子区间(包含本身)。是则yes
99
        bool has_st = (maxR == t && minL == s);
100
        if(has_st && cnt_within[idx] == 1){
101
            cout << "No" << endl;
102
        }
103
        else{
104
            cout << "Yes" << endl;
105
        }
106
    }
107
}
108

109
    int main(){
110
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
111
    solved();
112
    return 0;
113
}

树状数组#

我们拿这道题目用到的 $BIT$ 来说明一下。
我们首先要理解 $bit[i]$ 里的 $i$ 代表的其实是一个区间。比如 $6$ 其实代表的是 $[5,6]$ 这个区间， $7$ 代表的是 $[7,7]$ 这个区间。它是这样理解的。 $6$ 对应的区间长度由它的二进制从右往左第一次出现 $1$ 的位置对应的 $2$ 的幂值来决定。 $6$ 的二进制为 $110$ ，所以它对应的区间长度就是 $2^1 = 2$ ， $7$ 的是 $111$ ，所以它的区间长度是 $2^0 = 1$ ，同理 $8$ 就是 $2^3 = 8$ 。所以我们可以通过这种方式划分区间：
$1$ 对应 $[1,1]$ ， $2$ 对应 $[1,2]$ ， $3$ 对应 $[3,3]$ ， $4$ 对应 $[1,4]$ ，以此类推， $[5,5]$ ， $[5,6]$ ， $[7,7]$ ， $[1,8]$ 。
那么我们就会发现一个规律，每到一个二次幂就是一个大区间，这个大区间我们就可以存放对应区间 $[1,n]$ 含有的所有的值。所以我们在插入值时，我们就可以利用 $i += i \& -i$ (本质上就是根据区间长度进行跳转)这个条件来不断跳转我们要赋值的 $i$ 对应的 $bits[i]$ 。然后我们发现一旦它跳转到了一个大区间(二次幂对应的区间)，它接下来就只会在大区间里继续向上跳了。(因为大区间的区间长度都是二次幂，跳转也是这个大小)因此通过这种方式，我们小区间内的值都会被传递到大区间内然后不断向上传递，这里其实就是 $add$ 插入值的原理，显然是一个 $O(logN)$ 级别的插入。
同理我们来看看查询一个对应区间内的总值(也就是 $sum$ )应该怎么查询。我们查询一个右端点，也就是最大的 $i$ 所在的区间。我们通过向下跳转 $i -= i \& -i$ ，会不断向下面的区间跳转。每跳转一个区间我们就将其中的值 $bit[i]$ 加入总和 $s$ 中。然后一旦跳转到一个大区间(二次幂对应的区间)，下一步就会直接结束循环了，而此时大区间对应的值就是前面 $[1, n]$ 所有的总值了，(插入的原理)我们本次的查询就结束了。显然通过这种跳转的方式，查询也是一个 $O(logN)$ 级别的查询。
在本题中树状数组的优化就显得十分高效，利用方式也完全基于这个原理。只不过区间最小端点变成了查询时的 $s$ ，而不是 $1$ 。

NOTE
这里的 $i \& -i$ 其实就是原数和补码取合，然后就会取到二进制里从右往左第一个为 $1$ 的位对应的二次幂。

1
// 树状数组
2
struct BIT {
3
    int n;
4
    vector<int> bit;
5
    BIT(int n_) : n(n_), bit(n_ + 2, 0) {}     //初始化结构体
6
    void add(int i, int v) {
7
        for(; i <= n; i += i & -i) bit[i] += v;   //先给当前的区间加值，然后不断给父区间（包含这个区间的大区间）也加值
8
    }
9
    int sum(int i){
10
        int s = 0;
11
        for (; i > 0; i -= i & -i) s += bit[i];  //从最大区间开始，不断查找小区间，累加小区间的值计入总和，然后返回这个总和
12
        return s;
13
    }
14
};

Mkrari的个人博客

A - Array#

B - Arrays#

C - Long Sequence#

D - Raise Minimum#

E - Crossing Table Cloth#

树状数组#