Codeforces Round #700 (Div. 2) A~D题解

作者：菜鸟追梦旅行 | 2024-02-09 10:28:34

踩

A. Yet Another String Game

解题思路
贪心题，Alice和Bob为了处理字典序，必定是从开头遍历字符串的。作为Alice想要最小，那么就将当前所处理的字符变为’a’，要注意，如果当前处理字符串就为’a’，那么Alice需要将其变为’b’。同理Bob想要最大，那么就就将所处理的字符变为’z’，要注意，如果当前处理字符串就为’z’，那么Bob需要将其变为’y’。
AC代码

/**
  *@filename:A_Yet_Another_String_Game
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-01 16:40
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int t;
string s;
void solve(){
    //Alice want to be min,Bob want to be max, Alice first;
    bool flag = true;
    for(auto &x : s){
        if(flag){
            //让其最小。
            if(x == 'a'){
                x = 'b';
            }
            else{
                x = 'a';
            }
        }
        else{
            //让其最大。
            if(x == 'z'){
                x = 'y';
            }
            else{
                x = 'z';
            }
        }
        flag = !flag;
    }
    cout << s << endl;
}
int main(){
    cin >> t;
    while(t -- ){
        cin >> s;
        solve();
    }
    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

B. The Great Hero

解题思路
这道题我们需要知道贪心只有一步，就是最后处理最大伤害的那个怪兽的最后一战。这里解释一下，不管如何，倘若要消灭掉所有的怪兽，所付出的代价都是一样的。而题目中允许当消灭掉所有怪兽的时候英雄死亡，所以我们实际上就可以判断在最后一战前，英雄是否存活，即加上最后一战的最大伤害值即可。故题可解。
AC代码

/**
  *@filename:B_The_Great_Hero
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-01 16:46
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int t,n;
ll A,B,a[N],b[N];
ll maxx;
void solve(){
    bool flag = false;
    for(int i = 1; i <= n; ++ i){
        int temp = b[i] / A + (b[i] % A != 0);
        B -= a[i] * temp;
    }
    B += maxx;
    if(B <= 0)flag = true;
    printf("%s\n",flag ? "NO" : "YES");
}
int main(){
    scanf("%d", &t);
    while(t -- ){
        maxx = 0;
        scanf("%lld%lld%d", &A, &B, &n);
        for(int i = 1; i <= n; ++ i){
            scanf("%lld", &a[i]);
            maxx = max(a[i],maxx);//存储其中的最大伤害。
        }
        for(int i = 1; i <= n; ++ i){
            scanf("%lld", &b[i]);
        }
        solve();
    }
    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

C. Searching Local Minimum

解题思路
我们需要找到一个局部最小值下标 $i$ ，即 $a_{i-1}>a_i<a_{i + 1}$ 。数据范围为 $10^5$ ，查询次数不能超过 $100$ 次。所以我们应该能想到二分。怎么二分呢？数组不是无序的嘛？数组虽然是无序的，可是我们可以维护一个区间 $[l, r]$ ，使得其中存在局部最小值，同时我们保证 $a_{l-1}>a_l,a_r<a_{r+1}$ 。那么我们每次二分取中点 $m$ ，然后查询 $a_m,a_{m+1}$ ，如果 $a_m<a_{m+1}$ ，为了维护这个区间，即区间变成 $[l, m]$ ；同理，如果 $a_m>a_{m + 1}$ ，为了维护这个区间，即区间变成 $[m + 1, r]$ 。我们这样维护下去，最后当区间长度为 $1$ 的时候必定是局部最小值。
AC代码

/**
  *@filename:C_Searching_Local_Minimum
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-02 08:36
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int n,l,r;
int get(int idx){
    cout << "? " << idx << endl;
    fflush(stdout);
    int res;
    cin >> res;
    return res;
}
void solve(){
    l = 1,r = n;
    while(l < r){
        int mid = l + r >> 1;
        int temp1 = get(mid + 1),temp2 = get(mid);
        if(temp2 < temp1){
            //说明左边小于右边。那么答案就在左边。
            r = mid;
        } 
        else{
            l = mid + 1;
        }
    }
    cout << "! " << l << endl;
    fflush(stdout);
}
int main(){
    cin >> n;
    solve();
    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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

D1. Painting the Array I

题意

给你一个序列 a，请你将这个序列撕开分成两个序列 $a^{(0)}$ 和 $a^{(1)}$ ，使得将 $a^{(0)}$ 和 $a^{(1)}$ 合并所有相邻且相同的元素之后，两个序列剩余的元素个数和最大。

解题思路
此题我们可以贪心实现。我们来分析一下，对于这两个序列，影响放置的决定因素就是当前序列中的最后一个元素，我们设 $a^{(0)}$ 的最后一个元素为 $x$ ， $a^{(1)}$ 的最后一个元素为 $y$ 。那么对于当前要放置的元素 $z_1$ 来看，我们分类讨论：
1. 如果 $z_1=x,z1 =y$ ，这种情况我们放哪个序列都要被合并；
2. 如果 $z_1=x,z1!=y$ ，那么此时我们放 $a^{(1)}$ 更优；
3. 如果 $z_1=y,z1!=x$ ，那么此时我们放 $a^{(0)}$ 更优。
4. 如果 $z_1 !=x,z_1!=y$ ，这种情况我们可以都放，但是为了考虑最优情况，我们还需要作出判断，即会不会影响下一个要放置的元素 $z_2$ ，如果 $z_2=x$ ，我们就可以放置 $a^{(0)}$ 更改 $x$ ，使其更优，同理如果 $z_2=y$ ，我们就可以放置 $a^{(1)}$ 更改 $y$ ，使其更优，否则就随便放置。
经过以上分析，此题也就迎刃而解了，我们遍历处理即可。
AC代码

/**
  *@filename:D1_Painting_the_Array_I
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-02 09:00
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int n,a[N]; 
void solve(){
    int ans = 0;
    int x = -1,y = -1;//x代表a0中的最后一个元素，y代表a1中的最后一个元素，初始化为-1.
    for(int i = 1; i <= n; ++ i){
        int z1 = a[i],z2 = a[i + 1];//z1表示当前要处理的元素，z2表示下一个要处理的元素。
        if(z1 == x && z1 == y)continue;//因为放哪都没有贡献。
        if(z1 == x){
            //此时放a1更优。
            ans ++;
            y = z1;
        }
        else if(z1 == y){
            //此时放a0更优。
            ans ++;
            x = z1;
        }
        else{
            //如果两个都可以放，我们需要考虑贡献，即下一个元素是否会影响。
            ans ++;
            if(z2 == x){
                //那我们放x就可能抵消这种冲突。
                x = z1;
            }
            else{
                y = z1;
            }
        }
    }
    cout << ans << endl;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
    }
    solve();
    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
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

D2. Painting the Array II

题意

给你一个序列 a，请你将这个序列撕开分成两个序列 $a^{(0)}$ 和 $a^{(1)}$ ，使得将 $a^{(0)}$ 和 $a^{(1)}$ 合并所有相邻且相同的元素之后，两个序列剩余的元素个数和最小。**

解题思路
同 $D 1$ 思考方式相同，但是这里需要注意在 $x!=z_2,y!=z2$ 的情况下，我们还需要考虑整体，我们为了让元素尽可能合并，所以我们需要判断哪个相同的元素最先到达，如果下一个相等的 $x$ 比 $y$ 先到，就更新 $y$ ，否则更新 $x$ 。所以我们需要存储每个元素的下一个相等位置。即可以先用邻接表存储每个元素的位置。最后用nex数组存储相等元素的下一个位置即可。具体看AC代码。
AC代码

/**
  *@filename:D1_Painting_the_Array_I
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-02 09:00
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int n,a[N]; 
vector<int> v[N];
int nex[N];
void solve(){
    for(int i = 1; i <= n; ++ i){
        for(int j = 0 ; j < (int)v[i].size() - 1; ++ j){
            nex[v[i][j]] = v[i][j + 1];//保存下一个与其值相等的情况。
        }
    }
    int ans = 0;
    int x = -1,y = -1;//x代表a0中的最后一个元素，y代表a1中的最后一个元素，初始化为-1.
    int next_x = n + 1,next_y = n + 1;//初始化。
    for(int i = 1; i <= n; ++ i){
        int z1 = a[i],z2 = a[i + 1];//z1表示当前要处理的元素，z2表示下一个要处理的元素。
        if(z1 == x){
            //放x更优。
            next_x = nex[i];
        }
        else if(z1 == y){
            next_y = nex[i];
        }
        else{
            //说明都不相等，我们需要考虑放哪个更优。
            ans ++;
            if(z2 == x && z2 != y){
                y = z1;
                next_y = nex[i];
            }
            else if(z2 == y && z2 != x){
                x = z1;
                next_x = nex[i];
            }
            else{
                if(next_x < next_y){
                    //说明下个相等的x比y先到。
                    y = z1;
                    next_y = nex[i];
                }
                else{
                    x = z1;
                    next_x = nex[i];
                }
            }
        }
    }
    cout << ans << endl;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        v[a[i]].push_back(i);
        nex[i] = n + 1;
    }
    solve();
    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
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/71355