Panasonic Programming Contest 2024（AtCoder Beginner Contest 375） - AtCoder

A - Seats

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;
    
    int ans = 0;
    for (int i = 0; i < n - 2; i++) {
        ans += s.substr(i, 3) == "#.#";
    }
    cout << ans << "\n";
    
    return 0;
}

B - Traveling Takahashi Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << fixed << setprecision(20);

    int n;
    cin >> n;
    n += 2;

    vector<pair<double, double>> p(n);
    for (int i = 1; i < n - 1; i++) {
        cin >> p[i].first >> p[i].second;
    }

    long double res;
    for (int i = 1; i < n; i++) {
        res += sqrtl(
            ((p[i].first - p[i - 1].first) * (p[i].first - p[i - 1].first))
          + ((p[i].second - p[i - 1].second) * (p[i].second - p[i - 1].second))
        );
    }
    cout << res << "\n";

    return 0;
}

C - Spiral Rotation

距离矩阵边界ii 的格子顺时针转了ii 次，也就是i mod 4i \bmod 4 次，遍历距离矩阵边界ii 的所有格子即可，总共有0∘,90∘,180∘,270∘0^{\circ},90^{\circ},180^{\circ},270^{\circ} 这四种可能。时间复杂度Θ(n2)\Theta(n^{2})。

（代码写得比较蠢）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<string> s(n), res(n, string(n, '$'));
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    for (int t = 0; t < n / 2; t++) {
        if (t % 4 == 0) {  // 90
            for (int i = t; i < n - t; i++) {
                for (int j = t; j <= t; j++) {
                    res[j][n - 1 - i] = s[i][j];
                }
                for (int j = n - 1 - t; j <= n - 1 - t; j++) {
                    res[j][n - 1 - i] = s[i][j];
                }
            }
            for (int j = t; j < n - t; j++) {
                for (int i = t; i <= t; i++) {
                    res[j][n - 1 - i] = s[i][j];
                }
                for (int i = n - 1 - t; i <= n - 1 - t; i++) {
                    res[j][n - 1 - i] = s[i][j];
                }
            }
        } else if (t % 4 == 1) {  // 180
            for (int i = t; i < n - t; i++) {
                for (int j = t; j <= t; j++) {
                    res[n - 1 - i][n - 1 - j] = s[i][j];
                }
                for (int j = n - 1 - t; j <= n - 1 - t; j++) {
                    res[n - 1 - i][n - 1 - j] = s[i][j];
                }
            }
            for (int j = t; j < n - t; j++) {
                for (int i = t; i <= t; i++) {
                    res[n - 1 - i][n - 1 - j] = s[i][j];
                }
                for (int i = n - 1 - t; i <= n - 1 - t; i++) {
                    res[n - 1 - i][n - 1 - j] = s[i][j];
                }
            }
        } else if (t % 4 == 2) {  // -90
            for (int i = t; i < n - t; i++) {
                for (int j = t; j <= t; j++) {
                    res[n - 1 - j][i] = s[i][j];
                }
                for (int j = n - 1 - t; j <= n - 1 - t; j++) {
                    res[n - 1 - j][i] = s[i][j];
                }
            }
            for (int j = t; j < n - t; j++) {
                for (int i = t; i <= t; i++) {
                    res[n - 1 - j][i] = s[i][j];
                }
                for (int i = n - 1 - t; i <= n - 1 - t; i++) {
                    res[n - 1 - j][i] = s[i][j];
                }
            }
        } else {  // 0
            for (int i = t; i < n - t; i++) {
                for (int j = t; j <= t; j++) {
                    res[i][j] = s[i][j];
                }
                for (int j = n - 1 - t; j <= n - 1 - t; j++) {
                    res[i][j] = s[i][j];
                }
            }
            for (int j = t; j < n - t; j++) {
                for (int i = t; i <= t; i++) {
                    res[i][j] = s[i][j];
                }
                for (int i = n - 1 - t; i <= n - 1 - t; i++) {
                    res[i][j] = s[i][j];
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << res[i] << "\n";
    }

    return 0;
}

D - ABA

题意 给定字符串，求(i,j,k)(i,j,k) 的组数，满足i<j<ki<j<k 且sisjsks_{i}s_{j}s_{k} 是回文串。

思路 小清新 map 题。

实际上是问所有满足sl=srs_{l}=s_{r} 的r−l−1r-l-1 之和。开个 map，存储左端点信息，枚举右端点，边计算边加到 map 里。

具体来说，map 里存：

  • 键：26 种字母；
  • 值：这种字母的数量cnt⁡\operatorname{cnt} 以及下标之和sum⁡\operatorname{sum}。

则枚举到右端点rr 时，map 里左端点对答案的贡献是∑sl=sr(r−l−1)=cnt⁡(r−1)−sum⁡\sum \limits_{s_{l}=s_{r}}(r-l-1)=\operatorname{cnt}(r-1)-\operatorname{sum}。

时间复杂度Θ(n)\Theta(n)，只跑了 1ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    array<ll, 26> cnt{}, sum{};

    ll res = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s[i] - 'A';
        res += cnt[c] * (i - 1) - sum[c];
        cnt[c]++;
        sum[c] += i;
    }
    cout << res << "\n";

    return 0;
}

E - 3 Team Division

题意 有三个类型共nn 人，每个人的初始类型已知，每个人有能力值。可以选择进行若干次操作：每次操作交换两个人的类型，而能力值不变。问能否使得每个类型的能力值之后相等。如果可能，求最少操作次数。

思路 和上个题差不多，还是开个 map。依次处理每个人，map 里存：

  • 键：ii 为类型 1 的能力和，jj 为类型 2 的能力和（不设kk 是因为类型 3 的能力和可以由i,ji,j 惟一确定）；
  • 值：修改的最小代价。

时间复杂度Θ(ns2)\Theta(ns^{2})，其中s=13∑bs=\cfrac{1}{3}\sum b。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int inf = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int, int>> a(n);
    int sum = 0;
    for (auto& [x, b] : a) {
        cin >> x >> b;
        sum += b;
    }

    if (sum % 3) {
        cout << "-1\n";
    }
    else {
        sum /= 3;
        vector mp(sum + 1, vector(sum + 1, inf));
        mp[0][0] = 0;
        for (auto& [x, b] : a) {
            vector nmp(sum + 1, vector(sum + 1, inf));
            for (int i = 0; i <= sum; i++) {
                for (int j = 0; j <= sum; j++) {
                    if (i >= b) nmp[i][j] = min(nmp[i][j], mp[i - b][j] + (x != 1));
                    if (j >= b) nmp[i][j] = min(nmp[i][j], mp[i][j - b] + (x != 2));
                    nmp[i][j] = min(nmp[i][j], mp[i][j] + (x != 3));
                }
            }
            mp = nmp;
        }
        cout << (mp[sum][sum] == inf ? -1 : mp[sum][sum]) << "\n";
    }

    return 0;
}

F - Road Blocked（全源最短路）

题意 无向图，有边权，两种操作：

  1. 永久删去一条边；
  2. 询问u,vu,v 最短路。

数据范围：n⩽300, q⩽2×105, q1⩽300n \leqslant 300,\ q \leqslant 2\times 10^{5}, \ q_{1} \leqslant 300。

思路 对于操作一，跑 300 次全源最短路时间是不够的，而且这加强了问题。应当考虑删边的影响。

删边不好做，倒着处理询问，转化为加边。设加上了s−ts-t 边，那么u−vu-v 最短路可能会更新，如果更新那必须经过s−ts-t 边，路径长度是du−s+w+dt−vd_{u-s}+w+d_{t-v} 或du−t+w+ds−vd_{u-t}+w+d_{s-v}。遍历u,vu,v 更新最短路。时间复杂度Θ(n3+q1n2)\Theta(n^{3}+q_{1}n^{2})。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll Inf = 0x3f3f3f3f3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<array<int, 3>> E(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        E[i] = { u, v, w };
    }

    vector<array<int, 3>> que(q);
    vector<int> del(m);
    for (int i = 0; i < q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            x--;
            del[x] = 1;
            que[i] = { op, x, 0 };
        } else {
            int u, v;
            cin >> u >> v;
            u--, v--;
            que[i] = { op, u, v };
        }
    }

    vector dis(n, vector(n, Inf));
    for (int u = 0; u < n; ++u) {
        dis[u][u] = 0;
    }
    for (int i = 0; i < m; i++) {
        if (!del[i]) {
            auto [u, v, w] = E[i];
            dis[u][v] = dis[v][u] = w;
        }
    }
    for (int k = 0; k < n; ++k) {
        for (int u = 0; u < n; ++u) {
            for (int v = 0; v < n; ++v) {
                dis[u][v] = min(dis[u][v], dis[u][k] + dis[k][v]);
            }
        }
    }

    vector<ll> ans(q);
    for (int i = q - 1; i >= 0; i--) {
        auto [op, a, b] = que[i];
        if (op == 1) {
            auto [s, t, w] = E[a];
            for (int u = 0; u < n; ++u) {
                for (int v = 0; v < n; ++v)
                    dis[u][v] = min(dis[u][v], min(dis[u][s] + dis[t][v] + w, dis[u][t] + dis[s][v] + w));
            }
        } else {
            ans[i] = dis[a][b];
        }
    }

    for (int i = 0; i < q; i++) {
        if (ans[i]) cout << (ans[i] == Inf ? -1 : ans[i]) << "\n";
    }

    return 0;
}

G - Road Blocked 2（最短路计数）

题意 无向图，有边权，mm 次询问，每次询问删去第ii 条边是否会影响1−n1-n 最短路，询问间独立。

数据范围：n,m⩽2×105n ,m \leqslant 2\times 10^{5}。

思路 实际上是询问最短路是否必须经过u−vu-v，如果是，那必须长度一样，且路径唯一。具体来说，要满足d1u+w+dvn=d1nd_{1u}+w+d_{vn}=d_{1n}，以及p1u⋅pvn=p1np_{1u}\cdot p_{vn}=p_{1n}，其中pp 表示最短路数量。注意uu 是靠近11 的那个点（也就是满足d1u<d1vd_{1u}<d_{1v}）。

从11 和nn 各跑一次最短路，同时最短路计数。最短路计数会炸 int128，可以用 double 或者取模判断。

时间复杂度Θ(mlog⁡m)\Theta(m\log m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll Inf = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> g(n);
    vector<array<int, 3>> E(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        g[u].push_back({ w, v });
        g[v].push_back({ w, u });
        E[i] = { u, v, w };
    }

    auto Dijkstra = [&](int s) {
        vector<ll> dis(n, Inf); 
        vector<int> vis(n);     
        vector<int> from(n, -1);  
        vector<ll> pcnt(n);   
        dis[s] = 0, pcnt[s] = 1;  
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> Q;
        Q.push({ 0, s });
        while (!Q.empty()) {
            auto [d, u] = Q.top(); Q.pop();
            if (vis[u]) continue;          
            vis[u] = 1;
            for (auto& [w, v] : g[u]) {
                if (dis[v] > w + d) {
                    dis[v] = w + d;         
                    from[v] = u;            
                    pcnt[v] = pcnt[u];       
                    Q.push({ dis[v], v });  
                }
                else if (dis[v] == w + d) {
                    (pcnt[v] += pcnt[u]) %= mod;      
                }
            }
        }
        return make_pair(dis, pcnt);
    };
    auto [d1, p1] = Dijkstra(0);
    auto [dn, pn] = Dijkstra(n - 1);
    
    for (auto& [u, v, w] : E) {
        if (d1[u] > d1[v]) swap(u, v);
        bool only = (d1[u] + w + dn[v] == dn[0]) && (p1[u] * pn[v] % mod == pn[0]);
        cout << (only ? "Yes" : "No") << "\n";
    }

    return 0;
}