AtCoder Beginner Contest 375

2024-10-12 23:18 由 ~Lanly~ 发表于 #其他

省流版

A. 枚举所有子串判断即可
B. 模拟计算记录累加即可
C. 根据旋转的周期性对每个点旋转次数取模后暴力旋转即可
D. 枚举\(k\)，考虑 \(i,j\)的对数，写成数学表达式后维护个数和位置和即可
E. 背包问题，以前两个数组和为状态，考虑每个数移动到何处转移即可
F. 逆向，删边变加边，维护加边后的距离变化即可
G. 最短路径图的割边判断，根据最短路条数判断是否必经即可

A - Seats (abc375 A)

题目大意

给定一个字符串，问有多少个形如#.#的子串。

解题思路

枚举所有子串依次比较即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += (s.substr(i, 3) == "#.#");
    }
    cout << ans << '\n';

    return 0;
}

B - Traveling Takahashi Problem (abc375 B)

题目大意

二维平面，给定\(n\)个点，从\((0,0)\)出发，依次经历这些点，最后回到 \((0,0)\)，求其欧几里德距离和。

解题思路

依次模拟计算距离和，累加即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<array<int, 2>> p(n + 2);
    p[0] = {0, 0};
    for (int i = 1; i < n + 1; i++) {
        cin >> p[i][0] >> p[i][1];
    }
    p[n + 1] = {0, 0};
    double ans = 0;
    auto dist = [](array<int, 2> a, array<int, 2> b) {
        return sqrt(1ll * (a[0] - b[0]) * (a[0] - b[0]) +
                    1ll * (a[1] - b[1]) * (a[1] - b[1]));
    };
    for (int i = 1; i < p.size(); ++i) {
        ans += dist(p[i], p[i - 1]);
    }
    cout << fixed << setprecision(10) << ans << '\n';

    return 0;
}

C - Spiral Rotation (abc375 C)

题目大意

给定一个\(n \times n\)的正方形，对于 \(i \in [1, n]\) ，依次进行如下操作：

以\((i,i)\)为一角的 \((n - i + 1) \times (n - i - 1)\) 的正方形顺时针旋转\(90\)度。

输出最终的矩形。

解题思路

注意到旋转的区间是往中间收缩的，因为旋转操作具有结合性和周期性（旋转\(4\)次等于没旋转），所以依次遍历该正方形的每个元素\((i,j)\)，可以求出它进行了多少次顺时针旋转 \(90\)度，然后对 \(4\)取余后，再进行对应次数的顺时针旋转即可。

其实暴力的复杂度是\((2n^2 \log n)\)，虽然\(n \leq 3000\)，但貌似还是不能过。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<string> s(n);
    for (auto& i : s)
        cin >> i;
    auto tr = [](int x, int y, int n) { return make_pair(y, n - 1 - x); };
    auto tr_cnt = [&](int x, int y, int n, int c) {
        for (int i = 0; i < c; ++i) {
            tie(x, y) = tr(x, y, n);
        }
        return make_pair(x, y);
    };
    vector<string> t = s;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int cnt = min({i, j, n - 1 - i, n - 1 - j}) + 1;
            auto [x, y] = tr_cnt(i, j, n, cnt % 4);
            t[x][y] = s[i][j];
        }
    }
    for (auto i : t)
        cout << i << '\n';

    return 0;
}

D - ABA (abc375 D)

题目大意

给定一个字符串\(s\)，问有多少\(i < j < k\)，满足 \(s_is_js_k\)是回文串。

解题思路

枚举\(k\)，考虑满足条件的 \(i\)，那必然有\(s_i == s_k\)，然后固定这个\(i\)，考虑 \(j\)的方案数，即为 \(k - i - 1\)。

也就是说，对于当期 \(k\)，其对答案的贡献为 \(\sum_{i < k \& s_i==s_k} k - i - 1 = (k-1) cnt_{a_k} - \sum_{i < k \& s_i == s_k} i\)。

因此我们只需动态维护两个数组：

\(cnt_i\)表示字符为\(i\)的位置数
\(sum_i\)表示字符为\(i\)的位置的和

就可以\(O(1)\)求得固定\(k\)时， \((i,j,k)\)的方案数。

对所有的\(k\)累加即为答案。时间复杂度为 \(O(n)\)。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    array<int, 26> cnt{};
    array<LL, 26> sum{};
    LL ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        int c = s[i] - 'A';
        ans += 1ll * cnt[c] * (i - 1) - sum[c];
        cnt[c]++;
        sum[c] += i;
    }
    cout << ans << '\n';

    return 0;
}

E - 3 Team Division (abc375 E)

题目大意

三个数组，操作为，花费\(1\)的代价，将一个数从一个数组移动到另一个数组。

问最小的代价，使得三个数组的和相等，或告知不可行。

数组和\(\sum b_i \leq 1500\)。

解题思路

考虑两个数组的简化版。

考虑朴素搜索，即依次考虑每个数，应该移动还是不移动。其复杂度显然是\(O(2^n)\)。

因为状态是包含了每个数的数组位置，它过于冗余了，考虑到我们要求的答案，我们可以仅保留一个简化的状态即可：

一个数组的和

知道了一个数组的和，对于当前数，移动还是不移动，其带来的影响都可以进行转移，最后也能直接得到答案。

因为总数不变，所以知道了一个数组的和，另一个数组的和其实也知道了，即设 \(dp[i][j]\)表示考虑了前 \(i\)个数，第一个数组和为 \(j\)的最小移动代价。对于一个数，考虑移动或不移动，对 \(j\)的影响转移即可。这样的复杂度即为 \(O(n \sum b_i)\)

而这里有三个数组，按照同样的思路，知道了前两个数组的和，第三个数组的和也确定了，即设\(dp[i][j][k]\)表示考虑了前 \(i\)个数，第一个数组和为 \(j\)，第二个数组和为\(k\)的最小移动代价，转移仍然是对于一个数，考虑移动到哪个数组，或者不移动即可。这样的时间复杂度为\(O(n (\sum b_i) ^ 2)\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    array<vector<int>, 3> p{};
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        --a;
        p[a].push_back(b);
        sum += b;
    }
    if (sum % 3 != 0)
        cout << -1 << '\n';
    else {
        vector<vector<int>> dp(sum + 1, vector<int>(sum + 1, inf));
        dp[accumulate(p[0].begin(), p[0].end(), 0)]
          [accumulate(p[1].begin(), p[1].end(), 0)] = 0;
        for (auto& i : p[0]) {
            auto dp2 = dp;
            for (int j = 0; j <= sum; j++) {
                for (int k = 0; k <= sum; k++) {
                    if (j >= i)
                        dp2[j - i][k] = min(dp2[j - i][k], dp[j][k] + 1);
                    if (j >= i && k + i <= sum)
                        dp2[j - i][k + i] =
                            min(dp2[j - i][k + i], dp[j][k] + 1);
                }
            }
            dp.swap(dp2);
        }
        for (auto& i : p[1]) {
            auto dp2 = dp;
            for (int j = 0; j <= sum; j++) {
                for (int k = 0; k <= sum; k++) {
                    if (k >= i)
                        dp2[j][k - i] = min(dp2[j][k - i], dp[j][k] + 1);
                    if (k >= i && j + i <= sum)
                        dp2[j + i][k - i] =
                            min(dp2[j + i][k - i], dp[j][k] + 1);
                }
            }
            dp.swap(dp2);
        }
        for (auto& i : p[2]) {
            auto dp2 = dp;
            for (int j = 0; j <= sum; j++) {
                for (int k = 0; k <= sum; k++) {
                    if (k + i <= sum)
                        dp2[j][k + i] = min(dp2[j][k + i], dp[j][k] + 1);
                    if (j + i <= sum)
                        dp2[j + i][k] = min(dp2[j + i][k], dp[j][k] + 1);
                }
            }
            dp.swap(dp2);
        }
        int target = sum / 3;
        if (dp[target][target] == inf) {
            dp[target][target] = -1;
        }
        cout << dp[target][target] << '\n';
    }

    return 0;
}

F - Road Blocked (abc375 F)

题目大意

给定一张无向图，维护以下两种操作：

1 x，删去第\(x\)条边
2 u v，问\(u \to v\)的最短路长度

其中操作 \(1\)最多 \(300\)次。

解题思路

加边往往比删边好做，注意到询问没有强制在线，因此可以倒着考虑操作，这样删边操作就变成加边操作了。

因为点数\(\leq 300\)，先用 \(floyd\)花 \(O(n^3)\)求出任意两点的最短路，这样操作 \(2\)就可以 \(O(1)\)回答，然后考虑操作 \(1\)加边后，怎么更新这个两点的最短路。

考虑加的边 \(u \to v\)对任意两点 \(x \to y\) 的最短路的影响，其实就两种情况：

\(x \to y\)的最短路不经过 \(u \to v\)
\(x \to y\)的最短路经过 \(u \to v\)

在加边之前，\(dis[x][y]\)的值就属于第一种情况，现在加边后， \(dis[x][y]\)就是这两种情况的最小值，因此\(dis[x][y]\)只要和第二种情况取个最小值，这样\(dis[x][y]\)就变成加上边 \(u \to v\)后的值了。

而第二种情况的距离即为 \(dis[x][u] + u \to v + dis[v][y]\)或 \(dis[x][v] + v \to u + dis[u][y]\)。

加一边，更新一次的复杂度为 \(O(n^2)\)，因为操作 \(1\)不超过 \(300\)，因此总的时间复杂度为 \(O(n^3)\)。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL inf = 1e18;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<LL>> dis(n, vector<LL>(n, inf));
    vector<array<int, 3>> edges(m);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        dis[u][v] = dis[v][u] = min(dis[u][v], (LL)w);
        edges[i] = {u, v, w};
    }
    for (int i = 0; i < n; ++i)
        dis[i][i] = 0;
    vector<array<int, 3>> query(q);
    for (auto& [op, x, y] : query) {
        cin >> op >> x;
        if (op == 1) {
            --x;
            auto [u, v, w] = edges[x];
            dis[u][v] = dis[v][u] = inf;
        } else {
            cin >> y;
            --x, --y;
        }
    }
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    vector<LL> ans;
    for (int i = q - 1; i >= 0; --i) {
        auto [op, x, y] = query[i];
        if (op == 1) {
            auto [u, v, w] = edges[x];
            dis[u][v] = dis[v][u] = min(dis[u][v], (LL)w);
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j) {
                    dis[i][j] =
                        min(dis[i][j], dis[i][u] + dis[u][v] + dis[v][j]);
                    dis[i][j] =
                        min(dis[i][j], dis[i][v] + dis[v][u] + dis[u][j]);
                }
        } else {
            ans.push_back((dis[x][y] == inf ? -1 : dis[x][y]));
        }
    }
    reverse(ans.begin(), ans.end());
    for (auto x : ans)
        cout << x << '\n';

    return 0;
}

G - Road Blocked 2 (abc375 G)

题目大意

给定一张无向图，对于每一条边，回答以下询问：

删去该边后，\(1 \to n\)的最短路长度是否发生变化。

解题思路

题意就是问一条边是不是最短路的必经之边，换句话说就是一条边是否被所有最短路径经过。

由于\(1 \to n\)可能有多条最短路，我们先求出每条边，是否被一条最短路经过。

如果一条边 \(u \to v\)满足： \(1 \to n = 1 \to u \to v \to n\)或者 \(1 \to n = 1 \to v \to u \to n\)，这说明该边被一条最短路径经过。

但怎么说该边被所有的最短路径经过呢？

如果\(1 \to n\)的最短路径有 \(z\)条，而 \(1 \to u\)的最短路径有 \(x\)条， \(v \to n\)的最短路径有 \(y\)条，由乘法原理，\(1 \to n\)且经过 \(u \to v\)的路径就有 \(xy\)条，而如果有\(z = xy\)，那这就说明该边是必经边。

因此分别从点\(1\)和点 \(n\)进行 \(dijkstra\)，求出 \(dis_1[i],dis_n[i]\)和 \(cnt_1[i],cnt_n[i]\) 表示\(1 \to i\)的最短路径长度和数量， \(n \to i\)的最短路径长度和数量，对于任意一条边\(u \to v, w\)，如果满足二者任意其一：

\(dis_1[u] + w + dis_n[v] == dis_1[n]\) 且\(cnt_1[u] \times cnt_n[v] == cnt_1[n]\)
\(dis_1[v] + w + dis_n[u] == dis_1[n]\) 且\(cnt_1[v] \times cnt_n[u] == cnt_1[n]\)

则该边是最短路必经边。

其实根据一条边是否被最短路经过，建立一张最短路图，这些必经边就是所谓的割边，即删去该边后， \(1 \to n\)不连通。

注意 \(cnt\)可能会非常大，甚至会超过 \(int128\)，而此处我们只需判断乘积是否相等，可以取模。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL inf = 1e18;
const int mo = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<array<int, 2>>> edge(n);
    vector<array<int, 3>> e(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
        e[i] = {u, v, w};
    }
    auto dijkstra = [&](int s) {
        vector<LL> dis(n, inf);
        vector<LL> cnt(n, 0);
        dis[s] = 0;
        cnt[s] = 1;
        priority_queue<array<LL, 2>, vector<array<LL, 2>>,
                       greater<array<LL, 2>>>
            team;
        team.push({0, s});
        while (!team.empty()) {
            auto [d, u] = team.top();
            team.pop();
            if (dis[u] < d)
                continue;
            for (auto [v, w] : edge[u]) {
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    team.push({dis[v], v});
                    cnt[v] = cnt[u];
                } else if (dis[v] == dis[u] + w) {
                    cnt[v] += cnt[u];
                    if (cnt[v] >= mo)
                        cnt[v] -= mo;
                }
            }
        }
        return make_pair(dis, cnt);
    };
    auto [dis1, cnt1] = dijkstra(0);
    auto [dis2, cnt2] = dijkstra(n - 1);
    vector<int> ans(m, 0);
    for (int i = 0; i < m; ++i) {
        auto& [u, v, w] = e[i];
        if (dis1[u] + w + dis2[v] == dis1[n - 1] &&
                cnt1[u] * cnt2[v] % mo == cnt1[n - 1] ||
            dis1[v] + w + dis2[u] == dis1[n - 1] &&
                cnt1[v] * cnt2[u] % mo == cnt1[n - 1]) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }
    }

    return 0;
}