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

A - A#

直接遍历字符串中的每个字符。如果当前字符为 $A$ 就保持不变，否则将其替换为 $.$ ，最后输出修改后的字符串即可。

1
void solve(){
2
    string s; cin >> s;
3
    for(auto &it : s){
4
        if(it != 'A'){
5
            it = '.';
6
        }
7
    }
8
    cout << s << endl;
9
}

B - Break a Stick#

设所有部分的长度总和为 $sum$ ，在第 $i$ 个切口折断时，左侧长度为前缀和 $pre_i$ ，右侧长度为 $sum-pre_i$ 。两侧长度之差的绝对值为 $|pre_i-(sum-pre_i)|=|2pre_i-sum|$ 。
我们先预处理前缀和，再枚举 $i=1,2,\ldots,N-1$ 的所有合法切口，对上述差值取最小值即可。时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    int ans = 1e9, sum = 0;
4
    vector<int> pre(n + 1, 0), suf(n + 1, 0);
5
    for(int i = 1; i <= n;i++) {
6
        int x; cin >> x;
7
        pre[i] = pre[i - 1] + x;
8
        sum += x;
9
    }
10
    for(int i = 1; i < n;i++){
11
        ans = min(ans, abs(2 * pre[i] - sum));
12
    }
13
    cout << ans << endl;
14
}

C - On a Diet#

按照题意顺序模拟，并用滑动窗口维护当前日期之前最近 $M-1$ 天内实际吃下的总热量 $sum$ 。处理第 $i$ 天时，如果 $sum+A_i\leq K$ ，就将第 $i$ 天标记为 $Yes$ 并把 $A_i$ 加入窗口；否则标记为 $No$ ，窗口总和不变。
完成当天判断后，如果当前窗口长度已经达到 $M$ ，就将最左端日期移出。只有该日期实际吃过时，它的热量才包含在 $sum$ 中，所以代码使用 $vis$ 记录每一天的选择，并在移出时判断是否需要减去 $A_{left}$ 。这样进入下一天前， $sum$ 恰好表示仍会影响下一次决策的日期范围。
每一天只会进入和移出窗口一次，时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。由于 $K$ 和窗口和可能达到 $10^{15}$ ，需要使用 $long\ long$ 保存。

1
void solve(){
2
    int n, m; ll k; cin >> n >> m >> k;
3
    vector<ll> a(n + 1, 0);
4
    vector<bool> vis(n + 1, false);
5
    for(int i = 1; i <= n;i++) cin >> a[i];
6
    int left = 1;ll sum = 0;
7
    for(int i = 1; i <= n;i++){
8
        if(i - left + 1 <= m){
9
            if(sum + a[i] <= k){
10
                sum += a[i];
11
                vis[i] = true;
12
            }
13
            if(i - left + 1 == m){
14
                if(vis[left] == true)
15
                    sum -= a[left];
16
                left++;
17
            }
18
        }
19
    }
20
    for(int i = 1; i <= n;i++){
21
        if(vis[i]) cout << "Yes" << '\n';
22
        else cout << "No" << '\n';
23
    }
24
}

D - Bomber Mad#

首先确定所有安全空格。一个位置 $(i,j)$ 安全，当且仅当第 $i$ 行没有炸弹且第 $j$ 列没有炸弹。因此可以分别预处理所有无炸弹的行集合 $R$ 和列集合 $C$ ，全部安全空格正好是笛卡尔积 $R\times C$ 。
接下来需要统计到安全空格的最短路不超过 $K$ 的空格。将所有安全空格同时加入队列并令距离为 $0$ ，执行一次多源 $BFS$ 。因为每次只能向上下左右的空格移动，且所有边权均为 $1$ ，多源 $BFS$ 得到的 $dist[i][j]$ 就是位置 $(i,j)$ 到最近安全空格的最少移动次数。搜索过程中不进入炸弹格，并且只扩展距离不超过 $K$ 的状态，最终访问到的格子数就是答案。
如果整个网格没有炸弹，那么每个格子本身都是安全空格，可以直接输出 $H\times W$ 。安全空格数量至多为 $H\times W$ ，因此总时间复杂度和空间复杂度均为 $O(HW)$ 。

1
int dx[5] = {0, 1, 0, 0, -1};
2
int dy[5] = {0, 0, 1, -1, 0};
3

4
void solve(){
5
    int H, W, K;
6
    cin >> H >> W >> K;
7
    bool has_boom = false;
8
    vector<string> grid(H + 1);
9
    for(int i = 1; i <= H;i++){
10
        cin >> grid[i];
11
        grid[i] = " " + grid[i];
12
        if(grid[i].find('#') != grid[i].npos)
13
            has_boom = true;
14
    }
15
    if(!has_boom){
16
        cout << H * W << endl;
17
        return;
18
    }
19
    vector<int> q1, q2;
20
    for(int i = 1; i <= H;i++){
21
        bool h = true;
22
        for(int j = 1; j <= W;j++){
23
            if(grid[i][j] == '#') h = false;
24
        }
25
        if(h) q1.push_back(i);
26
    }
27
    int ans = 0;
28
    for(int i = 1; i <= W;i++){
29
        bool w = true;
30
        for(int j = 1; j <= H;j++){
31
            if(grid[j][i] == '#') w = false;
32
        }
33
        if(w) q2.push_back(i);
34
    }
35
    queue<pii> q;
36
    vector<vector<int>> dist(H + 1, vector<int>(W + 1, -1));
37
    for(int i = 0; i < (int)q1.size();i++){
38
        for(int j = 0; j < (int)q2.size();j++){
39
            int a = q1[i], b = q2[j];
40
            dist[a][b] = 0;
41
            q.push({a, b});
42
        }
43
    }
44
    while(!q.empty()){
45
        auto [x, y] = q.front();
46
        q.pop();
47

48
        if(dist[x][y] > K) continue;
49
        ans++;
50
        for(int i = 1; i <= 4;i++){
51
            int tx = x + dx[i];
52
            int ty = y + dy[i];
53
            if(tx >= 1 && tx <= H && ty >= 1 && ty <= W && dist[tx][ty] == -1 && grid[tx][ty] != '#'){
54
                dist[tx][ty] = dist[x][y] + 1;
55
                if(dist[tx][ty] <= K)
56
                    q.push({tx, ty});
57
            }
58
        }
59
    }
60
    cout << ans << endl;
61
}

E - Odd Cycle#

无向图不存在奇环，当且仅当它是二分图。因此可以在 $BFS$ 过程中进行二染色：起点染为 $1$ ，每条树边的另一端染为相反颜色。如果遍历到一条连接同色顶点 $U,V$ 的边，就说明图中存在奇环；如果所有边都满足两端异色，则图是二分图，输出 $-1$ 。
为了还原奇环，染色时同时记录 $BFS$ 树中的父节点 $fa$ 和深度 $dep$ 。找到同色边 $(U,V)$ 后，分别让 $U,V$ 沿父节点向上移动：先将深度较大的顶点提升到相同深度，再同步上移直到到达最近公共祖先。这个过程得到 $BFS$ 树上从 $U$ 到 $V$ 的唯一简单路径，最后再加上原图中的边 $(V,U)$ 就形成一个简单环。
由于 $U,V$ 颜色相同，它们的深度奇偶性相同，所以树上路径长度为偶数；再加上边 $(U,V)$ 后，环的边数以及顶点数均为奇数。代码将 $U$ 到最近公共祖先的路径存入 $path1$ ，将 $V$ 侧路径反转后接到末尾，输出的顶点序列首尾通过冲突边相连。
每个顶点和每条边只会被遍历常数次，单个测试用例的时间复杂度为 $O(N+M)$ ，空间复杂度为 $O(N+M)$ 。题目保证图连通，因此从顶点 $1$ 开始一次 $BFS$ 即可覆盖全部顶点。

1
void solve(){
2
    int n, m;
3
    cin >> n >> m;
4
    vector<vector<int>> g(n + 1);
5
    for(int i = 1; i <= m;i++){
6
        int u, v;
7
        cin >> u >> v;
8
        g[u].push_back(v);
9
        g[v].push_back(u);
10
    }
11
    vector<int> color(n + 1, 0), fa(n + 1, 0), dep(n + 1, 0);
12
    int U = -1, V = -1;
13
    queue<int> q;
14
    color[1] = 1, fa[1] = 0;
15
    dep[1] = 0, q.push(1);
16
    while(!q.empty() && U == -1){
17
        int u = q.front();
18
        q.pop();
19
        for(auto v : g[u]){
20
            if(color[v] == 0){
21
                color[v] = -color[u];
22
                fa[v] = u;
23
                dep[v] = dep[u] + 1;
24
                q.push(v);
25
            }
26
            else if(color[v] == color[u]){
27
                U = u;
28
                V = v;
29
                break;
30
            }
31
        }
32
    }
33
    if(U == -1){cout << -1 << '\n'; return;}
34
    int u = U, v = V;
35
    vector<int> path1, path2;
36
    while(dep[u] > dep[v]){
37
        path1.push_back(u); u = fa[u];
38
    }
39
    while(dep[v] > dep[u]){
40
        path2.push_back(v); v = fa[v];
41
    }
42
    while(u != v){
43
        path1.push_back(u), path2.push_back(v);
44
        u = fa[u], v = fa[v];
45
    }
46
    path1.push_back(u);
47
    reverse(path2.begin(), path2.end());
48
    cout << (int)path1.size() + (int)path2.size() << '\n';
49
    for(auto it : path1) cout << it << " ";
50
    for(auto it : path2) cout << it << " ";
51
    cout << '\n';
52
}

模板：

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

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

10
ll fast_pow(ll a, ll b, ll MOD){
11
    ll ans = 1;
12
    while(b){
13
        if(b & 1) ans = (ans * a) % MOD;
14
        b >>= 1;
15
        a = (a * a) % MOD;
16
    }
17
    return ans;
18
}
19

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

29
void solve(){
30
}
31

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

Mkrari的个人博客

A - A#

B - Break a Stick#

C - On a Diet#

D - Bomber Mad#

E - Odd Cycle#