壁纸链接
题目链接：https://atcoder.jp/contests/abc469/tasks

A - Train Car#

将位置从前往后编号为 $1,2,\ldots,N$ ，再从后往前编号为 $N,N-1,\ldots,1$ 。因此前端第 $K$ 个位置对应的反向编号为 $N-K+1$ ，直接输出即可。

1
void solved(){
2
    int n, k; cin >> n >> k;
3
    cout << n - k + 1 << endl;
4
}

B - Isolated Seats#

直接遍历字符串，判断每个位置是否为空位，并且所有存在的相邻位置也都是空位。对于中间位置 $i$ ，需要满足 $S_{i-1}=S_i=S_{i+1}=x$ ；对于左右端点，只需要额外判断唯一存在的相邻位置。
当 $N=1$ 时不存在相邻位置，所以唯一字符为 $x$ 时答案为 $1$ ，否则为 $0$ ，需要单独处理。整体只需要一次线性遍历，时间复杂度为 $O(N)$ 。

1
void solved(){
2
    int n; cin >> n;
3
    int cnt = 0;
4
    string s; cin >> s;
5
    if(n == 1 && s[0] == 'x') {cout << 1 << endl; return;}
6
    else if(n == 1 && s[0] == 'o') {cout << 0 << endl; return;}
7
    for(int i = 0; i < (int)s.size();i++){
8
        if(i == 0 && s[i] == 'x' && s[i + 1] == 'x')
9
            cnt++;
10
        else if(i == (int)s.size() - 1 && s[i] == 'x' && s[i - 1] == 'x')
11
            cnt++;
12
        else if(i > 0 && s[i - 1] == 'x' && s[i] == 'x' && s[i + 1] == 'x')
13
            cnt++;
14
    }
15
    cout << cnt << endl;
16
}

C - Cantrip#

关键是分析当前持有的 $o$ 数量如何变化。每次操作会先消耗一个 $o$ ，再取得下一个字符：如果新字符为 $o$ ，持有的 $o$ 数量不变；如果为 $x$ ，持有的 $o$ 数量减一。因此，初始前缀中有多少个 $o$ ，后续就可以经过多少个 $x$ ，操作会在取得最后一个可经过的 $x$ 后停止。
对于前 $i$ 个字符，记其中 $o$ 和 $x$ 的数量分别为 $o\_cnt,x\_cnt$ 。如果 $o\_cnt=0$ ，没有可用于继续操作的 $o$ ，答案就是 $i$ 。否则停止时到达的 $x$ 在整个字符串中的序号为 $x\_cnt+o\_cnt=i$ ，也就是整个字符串中第 $i$ 个 $x$ 的位置。如果字符串中不存在第 $i$ 个 $x$ ，说明可以一直操作到序列末尾，答案为 $N$ 。
我们预处理所有 $x$ 出现的位置，然后从左往右维护前缀中 $o,x$ 的数量，每个 $i$ 都可以在 $O(1)$ 时间内得到答案。总时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

1
void solved(){
2
    int n; cin >> n;
3
    string s; cin >> s;
4

5
    vector<int> x_pos;
6
    for(int i = 0; i < n;i++){
7
        if(s[i] == 'x')
8
            x_pos.push_back(i + 1);
9
    }
10

11
    int total_x = (int)x_pos.size();
12
    int o_cnt = 0, x_cnt = 0;
13
    for(int i = 1; i <= n;i++){
14
        char c = s[i - 1];
15
        if(c == 'o') o_cnt++;
16
        else x_cnt++;
17

18
        if(!o_cnt) cout << i << endl;
19
        else{
20
            int index = x_cnt + o_cnt;
21
            if(index <= total_x)
22
                cout << x_pos[index - 1] << endl;
23
            else cout << n << endl;
24
        }
25
    }
26
}

D - The Big Two#

将每名选手看作一个点，每场决赛的两名选手 $(A_i,B_i)$ 看作一条无向边。题目要求统计二元点集 $\{x,y\}$ ，使每条边都至少有一个端点属于这个集合，也就是统计大小为 $2$ 的点覆盖。
设第一条边为 $(u,v)$ 。任何合法点覆盖都必须包含 $u,v$ 中的至少一个，因此只需要分别固定 $x=u$ 和 $x=v$ ，再统计另一个点 $y$ 的选择数量。
对于一个固定的 $x$ ，我们找到第一条不与 $x$ 相连的边 $(a,b)$ 。为了覆盖这条边， $y$ 只能是 $a$ 或 $b$ ，分别枚举这两个候选点，再遍历所有边检查 $\{x,y\}$ 能否将其覆盖。如果不存在不与 $x$ 相连的边，说明 $x$ 单独就能覆盖全部边，此时除 $x$ 以外的任意点都可以作为 $y$ ，方案数为 $N-1$ 。
$count\_with(u)$ 和 $count\_with(v)$ 的结果相加时，点集 $\{u,v\}$ 可能被计算两次。因此再检查 $\{u,v\}$ 本身是否覆盖所有边，如果满足条件就将答案减一。每次检查只需要线性扫描边集，整体时间复杂度为 $O(M)$ ，空间复杂度为 $O(M)$ 。

1
void solved(){
2
    int N, M; cin >> N >> M;
3
    vector<pii> match(M);
4
    for(auto &[a, b] : match){
5
        cin >> a >> b;
6
    }
7

8
    auto count_with = [&](int x) -> int {
9
        int first = -1;
10
        for(int i = 0; i < M;i++){
11
            int a = match[i].first, b = match[i].second;
12
            if(a != x && b != x){
13
                first = i;
14
                break;
15
            }
16
        }
17

18
        if(first == -1) return N - 1;
19

20
        int cnt = 0;
21
        int candicate[2] = {match[first].first, match[first].second};
22
        for(int y : candicate){
23
            bool ok = true;
24
            for(auto [a, b] : match){
25
                if(a != x && b != y && a != y && b != x){
26
                    ok = false;
27
                    break;
28
                }
29
            }
30
            cnt += ok;
31
        }
32
        return cnt;
33
    };
34

35
    int u = match[0].first, v = match[0].second;
36
    int ans = count_with(u) + count_with(v);
37

38
    bool first_pair_yes = true;
39
    for(int i = 0; i < M;i++){
40
        int a = match[i].first, b = match[i].second;
41
        if(u != a && u != b && v != a && v != b){
42
            first_pair_yes = false;
43
            break;
44
        }
45
    }
46
    ans -= first_pair_yes;
47

48
    cout << ans << endl;
49
}

模板：

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
ll fast_pow(ll a, ll b, ll MOD) {
12
    ll ans = 1;
13
    while (b) {
14
        if (b & 1) ans = (ans * a) % MOD;
15
        b >>= 1;
16
        a = (a * a) % MOD;
17
    }
18
    return ans;
19
}
20

21
vector<ll> get_inverse(ll n, ll MOD){
22
    vector<ll> inverse(n + 1);
23
    inverse[1] = 1;
24
    for(ll i = 2; i <= n;i++){
25
        inverse[i] = MOD - (MOD / i) * (inverse[MOD % i]) % MOD;
26
    }
27
    return inverse;
28
}
29

30
void solved() {
31
}
32

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

Mkrari的个人博客

A - Train Car#

B - Isolated Seats#

C - Cantrip#

D - The Big Two#