Codeforces Round 1003 (Div. 4)题解#

A#

字符串水题

Code#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
inline void Solve()
15
{
16
  string s;
17
    cin>>s;
18
    s.erase(s.size()-2,2);
19
    cout<<s<<"i"<<endl;
20
}
21
signed main()
22
{
23
#ifndef ONLINE_JUDGE
24
    freopen(".in", "r", stdin);
25
    freopen(".out", "w", stdout);
26
#endif
27
    ios::sync_with_stdio(0);
28
    cin.tie(0),cout.tie(0);
29

30
#ifdef MULTI_CASES
31
    cin >> T;
32
    while (T--)
33
#endif
34
       Solve();
35
    //fclose(stdin);
36
    //fclose(stdout);
37
    return 0;
38
}

B#

题意简述#

给定一个字符串 $s$ ，每次操作，可以选择一个索引 $i（1\le i\le \lvert s \rvert-1）$ ，且 $s_i=s_{i+1}$ ，然后将这两个字符更改为任意一个字母。求多次操作后可以达到的最小长度。

题目分析#

不难发现，只要字符串中存在 $s_i=s_{i+1}$ ，就可以重复删除字符并更改为相邻字符。最后的长度一定为 $1$ 。

Code#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
inline void Solve()
15
{
16
  string s;
17
    cin>>s;
18
    for(int i=0;i<s.size()-1;i++){
19
        if(s[i]==s[i+1]){
20
            cout<<1<<endl;
21
            return;
22
        }
23
    }
24
    cout<<s.size()<<endl;
25
}
26
signed main()
27
{
28
#ifndef ONLINE_JUDGE
29
    freopen(".in", "r", stdin);
30
    freopen(".out", "w", stdout);
31
#endif
32
    ios::sync_with_stdio(0);
33
    cin.tie(0),cout.tie(0);
34

35
#ifdef MULTI_CASES
36
    cin >> T;
37
    while (T--)
38
#endif
39
       Solve();
40
    //fclose(stdin);
41
    //fclose(stdout);
42
    return 0;
43
}

C1/C2#

题意简述#

给定长度分别为 $n,m$ 的数组 $a,b$ ，对于 $a$ 中的每个元素，最多可以执行一次操作。

选择一个整数 $j（1\le j\le m）$ ，使得 $a_i:=b_j-a_i$ 。

求是否在若干次操作后，数组 $a$ 可以按非递减顺序排序。

C1要求 $m=1$ ，C2要求 $1\le m \le 2\times 10^5$ 。

题目分析#

C1#

考虑贪心，对于每一位数字，要尽可能保证前一个数小于等于后一个数，那么对于每一个数都要在符合条件的情况下尽可能小，而因为 $m=1$ ，所以对于每一位数 $a_i$ 将其与 $b_0-a_i$ 比大小，在保证比上一个数大的条件下，选择更小的那个即可。如果当前数无论如何操作都无法满足，则说明不可以实现。

C2#

在C1的基础上，依然考虑贪心，对于每一位数字，仍然可以遍历数组 $b$ ，使其在符合条件的情况下最小。复杂度 $O(N^2)$ 。

考虑优化，题目要求 $a_{i-1}\le \min(a_i,b_j-a_i),(1\le j\le m)$ ，复杂度瓶颈在遍历 $b$ 数组上，所以我们可以使用二分查找，找到 $b$ 数组中第一个大于等于 $a_{i-1}+a_i$ 的值并将其替换 $a_i$ ，如果这个值比数组中的所有值都大，那么则无法实现。

Code#

C1#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5+100;
10
const int INF = 1e9;
11
const int mod=212370440130137957ll;
12
int T=1, N, M;
13
int a[MaxN];
14
inline void Solve()
15
{
16
  cin>>N>>M;
17
    for(int i=1;i<=N;i++){
18
        cin>>a[i];
19
    }
20
    int cnt;
21
    cin>>cnt;
22
    int las=-INF;
23
    for(int i=1;i<=N;i++){
24
        int x=cnt-a[i];
25
        if(x<=a[i]){
26
            if(x>=las){
27
                las=x;
28
            }
29
            else{
30
                if(a[i]>=las){
31
                    las=a[i];
32
                }
33
                else{
34
                    puts("NO");
35
                    return ;
36
                }
37
            }
38
        }
39
        else{
40
            if(a[i]>=las){
41
                las=a[i];
42
            }
43
            else{
44
                if(x>=las){
45
                    las=x;
46
                }
47
                else{
48
                    puts("NO");
49
                    return ;
50
                }
51
            }
52
        }
53
    }
54
    puts("YES");
55
}
56
signed main()
57
{
58
#ifndef ONLINE_JUDGE
59
    freopen(".in", "r", stdin);
60
    freopen(".out", "w", stdout);
61
#endif
62
    ios::sync_with_stdio(0);
63
    cin.tie(0),cout.tie(0);
64

65
#ifdef MULTI_CASES
66
    cin >> T;
67
    while (T--)
68
#endif
69
       Solve();
70
    //fclose(stdin);
71
    //fclose(stdout);
72
    return 0;
73
}

C2#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5 + 100;
10
const int INF = 1e9;
11
const int mod = 212370440130137957ll;
12
int T = 1, N, M;
13
int a[MaxN];
14
inline void Solve()
15
{
16
    cin >> N >> M;
17
    for (int i = 1; i <= N; i++)
18
    {
19
        cin >> a[i];
20
    }
21
    vector<int> b;
22
    for (int i = 1; i <= M; i++)
23
    {
24
        int x;
25
        cin >> x;
26
        b.push_back(x);
27
    }
28
    sort(b.begin(), b.end());
29
    int las = a[1];
30
    for (int i = 0; i < M; i++)
31
    {
32
        las = min(las, b[i] - a[1]);
33
    }
34
    // cerr<<las<<endl;
35
    for (int i = 2; i <= N; i++)
36
    {
37
        int minn = INF;
38
        if (a[i] >= las)
39
        {
40
            minn = a[i];
41
        }
42
        auto x = lower_bound(b.begin(), b.end(), a[i] + las);
43
        if (x == b.end())
44
        {
45
            if (minn == INF)
46
            {
47
                puts("NO");
48
                return;
49
            }
50
            else
51
            {
52
                las = minn;
53
            }
54
        }
55
        else
56
        {
57
            int cnt = x - b.begin();
58
            las = min(minn, b[cnt] - a[i]);
59
        }
60
        // cerr<<las<<" ";
61
    }
62
    puts("YES");
63
}
64
signed main()
65
{
66
#ifndef ONLINE_JUDGE
67
    freopen(".in", "r", stdin);
68
    freopen(".out", "w", stdout);
69
#endif
70
    ios::sync_with_stdio(0);
71
    cin.tie(0), cout.tie(0);
72

73
#ifdef MULTI_CASES
74
    cin >> T;
75
    while (T--)
76
#endif
77
        Solve();
78
    // fclose(stdin);
79
    // fclose(stdout);
80
    return 0;
81
}

Codeforces Round 1003 (Div. 4)题解#

A#

Code#

B#

题意简述#

题目分析#

Code#

C1/C2#

题意简述#

题目分析#

C1#

C2#

Code#

C1#

C2#

D#