AtCoder Beginner Contest 447

A

1
#include<bits/stdc++.h>
2
#include<concepts>
3
using namespace std;
4
typedef long long ll;
5
typedef unsigned long long ull;
6
typedef pair<int, int> PII;
7
#define MP make_pair
8
#define fi first
9
#define se second
10
#define pb push_back
11
#define eb emplace_back
12
#define SET(a, b) memset(a, b, sizeof(a))
13
#define CPY(a, b) memcpy(a, b, sizeof(b))
14
#define rep(i, j, k) for(int i = (j); i <= (k); ++i)
15
#define per(i, j, k) for(int i = (j); i >= (k); --i)
16
struct FastIO {
17
    static const int MAXSIZE = 1 << 20;
18
    char buf[MAXSIZE], *p1, *p2;
19
    char pbuf[MAXSIZE], *pp;
20

21
    FastIO() : p1(buf), p2(buf), pp(pbuf) {}
22
    ~FastIO() { flush(); }
23

24
    void flush() {
25
        if (pp > pbuf) {
26
            fwrite(pbuf, 1, pp - pbuf, stdout);
27
            pp = pbuf;
28
        }
29
    }
30

31
    char gc() {
32
        if (p1 == p2) {
33
            p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
34
            if (p1 == p2) return EOF;
35
        }
36
        return *p1++;
37
    }
38

39
    void pc(char c) {
40
        if (pp - pbuf == MAXSIZE) flush();
41
        *pp++ = c;
42
    }
43
    template <typename T>
44
    void read(T &x) {
45
        x = 0; bool neg = false; char ch = gc();
46
        while (!isdigit(ch) && ch != EOF) { if (ch == '-') neg = true; ch = gc(); }
47
        if (ch == EOF) return;
48
        while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = gc(); }
49
        if (neg) x = -x;
50
    }
51

52
    template <typename T>
53
    void write(T x) {
54
        if (x < 0) { pc('-'); x = -x; }
55
        static int sta[45];
56
        int top = 0;
57
        do { sta[top++] = x % 10; x /= 10; } while (x);
58
        while (top) pc(sta[--top] + '0');
59
    }
60

61
    template <typename T>
62
    void write(T x, char lastChar) {
63
        write(x);
64
        pc(lastChar);
65
    }
66
} io;
67
signed main() {
68
    // ios::sync_with_stdio(false);
69
    // cin.tie(nullptr);
70
    int n = 0, m = 0;
71
    io.read(n);
72
    io.read(m);
73
    if(n >= (m * 2 - 1)) puts("Yes");
74
    else puts("No");
75
    return 0;
76
}

B

1
#include<bits/stdc++.h>
2
#include<concepts>
3
using namespace std;
4
typedef long long ll;
5
typedef unsigned long long ull;
6
typedef pair<int, int> PII;
7
#define MP make_pair
8
#define fi first
9
#define se second
10
#define pb push_back
11
#define eb emplace_back
12
#define SET(a, b) memset(a, b, sizeof(a))
13
#define CPY(a, b) memcpy(a, b, sizeof(b))
14
#define rep(i, j, k) for(int i = (j); i <= (k); ++i)
15
#define per(i, j, k) for(int i = (j); i >= (k); --i)
16
struct FastIO {
17
    static const int MAXSIZE = 1 << 20;
18
    char buf[MAXSIZE], *p1, *p2;
19
    char pbuf[MAXSIZE], *pp;
20

21
    FastIO() : p1(buf), p2(buf), pp(pbuf) {}
22
    ~FastIO() { flush(); }
23

24
    void flush() {
25
        if (pp > pbuf) {
26
            fwrite(pbuf, 1, pp - pbuf, stdout);
27
            pp = pbuf;
28
        }
29
    }
30

31
    char gc() {
32
        if (p1 == p2) {
33
            p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
34
            if (p1 == p2) return EOF;
35
        }
36
        return *p1++;
37
    }
38

39
    void pc(char c) {
40
        if (pp - pbuf == MAXSIZE) flush();
41
        *pp++ = c;
42
    }
43
    template <typename T>
44
    void read(T &x) {
45
        x = 0; bool neg = false; char ch = gc();
46
        while (!isdigit(ch) && ch != EOF) { if (ch == '-') neg = true; ch = gc(); }
47
        if (ch == EOF) return;
48
        while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = gc(); }
49
        if (neg) x = -x;
50
    }
51

52
    template <typename T>
53
    void write(T x) {
54
        if (x < 0) { pc('-'); x = -x; }
55
        static int sta[45];
56
        int top = 0;
57
        do { sta[top++] = x % 10; x /= 10; } while (x);
58
        while (top) pc(sta[--top] + '0');
59
    }
60

61
    template <typename T>
62
    void write(T x, char lastChar) {
63
        write(x);
64
        pc(lastChar);
65
    }
66
} io;
67
string s;
68
int c[100];
69
signed main() {
70
    // ios::sync_with_stdio(false);
71
    // cin.tie(nullptr);
72
    cin >> s;
73
    int mx = 0;
74
    for(auto x : s) {
75
        c[x - 'a']++;
76
        mx = max(mx, c[x - 'a']);
77
    }
78
    for(auto x : s) if(c[x - 'a'] < mx) {
79
        cout << x;
80
    }
81
    cout << endl;
82
    return 0;
83
}

C

显然我们把两个串里所有的A去掉，然后如果此时不相同直接无解了。

然后我们分别把两个串里所有的A连续段（包括长度为 0）的都提取出来，对齐一下下标，并求出 $cs, ct$ 为两个串各自A的数量。设 $R(i, 0/1)$ 为两个串第 $i$ 段A的数量，显然只能保留 $2\min\big(R(i,0), R(i, 1) \big)$ 个，最后注意一下结尾的A连续段即可。

1
#include<bits/stdc++.h>
2
#include<concepts>
3
using namespace std;
4
typedef long long ll;
5
typedef unsigned long long ull;
6
typedef pair<int, int> PII;
7
#define MP make_pair
8
#define fi first
9
#define se second
10
#define pb push_back
11
#define eb emplace_back
12
#define SET(a, b) memset(a, b, sizeof(a))
13
#define CPY(a, b) memcpy(a, b, sizeof(b))
14
#define rep(i, j, k) for(int i = (j); i <= (k); ++i)
15
#define per(i, j, k) for(int i = (j); i >= (k); --i)
16
struct FastIO {
17
    static const int MAXSIZE = 1 << 20;
18
    char buf[MAXSIZE], *p1, *p2;
19
    char pbuf[MAXSIZE], *pp;
20

21
    FastIO() : p1(buf), p2(buf), pp(pbuf) {}
22
    ~FastIO() { flush(); }
23

24
    void flush() {
25
        if (pp > pbuf) {
26
            fwrite(pbuf, 1, pp - pbuf, stdout);
27
            pp = pbuf;
28
        }
29
    }
30

31
    char gc() {
32
        if (p1 == p2) {
33
            p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
34
            if (p1 == p2) return EOF;
35
        }
36
        return *p1++;
37
    }
38

39
    void pc(char c) {
40
        if (pp - pbuf == MAXSIZE) flush();
41
        *pp++ = c;
42
    }
43
    template <typename T>
44
    void read(T &x) {
45
        x = 0; bool neg = false; char ch = gc();
46
        while (!isdigit(ch) && ch != EOF) { if (ch == '-') neg = true; ch = gc(); }
47
        if (ch == EOF) return;
48
        while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = gc(); }
49
        if (neg) x = -x;
50
    }
51

52
    template <typename T>
53
    void write(T x) {
54
        if (x < 0) { pc('-'); x = -x; }
55
        static int sta[45];
56
        int top = 0;
57
        do { sta[top++] = x % 10; x /= 10; } while (x);
58
        while (top) pc(sta[--top] + '0');
59
    }
60

61
    template <typename T>
62
    void write(T x, char lastChar) {
63
        write(x);
64
        pc(lastChar);
65
    }
66
} io;
67
const int N = 3e5 + 5;
68
string s, t;
69
string s0, t0;
70
int R[N][2];
71
signed main() {
72
    ios::sync_with_stdio(false);
73
    cin.tie(nullptr);
74
    cin >> s >> t;
75
    int cs = 0, ct = 0;
76
    for(auto x : s) {
77
        if(x != 'A') {
78
            s0 += x;
79
        } else cs++;
80
    }
81
    for(auto x : t) {
82
        if(x != 'A') {
83
            t0 += x;
84
        } else ct++;
85
    }
86
    if(s == t) {
87
        cout << 0 << endl;
88
        return 0;
89
    }
90
    // cout << s0 << endl;
91
    // cout << t0 << endl;
92
    if(s0 != t0) {
93
        cout << -1 << endl;
94
        return 0;
95
    }
96

97
    int m = s0.size(), lst = 0, p = 0;
98
    for(int i = 0; i < s.size(); i++) {
99
        if(s[i] == 'A' && i != 0 && s[i - 1] != 'A') lst = i;
100
        else if(s[i] != 'A') R[++p][0] = i - lst, lst = i + 1;
101
    }
102
    lst = 0;
103
    p = 0;
104
    for(int i = 0; i < t.size(); i++) {
105
        if(t[i] == 'A' && i != 0 && t[i - 1] != 'A') lst = i;
106
        else if(t[i] != 'A') R[++p][1] = i - lst, lst = i + 1;
107
    }
108
    int res = 0;
109
    int c1 = 0, c2 = 0;
110
    for(int i = s.size() - 1; ~i; i--) {
111
        if(s[i] == 'A') c1++;
112
        else break;
113
    }
114
    for(int i = t.size() - 1; ~i; i--) {
115
        if(t[i] == 'A') c2++;
116
        else break;
117
    }
118
    for(int i = 1; i <= m; i++) {
119
        res += 2 * min(R[i][0], R[i][1]);
120
        // cout << R[i][0] << " " << R[i][1] << endl;
121
    }
122
    cout << cs + ct - res - 2 * min(c1, c2) << endl;
123
    return 0;
124
}

D

考虑一个策略：我们从左往右扫到第一个A，再往右找到第一个B，再找到第一个C，然后匹配之。

这样一定是最优秀的，因为每个C匹配尽可能靠前的AB最优，每个B匹配最靠前的A最优。

不过这样不是很好写，需要处理挺多细节。

考虑一个经典 Trick，我们直接维护当前位置A的数量 $ca$ ，AB的数量 $cab$ ，遇到一个A时增加 $ca$ ，遇到B时，如果 $ca > 0$ ，就增加 $cab$ ， $ca$ 减少 $1$ 。遇到C时匹配掉一个AB即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int, int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a, b) memset(a, b, sizeof(a))
12
#define CPY(a, b) memcpy(a, b, sizeof(b))
13
#define rep(i, j, k) for(int i = (j); i <= (k); ++i)
14
#define per(i, j, k) for(int i = (j); i >= (k); --i)
15
struct FastIO {
16
    static const int MAXSIZE = 1 << 20;
17
    char buf[MAXSIZE], *p1, *p2;
18
    char pbuf[MAXSIZE], *pp;
19

20
    FastIO() : p1(buf), p2(buf), pp(pbuf) {}
21
    ~FastIO() { flush(); }
22

23
    void flush() {
24
        if (pp > pbuf) {
25
            fwrite(pbuf, 1, pp - pbuf, stdout);
26
            pp = pbuf;
27
        }
28
    }
29

30
    char gc() {
31
        if (p1 == p2) {
32
            p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
33
            if (p1 == p2) return EOF;
34
        }
35
        return *p1++;
36
    }
37

38
    void pc(char c) {
39
        if (pp - pbuf == MAXSIZE) flush();
40
        *pp++ = c;
41
    }
42
    template <typename T>
43
    void read(T &x) {
44
        x = 0; bool neg = false; char ch = gc();
45
        while (!isdigit(ch) && ch != EOF) { if (ch == '-') neg = true; ch = gc(); }
46
        if (ch == EOF) return;
47
        while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = gc(); }
48
        if (neg) x = -x;
49
    }
50

51
    template <typename T>
52
    void write(T x) {
53
        if (x < 0) { pc('-'); x = -x; }
54
        static int sta[45];
55
        int top = 0;
56
        do { sta[top++] = x % 10; x /= 10; } while (x);
57
        while (top) pc(sta[--top] + '0');
58
    }
59

60
    template <typename T>
61
    void write(T x, char lastChar) {
62
        write(x);
63
        pc(lastChar);
64
    }
65
} io;
66
const int N = 1e6 + 5;
67
int n, a[N][3];
68
string s;
69
signed main() {
70
    ios::sync_with_stdio(false);
71
    cin.tie(nullptr);
72
    cin >> s;
73
    int ca = 0, cab = 0, ans = 0;
74

75
    for(auto x : s) {
76
        if(x == 'A') {
77
            ca++;
78
        } else if(x == 'B') {
79
            if(ca > 0) {
80
                ca--;
81
                cab++;
82
            }
83
        } else if (x == 'C') {
84
            if (cab > 0) {
85
                cab--;
86
                ans++;
87
            }
88
        }
89
    }
90
    cout << ans << endl;
91
    return 0;
92
}

E

考虑二进制的性质，我们知道如果你删掉了边 $i$ ，那么代价大于删掉 $[1, i)$ 中的所有边，所以应该能删则删。

保留恰好两个连通块，贪心选边，联想到 Kruskal 算法的过程。因为要保证连通块恰好为 $2$ ，所以还要有一个减少连通块的过程，也就是一些权值很小的边是必须保留的，这与我们上述的策略产生了冲突。

如何解决？转化一下就是我们尽可能不要保留编号大的边，于是我们按照边权（编号）递减排序，贪心用权值大的边减少连通块即可。

如果当前连通块数量大于 $2$ ，那么我们贪心保留边并合并，否则删掉这条边

F

赛时没有做出来。

Nanami^2

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区