2024 YAC Round 1 题解

A. 三妖精SAY WA!!!

题目描述

即求出数组中 小于等于 上界 mm 的最大三数之和。「YAC Round 1」三妖精SAY WA!!!

解法一 （暴力枚举）

由于数据范围较小，n≤100n \le 100，可以直接三重循环枚举三个数暴力解决这个问题，时间复杂度为 O(n3)O(n^3)。(注意三个数要求下标不重复)

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;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 110;

int a[N], n, m, res;

int main(){
    ios;

    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ )
        for(int j = i + 1; j <= n; j ++ )
            for(int k = j + 1; k <= n; k ++ ){
                int sum = a[i] + a[j] + a[k];
                if(sum <= m) res = max(res, sum);
            }
    cout << res << '\n';

    return 0;
}

解法二 （枚举 + 二分）

我们需要在小于等于上界 mm 的条件下，最大化三数之和的最大值，显然这个问题具有二段性，即 当三数之和 sum≤m\text{sum} \le m 时，此时的和满足条件 “小于等于 mm”；当 sum>m\text{sum} > m，此时的和则不满足。

故我们可以尝试用二分查找加以优化。先对数组进行排序，再枚举前两个数字，然后在区间 [j+1,n][j + 1, n] 范围内二分查找找到一个 a[mid]a[mid] （midmid 为第三个数下标）找到三数之和 a[i]+a[j]+a[mid]a[i] + a[j] + a[mid] 在小于等于 mm 条件下的最大值。这样就可以省去第三重循环，时间复杂度为 O(nlog⁡n)O(n \log n).

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 110;

int a[N], n, m, res;

int main(){
    ios;

    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    sort(a + 1, a + n + 1); // 排序

    for(int i = 1; i <= n; i ++ )
        for(int j = i + 1; j <= n; j ++ ){
            int l = j + 1, r = n;
            if(l > r) continue;  // 注意这里要提前退出
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(a[i] + a[j] + a[mid] <= m) l = mid;
                else r = mid - 1;
            }
            int sum = a[i] + a[j] + a[l];
            if(sum <= m) res = max(res, sum); // 最后还需要再check一次
        }
    cout << res << '\n';

    return 0;
}

B. 夜雀之歌

题目描述

构造一个长度为 nn 的 0101 字符串，满足 恰好 有 pp 个不处于字符串两端的 00 两边是 11，且输出字典序最小的构造方案。「YAC Round 1」夜雀之歌

解题思路 （贪心）

需要满足 pp 个字符 00 两边是 11，我们最少需要 p+1p + 1 个字符 11 。也就是说，我们至少需要 2×p+12 \times p + 1 个字符可以进行构造，所以当 n<2×p+1n < 2 \times p + 1 时，不可能完成构造，故直接输出 −1-1 。

对于 n≥2×p+1n \ge 2 \times p + 1 的情况，在满足 pp 个 00 两边有 11 的情况下，为了使得字典序最小，我们只需要最少的 p+1p + 1 个字符 11，并且尽可能地把 多余的 字符 00 放在前面即可（也就是构造成类似于 000…010101000 \ldots 010101 的形式。当然，也有可能没有多余的 00 ）。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int n, p; 

int main(){
    ios;

    int T = 1; cin >> T;
    while(T -- ){
        cin >> n >> p;
        if(n < 2 * p + 1){ // 判断是否可以构造
            cout << -1 << '\n';
            continue;
        }

        string res = "";
        for(int i = 2 * p + 1; i < n; i ++ ) res += "0"; // 多余的0
        for(int i = 1; i <= p; i ++ ) res += "10";       // p个满足的 0
        res += "1";  // 最后再加一个 1
        cout << res << '\n';    
    }

    return 0;
}

C. BBA

题目描述

统计字符串中 “bba”“\text{bba}” 型 子序列 个数，字符串只包含小写英文字符。「YAC Round 1」BBA

解题思路 （前缀和）

这里给出一个比较好理解的方法。（也有更好的做法，欢迎讨论）

对于 “bba”“\text{bba}” 型子序列，只需要枚举每个位置的字符，然后观察前面与当前位置字符不同的每种字符各有多少个，然后累加一下组合数即可。

例如，枚举到当前位置 ii 的字符为 c\text{c}，我们需要统计在位置 ii 前面除字符 c\text{c} 以外 a, b, d ... z\text{a, b, d ... z} 各有多少个，其中对于字符 q\text{q}，有 cntcnt 个，那么用当前位置 ii 的字符 c\text{c} 和前面的字符 q\text{q} 构成 “bba”“\text{bba}” 型字符串的方案数就是 Ccnt2C_{cnt}^2，也就是 cnt×(cnt−1)2\frac{cnt \times (cnt - 1)}{2} 。

字符串只包含小写英文字符，所以我们只需要预处理每个字符的前缀和。cnt[i][j]cnt[i][j] 表示区间 [1,i][1, i] 内字符 ′a′+j'a' + j 的总个数。

最后枚举每个位置，再枚举每个 与当前位置字符不同 的字符，累加答案即可。（注意开 long long\text{long long}）

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 1e5 + 10;

int n;
string s;
ll cnt[N][26]; // 每个字符的前缀和

int main(){
    ios;

    cin >> n >> s;
    s = " " + s;
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j < 26; j ++ )
            cnt[i][j] = cnt[i - 1][j] + (s[i] - 'a' == j);

    ll res = 0;
    for(int i = 3; i <= n; i ++ )
        for(int j = 0; j < 26; j ++ )
            if(j != s[i] - 'a') 
                res += cnt[i - 1][j] * (cnt[i - 1][j] - 1) / 2;
    
    cout << res << '\n';

    return 0;
}

当然，我们可以发现累加答案时，只需要知道前面一个位置的数量，所以可以在累加答案的同时统计每个字符的个数，而且可以直接省去第一个维度。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;

int n;
string s;
ll cnt[26];

int main(){
    ios;

    cin >> n >> s;
    s = " " + s;

    ll res = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 0; j < 26; j ++ )
            if(j != s[i] - 'a') res += cnt[j] * (cnt[j] - 1) / 2;
        cnt[s[i] - 'a'] ++ ;
    }

    cout << res << '\n';

    return 0;
}

D. 魔法使的事，能叫偷吗？

题目描述

在序列中找到一个包含数字 1,2,3…,m1, 2, 3 \ldots , m 的最小长度的连续区间 [l,r][l, r] 。若有多组解，输出 ll 最小的那个。（数据保证一定有解）「YAC Round 1」魔法使的事，能叫偷吗？

解法一 （二分 + 滑动窗口）

显然，连续区间的长度 lenlen 越长，包含的书的数量越多，更有可能包含所有种类的书。假设最终得到的区间的长度为 ansans，当 len≥anslen \ge ans 时，序列中存在一个连续区间 [l,r][l, r] 包含了所有种类的书；当 len<anslen < ans 时，序列中不存在区间 [l,r][l, r] 满足条件。可以看出该问题具有二段性。

所以，我们可以二分答案（区间长度），check\text{check} 函数中，顺序枚举当前长度的起点 ll 和终点 rr，如果当前区间 [l,r][l, r] 已经包含了所有种类的书，则直接返回 true\text{true}；如果枚举到最后都没有满足的区间，则返回 false\text{false} 。

对于区间 [l,r][l, r] 内是否包含所有种类的书这个问题，可以用一个计数数组 cntcnt 和一个计数变量 diffdiff 来实现一个 滑动窗口 算法。其中 cntcnt 数组统计的是 每个种类的书出现的次数，diffdiff 统计的是 当前区间内不同种类的书的个数。

先预处理初始情况下的滑动窗口，起点 l=1l = 1。对于当前种类为 cc 的书，若 cnt[c]=0cnt[c] = 0，则表明此种类的书在当前区间未出现过，此时 $cnt[c] ++ $ 的同时，还需要 $diff ++ $；若 cnt[c]≠0cnt[c] \not = 0，则表明已经出现过，只需要 $cnt[c] ++ $。

接着移动滑动窗口，对于新进入窗口的数 a[r]a[r]，如果 cnt[a[r]]=0cnt[a[r]] = 0，需要 $diff ++ $。对于离开窗口的数 a[l−1]a[l - 1]，如果 $cnt[a[l-1]] – $ 后，cnt[a[l−1]]=0cnt[a[l - 1]] = 0，此时说明区间内不再有种类为 a[l−1]a[l - 1] 的书，故需要进行 $diff – $。

对于当前的区间 [l,r][l, r]， 处理完这些操作后，若 diff=mdiff = m，则包含了所有种类的书，此时就返回起点 ll（由于是顺序枚举的，第一个满足的 ll 就是答案）。如果枚举到最后都没有满足的 ll，则返回 00。

最终时间复杂度为 O(nlog⁡n)O(n \log n)

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 1e6 + 10, M = 2010;

int n, m;
int a[N], cnt[M];

int check(int mid){
    memset(cnt, 0, sizeof cnt); // 初始化每个种类计数

    // 预处理初始化窗口
    int l = 1, r = mid, diff = 0; // diff 统计区间内不同种类数
    for(int i = l; i <= r; i ++ ){
        if(!cnt[a[i]]) diff ++ ;
        cnt[a[i]] ++ ;
    }
    if(diff == m) return l; // 若满足直接返回

    // 滑动窗口 注意操作的顺序
    for(l = 2, r = mid + 1; r <= n; l ++ , r ++ ){
        if(!cnt[a[r]]) diff ++ ;          // 出现新种类
        cnt[a[l - 1]] -- , cnt[a[r]] ++ ; // a[l - 1] 离开，a[r] 进入窗口
        if(cnt[a[l - 1]] == 0) diff -- ;  // 有种类被删去
        if(diff == m) return l;
    }

    return 0;
}

int main(){
    ios;

    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    int l = m, r = n;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    int s = check(r), e = s + r - 1; // 起点 s, 终点 e 为起点加上长度r 再 - 1
    cout << s << ' ' << e << endl; 

    return 0;
}

解法二 （双指针）

可以用双指针遍历数组来记录所有满足条件的区间 [l,r][l, r] 。我们还是需要一个计数数组 cntcnt 和一个计数变量 diffdiff，cntcnt 数组统计的是 每个种类的书出现的次数，diffdiff 统计的是 当前区间内不同种类的书的个数。

如果当前 diff<mdiff < m，此时右指针 rr 往后移动，并判断 $r ++ $ 后的 a[r]a[r] 是否出现过，同时增加计数。

如果当前 diff=mdiff = m，此时的区间 [l,r][l, r] 是满足要求的，故更新答案。我们注意到当前 rr 之后所有的 r′r^{'} 与当前的 ll 所构成的区间 [l,r′][l, r^{'}] 也都一定是满足条件的，而且区间长度还一定比当前的 [l,r][l, r] 更大。

所以，为了省去这些多余的情况，我们这时候需要将 a[l]a[l] 从区间中移除，也就是左指针 ll 往后走，并更新区间中的计数。遍历完后得到的答案就是最短且 ll 最小的区间。时间复杂度为 O(n)O(n)

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e6 + 10, M = 2010, inf = 0x3f3f3f3f;

int n, m;
int a[N], cnt[M];

int main(){
    ios;

    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    // 双指针
    int l = 1, r = l, diff = 1, res = inf, res_l, res_r;
    cnt[a[1]] = 1;
    while(l <= r && r <= n){
        if(diff == m){
            if(res > r - l + 1){  // 更新答案
                res = r - l + 1;
                res_l = l, res_r = r;
            }
            cnt[a[l]] -- ;
            if(!cnt[a[l ++ ]]) diff -- ; // 右指针往后走
        }else{
            if(!cnt[a[ ++ r]]) diff ++ ; // 左指针往后走
            cnt[a[r]] ++ ;
        }
    }
    cout << res_l << ' ' << res_r << '\n';

    return 0;
}

E. 时间冻结

题目描述

NN 个点，MM 条无向边，可以 最多 选择 KK 条边将其长度缩减为原先长度的一半，求 11 到 NN 的最短距离。（边的长度一定是偶数，所以不用担心出现浮点数情况）「YAC Round 1」时间冻结

解法一 （dijkstra + DP 最短路）

KK 的范围很小，故可以在更新最短路的时候记录使用的符卡数量，这是典型的 DPDP 最短路做法。

dist[v][cnt]dist[v][cnt] 表示 使用了 cntcnt 张符卡状态下 11 到 vv 的最短距离。走一遍最短路算法，最后枚举一下使用不同符卡数量到达重点 NN 的距离取最小值即可。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 60, M = 2010, inf = 0x3f3f3f3f;

int h[N], e[M], ne[M], w[M], idx; // 链式前向星
void add(int a, int b, int c){
    e[ ++ idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}

int n, m, K;
int dist[N][N]; // dist[v][cnt] 使用了cnt张符卡状态下1到v的最短距离
bool st[N][N];  // st[v][cnt] 状态是否已经在最短路径网络中
struct node{int d, u, cnt;}; // d 为距离，u 为到达的点，cnt 记录的是符卡使用次数
struct cmp{ // 运算符重载
    bool operator () (const node &a, const node &b){
        return a.d > b.d; // 根据距离排序
    }
};

// 堆优化 dijkstra
void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;
    priority_queue<node, vector<node>, cmp > q;
    q.push(node{dist[1][0], 1, 0});

    while(q.size()){
        auto [d, u, cnt] = q.top();
        q.pop();

        if(st[u][cnt]) continue;
        st[u][cnt] = true;

        for(int i = h[u]; i; i = ne[i]){
            int v = e[i], c = w[i];
            if(dist[v][cnt] > d + c){ // 当前不使用符卡
                dist[v][cnt] = d + c;
                q.push(node{dist[v][cnt], v, cnt});
            }
            if(cnt < K){ // 还有符卡可以用
                if(dist[v][cnt + 1] > d + (c >> 1)){ // 使用符卡
                    dist[v][cnt + 1] = d + (c >> 1);
                    q.push(node{dist[v][cnt + 1], v, cnt + 1});
                }
            }
        }
    }
}

int main(){
    ios;

    cin >> n >> m >> K;
    while(m -- ){
        int u, v, c; cin >> u >> v >> c;
        add(u, v, c), add(v, u, c); // 无向边
    }

    dijkstra();

    int res = inf;
    for(int i = 0; i <= K; i ++ ) res = min(res, dist[n][i]);
    cout << res << endl;

    return 0;
}

解法二 （dijkstra + 分层图）

我们可以通过构建分层图，在分层图上跑一遍最短路即可。

对于一条边 {u,v,w}\{ u, v, w\}，每个点构建 K+1K + 1 个点。同层的点 u+k×nu + k \times n 和 v+k×nv + k \times n （0≤k≤K0 \le k \le K）之间建立长度为 ww 的边；相邻层的点 u+k×nu + k \times n 和 v+(k+1)×nv + (k + 1) \times n，建立长度为 w2\frac{w}{2} 的边，表示这条边上使用一次符卡。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef pair<int, int> pii;
const int N = 3010, M = 1e6 + 10, inf = 0x3f3f3f3f;

int h[N], e[M], ne[M], w[M], idx; // 链式前向星
void add(int a, int b, int c){
    e[ ++ idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}

int n, m, K, dist[N];
bool st[N]; 

// 堆优化 dijkstra
void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(make_pair(dist[1], 1));

    while(q.size()){
        auto [d, u] = q.top();
        q.pop();

        if(st[u]) continue;
        st[u] = true;

        for(int i = h[u]; i; i = ne[i]){
            int v = e[i], c = w[i];
            if(dist[v] > d + c){ // 当前不使用符卡
                dist[v] = d + c;
                q.push(make_pair(dist[v], v));
            }
        }
    }
}

int main(){
    ios;

    cin >> n >> m >> K;
    while(m -- ){
        int u, v, c; cin >> u >> v >> c;  // 构建分层图
        for(int k = 0; k <= K; k ++ ) 
            add(u + k * n, v + k * n, c), add(v + k * n, u + k * n, c);
        for(int k = 0; k < K; k ++ ) 
            add(u + k * n, v + (k + 1) * n, c / 2), add(v + k * n, u + (k + 1) * n, c / 2);
    }

    dijkstra();

    int res = inf;
    for(int k = 0; k <= K; k ++ ) res = min(res, dist[n + k * n]);
    cout << res << '\n';

    return 0;
}

F. 卫星露天咖啡座

题目描述

共 QQ 次操作，每次操作包含一个日期 aa、一个奶牛编号 bb，以及一个产奶变化量 cc。需要维护所有奶牛中最大产奶量奶牛的编号（奶牛的数量未知）。求出所有操作结束后一共修改最大产奶量奶牛的编号的次数。「YAC Round 1」卫星露天咖啡座

解题思路 （线段树）

我们可以用 线段树 来维护所有奶牛的最大值以及最大值对应的编号。

由于操作的日期是乱序的，故我们需要先根据操作的日期对操作进行排序。但是，奶牛的数量是未知的，而且题中说明一定存在若干奶牛产奶量保持在 GG，所以，我们需要增加一个虚拟的操作 {0,0,0}\{0, 0, 0\}，预先加入一个产奶量不变的 00 号奶牛。

奶牛编号范围为 [1,109][1, 10^9]，但是操作数量为 [1,106][1, 10^6]，为了维护奶牛区间，需要对奶牛编号进行离散化。

对于维护最大产奶量奶牛的编号，我们不仅需要用线段树维护区间最值和对应编号，还需要维护最大产奶量奶牛的数量，因为题中表明，当有若干头奶牛的产奶量最高，需要展示 所有 的最高产奶量奶牛的编号。

也就是说，修改奶牛编号操作涉及两种情况：

  • 最大值对应的奶牛编号变化（有可能是有其他奶牛产奶量增加超过了当前奶牛，也有可能是当前奶牛产奶量减少被其他奶牛超越）

  • 最大值对应的奶牛数量增加（有其他奶牛产奶量增加，然后和当前最大产奶量并列）

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ls (u << 1)
#define rs (u << 1 | 1)
const int N =  1e6 + 10;

struct qu{int t, id, d;};
vector<qu> ques;   // 操作
int n, g; // g 为奶牛初始产奶量 

vector<int> v;
int find(int x){return lower_bound(v.begin(), v.end(), x) - v.begin();}

int mx[N << 2], cnt[N << 2], id[N << 2]; // 线段树

void pushup(int u, int l, int r){
    if(mx[ls] > mx[rs]){  // 左边的最值比右边的大
        mx[u] = mx[ls];
        cnt[u] = cnt[ls];
        id[u] = id[ls];
    }else if(mx[ls] < mx[rs]){  // 右边的最值比左边的大
        mx[u] = mx[rs];
        cnt[u] = cnt[rs];
        id[u] = id[rs];      
    }else{ // 两边最值一样大
        mx[u] = mx[ls];
        cnt[u] = cnt[ls] + cnt[rs];
        id[u] = id[ls];     
    }
}

void build(int u, int l, int r){
    mx[u] = g;
    if(l == r){cnt[u] = 1, id[u] = l; return;}
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u, l, r);
}

// 单点修改
void update(int u, int l, int r, int k, int d){
    if(l == r){mx[u] += d; return;}
    int mid = l + r >> 1;
    if(k <= mid) update(ls, l, mid, k, d);
    else update(rs, mid + 1, r, k, d);
    pushup(u, l, r);
}

int main(){
    ios;

    cin >> n >> g;
    for(int i = 1, t, id, d; i <= n; i ++ ){
        string s; cin >> t >> id >> s;
        d = (s[0] == '+' ? stoi(s.substr(1)) : stoi(s)); // stoi可以识别负数
        ques.push_back(qu{t, id, d});
        v.push_back(id);
    }
    ques.push_back(qu{0, 0, 0}); // 虚拟操作
    v.push_back(0);   // 产奶量不变的奶牛

    sort(ques.begin(), ques.end(), [](qu &a, qu &b){
        return a.t < b.t;  // 按照日期排序
    });

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end()); // 排序 去重 离散化

    int m = (int)v.size();
    build(1, 1, m);   // 构建区间 [1, m] 的线段树

    int pre_id, pre_cnt, res = 0;
    for(auto &p : ques){
        pre_id = id[1], pre_cnt = cnt[1];  // 当前的最大值编号以及最大值数量

        update(1, 1, m, find(p.id), p.d); // 更新产奶量变化

        int now_id = id[1], now_cnt = cnt[1];  // 更新后的最大值编号和最大值数量
        res += (now_id != pre_id || now_cnt != pre_cnt); // 两种情况 需要修改
    }

    cout << res << '\n';

    return 0;
}
咏唱光芒 > YAC 扬州大学算法练习赛
#C++ #算法 #算法竞赛 #Luogu #YAC
2024 YAC Round 1 题解
https://marisamagic.github.io/2024/12/14/YAC_Round_1/
作者
MarisaMagic
发布于
2024年12月14日
许可协议