题目链接：https://atcoder.jp/contests/abc464/tasks

A - Decisive Battle#

遍历字符串然后计数字符 $'E'$ 和 $'W'$ ，比较并输出最大的字符即可。

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

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

11
void solved() {
12
    int cntE, cntW = 0;
13
    string s;
14
    cin >> s;
15
    for(auto it : s){
16
        if(it == 'E') cntE++;
17
        else cntW++;
18
    }
19
    cout << ((cntE > cntW) ? "East" : "West") << endl;
20
}
21

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

B - Crop#

因为边界的 $'.'$ 都会被去除，题意可以转化为找到最大的含有 $'\#'$ 字符的矩阵。我们找到这个矩阵边界四个端点，然后遍历输出这个矩阵即可。

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

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

11
char grid[60][60];
12

13
void solved() {
14
    int H, W;
15
    cin >> H >> W;
16
    int WideMax = 0, LenMax = 0;
17
    int WideMin = 51, LenMin = 51;
18
    for(int i = 1; i <= H;i++){
19
        for(int j = 1; j <= W;j++){
20
            cin >> grid[i][j];
21
            if(grid[i][j] == '#'){
22
                WideMax = max(WideMax, j);
23
                LenMax = max(LenMax, i);
24
                WideMin = min(WideMin, j);
25
                LenMin = min(LenMin, i);
26
            }
27
        }
28
    }
29
    for(int i = LenMin; i <= LenMax;i++){
30
        for (int j = WideMin; j <= WideMax;j++){
31
            cout << grid[i][j];
32
        }
33
        cout << endl;
34
    }
35
}
36

37
int main() {
38
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
39
    int _ = 1;
40
    //cin >> _;
41
    while (_--) {
42
        solved();
43
    }
44
    return 0;
45
}

C - Plumage Palette#

这题我们不需要每次都计算当天对应的颜色总数，我们只需要在遍历到天数时更新这个总数，然后输出即可。
我们用一个二维数组 $event$ 记录每天会发生变化的颜色( $A$ 变成 $B$ )，用 $cnt$ 记录该颜色的总数，然后在遍历天数的时候根据 $cnt_A$ 和 $cnt_B$ 的数量来更新颜色总数。当进行颜色变换后如果 $cnt_A$ 为 $0$ ，那么总数 $kind$ 就减一，如果 $cnt_B$ 原来为 $0$ ，那么 $kind$ 就加一。
$tips：$ 这里的遍历记录当天颜色变化的 $event$ 实际上只增加了常数( $N$ )级的复杂度。这是因为 $event$ 的总数虽然为 $N$ ，但是每次循环时并不会取满这 $N$ 次，只有当完全遍历完天数时才会循环满这 $N$ 次。所以这里的时间复杂度为 $O(N + M)$ ，完全可以通过本题。

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

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

11
void solved() {
12
    int N, M; cin >> N >> M;
13
    vector<vector<pii>> event(M + 1);
14
    vector<int> cnt(N + 1, 0);
15
    for(int i = 1; i <= N; i++){
16
        int A, D, B; cin >> A >> D >> B;
17
        cnt[A]++;
18
        event[D].push_back({A, B});
19
    }
20
    int kind = 0;
21
    for(int c = 1; c <= N; c++){
22
        if(cnt[c] > 0) kind++;
23
    }
24
    for(int i = 1; i <= M; i++){
25
        for(auto [A, B] : event[i]){
26
            cnt[A]--;
27
            if(cnt[A] == 0) kind--;
28
            if(cnt[B] == 0) kind++;
29
            cnt[B]++;
30
        }
31
        cout << kind << endl;
32
    }
33
}
34

35
int main() {
36
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
37
    solved();
38
    return 0;
39
}

D - Celester#

这题是典型的线性 $dp$ ，后面的操作不影响前面的结果。
我们可以定义 $dpS[i]$ 和 $dpR[i]$ 分别为前 $i$ 天的最优幸福值。那么当前的最优幸福值就可以由前面的继承或者修改得到。我这里定义 $cost(i, 'char')$ 为第 $i$ 天是该字符的代价（不变就是 $0$ ，改变就是减去 $X[i]$ ）。
那么对于 $dpR[i]$ 来说，它就可以由 $dpR[i - 1] + cost(i, 'R')$ 或者 $dpS[i - 1] + cost(i, 'R')$ 继承得来，因为无论这里的前一天是 $R$ 还是 $S$ ，当天都是 $R$ ，无法满足加 $Y[i - 1]$ 幸福值的条件。
对于 $dpS[i]$ 来说，它就可以由 $dpR[i - 1] + cost(i, 'S') + Y[i - 1]$ 或者 $dpS[i - 1] + cost(i, 'S')$ 得来。这里当前一天为 $R$ 时，就满足了前 $R$ 后 $S$ 的条件，就可以加 $Y[i - 1]$ 。
所以状态转移方程就是
$dpR[i] = max(dpR[i - 1] + cost(i, 'R'), dpS[i - 1] + cost(i, 'R'))$
$dpS[i] = max(dpR[i - 1] + Y[i - 1] + cost(i, 'S'), dpS[i - 1] + cost(i, 'S'))$
我们每次更新时都在前一天选 $R$ 或者 $S$ 中取了最优方案，因此这种方法可以保证最终最优解出现在 $dpR[N]$ 或者 $dpS[N]$ 其中之一。

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

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

11
void solved() {
12
    int N; cin >> N;
13
    string s; cin >> s;
14
    vector<ll> X(N + 1);
15
    vector<ll> Y(N);
16
    for(int i = 1; i <= N;i++) cin >> X[i];
17
    for(int i = 1; i < N;i++) cin >> Y[i];
18

19
    auto cost = [&](int i, int statue) -> ll {
20
        char c = (statue ? 'S' : 'R');
21
        return (s[i - 1] == c ? 0 : -X[i]);
22
    };
23

24
    ll dpR = cost(1, 0);
25
    ll dpS = cost(1, 1);
26
    for(int i = 2; i <= N;i++){
27
        ll ndpR = max(dpR + cost(i, 0), dpS + cost(i, 0));
28
        ll ndpS = max(dpR + Y[i - 1] + cost(i, 1), dpS + cost(i, 1));
29
        dpR = ndpR;
30
        dpS = ndpS;
31
    }
32
    cout << max(dpR, dpS) << endl;
33
}
34

35
int main() {
36
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
37
    int _ = 1;
38
    cin >> _;
39
    while (_--) {
40
        solved();
41
    }
42
    return 0;
43
}

Mkrari的个人博客

A - Decisive Battle#

B - Crop#

C - Plumage Palette#

D - Celester#