ABC375(A-G)

A - Seats

题目大意

给你一个字符串 \(S\)，\(S\) 由字符 # 和 . 组成，问： \(S\) 中有多少个 . 的两边是 # ？

参考代码

C++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for(int i = 1; i < n - 1; i++)
    {
        if(s[i] == '.' && s[i-1] == '#' && s[i+1] == '#')
        {
            ans++;
            i++;
        }
    }
    cout << ans << endl;
    return 0;
}

---

B - Traveling Takahashi Problem

题目大意

你在二维平面的原点，平面上有 \(N\) 个点，第 \(i\) 个点的坐标是 \((X_i, Y_i)\)，你将按顺序访问这 \(N\) 个点，问：总路程是多少？

参考代码

C++

#include <cmath>
#include <iomanip>
#include <iostream>

using namespace std;

double distance(double x1, double y1, double x2, double y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }

int main()
{
    int n;
    cin >> n;
    double x = 0, y = 0, nx, ny;
    double ans = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> nx >> ny;
        ans += distance(x, y, nx, ny);
        x = nx;
        y = ny;
    }
    ans += distance(x, y, 0, 0);
    cout << fixed << setprecision(6) << ans << endl;
    return 0;
}

---

C - Spiral Rotation

题目大意

给你一个 \(N \times N\) 的网格，其中 \(2 \le N \le 3000\) 且 \(N\) 是偶数。网格中每个格子有一个字符。

你将执行以下操作 \(\frac{N}{2}\) 次：在第 \(i(i = 1, 2, ..., \frac{N}{2})\) 次操作中，对于所有满足 \(i \le x, y \le N+1-i\) 的 \(x\) 和 \(y\)，同时 将 \((y, N+1-x)\) 的字符替换成 \((x, y)\) 的字符。

输出执行所有操作后的网格。

解题思路

可以发现一次操作相当于将 \(i \le x, y \le N+1-i\) 范围内字符顺时针旋转 \(90^\circ\)，但是直接模拟的话时间复杂度达到 \(O(N^3)\)。进一步可以发现，从 \(i\) 到 \(i+1\) 需要旋转的圈数越来越少，这样从最外圈开始，每一圈旋转的次数都可以算出来，模 \(4\) 即可。

参考代码

C++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int n;

void print(const vector<string> &g)
{
    for (auto s : g)
        cout << s << endl;
    cout << endl;
}

void spin(vector<string> &g, int r)
{
    string t = g[r];
    for (int j = r; j < n - r; j++)
        g[r][j] = g[n - j - 1][r];
    for (int j = r; j < n - r; j++)
        g[j][r] = g[n - r - 1][j];
    for (int j = r; j < n - r; j++)
        g[n - r - 1][j] = g[n - j - 1][n - r - 1];
    for (int j = r; j < n - r; j++)
        g[j][n - r - 1] = t[j];
}

int main()
{
    cin >> n;
    vector<string> g(n);
    for (int i = 0; i < n; i++)
        cin >> g[i];
    for (int i = 0; i < n / 2; i++)
    {
        int cnt = (i + 1) % 4;
        while (cnt--)
            spin(g, i);
    }
    print(g);
    return 0;
}

---

D - ABA

题目大意

给你一个字符串 \(S(1 \le |S| \le 2 \times 10 ^ 5)\)，字符串由大写字母构成。设 \(S_x\) 表示 \(S\) 的第 \(x\) 个字符。

找到满足以下条件的三元组 \((i, j, k)\) 的个数：

• \(1 \le i \le j \le k \le |S|\)
• \(S_iS_jS_k\) 是回文字符串

解题思路

第一种做法我们可以枚举 \(j\)，然后维护左右两边每种字符的数量，直接用左边的字符数乘以右边的字符数就好，时间复杂度 \(O(26|S|)\)

第二种做法我们可以枚举 \(k\)，维护之前出现的每种字符的数量以及坐标之和。遍历到 \(k\) 的时候，查找与 \(S_k\) 相等的字符有多少个，再算出中间能插入多少个字符，时间复杂度 \(O(|S|)\)，下面的代码是第二种做法。

参考代码

C++

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;
using LL = long long;

struct Node
{
    int cnt;
    LL sum;
};

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    unordered_map<char, Node> mp;
    LL ans = 0;
    for(int i = 0; i < n; i++)
    {
        char ch = s[i];
        auto it = mp.find(ch);
        if(it == mp.end())
        {
            mp[ch] = {1, i};
            continue;
        }
        auto &[cnt, sum] = it->second;
        ans += (LL)cnt * (i - 1) - sum;
        cnt++;
        sum += i;
    }
    cout << ans << endl;
    return 0;
}

---

E - 3 Team Division

题目大意

有 \(N(3 \le N \le 100)\) 个人和 \(3\) 只队伍，初始的时候，第 \(i\) 个人属于 \(A_i(A_i \in \{1, 2, 3\})\) 队伍。第 \(i\) 个人的力量为 \(B_i\)，其中 \(\sum\limits_{i=1}^N B_i \le 1500\)，队伍的总力量值为队伍中所有人的力量的和。你可以将任意一个人换到任意队伍中，问：至少要更换多少个人的队伍，才能让三支队伍的总力量值都相等？如果无解输出 -1。

解题思路

注意到 \(\sum\limits_{i=1}^N B_i \le 1500\)，即 \(\frac{1}{3}\sum\limits_{i=1}^N B_i \le 500\)，考虑 \(dp[i][x][y]\) 表示前 \(i\) 个人分配完毕后，第一支队伍的力量值之和为 \(x\)，第二支队伍的力量值之和为 \(y\) 的所有方案中操作次数的最小值。转移的时候根据背包 \(dp\) 转移就好。

下面的代码我用了哈希表只存了有效的状态，实际没有必要，直接数组就好。

参考代码

C++

#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

const int P = 501;

int make_key(int x, int y) {return y * P + x;}
pair<int, int> get_xy(int key) {return {key % P, key / P};}

void update(unordered_map<int, int> *mp, int x, int y, int cnt)
{
    int key = make_key(x, y);
    auto it = mp->find(key);
    if (it == mp->end())
        mp->insert({key, cnt});
    else
        it->second = min(it->second, cnt);
}

int main()
{
    int n, target = 0;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
        target += b[i];
    }
    if (target % 3 != 0)
    {
        cout << "-1" << endl;
        return 0;
    }
    target /= 3;
    int sum = 0;
    unordered_map<int, int> dp[2], *now = &dp[0], *pre = &dp[1];
    now->insert({0, 0});
    for (int i = 0; i < n; i++)
    {
        swap(now, pre);
        now->clear();
        sum += b[i];
        for (auto [key, cnt]: *pre)
        {
            const auto [x, y] = get_xy(key);
            if (x + b[i] <= target)
                update(now, x + b[i], y, cnt + (a[i] != 1));
            if (y + b[i] <= target)
                update(now, x, y + b[i], cnt + (a[i] != 2));
            if (sum - x - y <= target)
                update(now, x, y, cnt + (a[i] != 3));
        }
    }
    auto it = now->find(make_key(target, target));
    cout << (it == now->end() ? -1 : it->second);
    return 0;
}

---

F - Road Blocked

题目大意

初始的时候，给你一个 \(N(2 \le N \le 300)\) 个点， \(M(0 \le M \le \frac{N(N-1)}{2})\) 条边的无向有权图。

接下来，你需要处理 \(Q(2 \times 10 ^ 5)\) 个询问，每一种询问有两种类型：

• 1 x 表示删除第 \(i\) 条边。
• 2 x y 表示查询点 \(x\) 到点 \(y\) 的最短路长度。如果不可达输出 -1

保证第一种操作至多出现 \(300\) 次。

解题思路

考虑离线处理，先用至始至终没被删过的边跑一边 Floyed，然后从最后一个询问开始，对于第二种操作就能 \(O(1)\) 回答。

考虑第一种操作如何处理，删除边就相当于加边，加边之后需要更新最短路的矩阵，设 \(dis[u][v]\) 表示 \(u\) 到 \(v\) 的最短路，边为 \((a, b)\)，则再加边之后，\(u\) 到 \(v\) 的最短路有以下情况：

• 不走边 \((a, b)\)，则仍然是 \(dis[u][v]\)
• \(u \rightarrow a \rightarrow b \rightarrow v\)，即 \(dis[u][a] + w(a, b) + dis[b][v]\)
• \(u \rightarrow b \rightarrow a \rightarrow v\)，即 \(dis[u][b] + w(a, b) + dis[a][v]\)

取最小值更新就好，这样每次更新的时间复杂度是 \(O(N^2)\)，又因为第一种操作至多 \(300\) 次，所以能过。

参考代码

C++

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

using namespace std;
using LL = long long;

const LL INF = numeric_limits<LL>::max() / 4;

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(m), b(m), c(m);
    vector<bool> del(m);
    for (int i = 0; i < m; i++)
        cin >> a[i] >> b[i] >> c[i];
    vector<LL> ans(q, -1);
    vector<vector<int>> querys(q);
    for (int i = 0; i < q; i++)
    {
        int op, x, y;
        cin >> op >> x;
        if (op == 1)
        {
            x--;
            querys[i] = {op, x};
            del[x] = true;
        }
        else
        {
            cin >> y;
            querys[i] = {op, x, y};
        }
    }
    vector<vector<LL>> dis(n + 1, vector<LL>(n + 1, INF));
    for (int u = 1; u <= n; u++)
        dis[u][u] = 0;
    for (int i = 0; i < m; i++)
        if (!del[i])
            dis[a[i]][b[i]] = dis[b[i]][a[i]] = c[i];
    for (int k = 1; k <= n; k++)
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++)
                dis[u][v] = min(dis[u][v], dis[u][k] + dis[k][v]);
    for (int i = q - 1; i >= 0; i--)
    {
        if (querys[i][0] == 2)
        {
            int x = querys[i][1], y = querys[i][2];
            ans[i] = dis[x][y] >= INF ? -1 : dis[x][y];
        }
        else
        {
            int idx = querys[i][1];
            for (int u = 1; u <= n; u++)
                for (int v = 1; v <= n; v++)
                    dis[u][v] = min({dis[u][v], dis[u][a[idx]] + c[idx] + dis[b[idx]][v], dis[u][b[idx]] + c[idx] + dis[a[idx]][v]});
        }
    }
    for (int i = 0; i < q; i++)
        if (querys[i][0] == 2)
            cout << ans[i] << '\n';
    return 0;
}

---

G - Road Blocked 2

题目大意

给你一个 \(N(2 \times 10 ^ 5)\) 个点，\(M(1 \le M \le 2 \times 10 ^ 5)\) 条边的无向有权图。

对于 \(i = 1, 2, ..., M\)，判断下面两个值是否相等：

• 点 \(1\) 到 点 \(N\) 的最短路长度。

• 在仅仅删掉第 \(i\) 条边的情况下，点 \(1\) 到点 \(N\) 的最短路长度。

如果这两个值相等输出 Yes，否则输出 No。

解题思路

首先以点 \(1\) 为起点跑最短路，如果 \(1\) 到 \(n\) 不可达，那么所有的答案都是 Yes。

然后以点 \(n\) 为起点跑一遍最短路，这样可以得到两个数组 \(dis_1\) 和 \(dis_n\)，我们需要构成一个子图，子图的边是能够成为 \(1\) 到 \(n\) 的最短路边，对于一条边 \((a, b)\)，如果这条边是最短路，要么是 \(1 \rightarrow a \rightarrow b \rightarrow n\)，要么是 \(1 \rightarrow b \rightarrow a \rightarrow n\)，所以判别条件就是 \(dis_1[a] + w(a, b) + dis_n[b] = dis_1[n]\)，或者 \(dis_1[b] + w(a, b) + dis_n[a] = dis_1[n]\)。

构建完子图之后，在子图上跑 tarjan 找割边即可。如果一条边出现在子图的割边中，则一定删去这条边一定会导致最短路长度发生变化。

参考代码

C++

#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <unordered_set>
#include <vector>

using namespace std;
using LL = long long;

const LL INF = numeric_limits<LL>::max() / 2;

struct Graph
{
    struct Edge
    {
        int to, w;
    };

    int n;
    vector<vector<Edge>> edge;

    Graph(int n) : n(n), edge(n + 1) {}

    void add_edge(int u, int v, int w)
    {
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }

    vector<LL> dijkstra(int s)
    {
        struct Node
        {
            int u;
            LL dis;
            bool operator>(const Node &other) const { return dis > other.dis; }
        };

        vector<LL> dis(n + 1, INF);
        dis[s] = 0;
        priority_queue<Node, vector<Node>, greater<Node>> heap;
        heap.push({s, 0});
        while (!heap.empty())
        {
            auto [u, d] = heap.top();
            heap.pop();
            if (d > dis[u])
                continue;
            for (auto e : edge[u])
            {
                int v = e.to;
                LL nd = d + e.w;
                if (nd < dis[v])
                {
                    dis[v] = nd;
                    heap.push({v, nd});
                }
            }
        }
        return dis;
    }
};

struct SubGraph
{
    struct Edge
    {
        int to, rev_idx;
        size_t edge_idx;
    };

    int n, ti = 1;
    vector<vector<Edge>> edge;
    vector<int> dfn, low;

    SubGraph(int n) : n(n), edge(n + 1), dfn(n + 1), low(n + 1) {}

    void add_edge(int u, int v, size_t idx)
    {
        int ui = edge[u].size();
        int vi = edge[v].size();
        edge[u].push_back({v, vi, idx});
        edge[v].push_back({u, ui, idx});
    }

    void tarjan(unordered_set<int> &bridge, int u, size_t rev_idx)
    {
        dfn[u] = low[u] = ti++;
        for (size_t i = 0; i < edge[u].size(); i++)
        {
            if (i == rev_idx)
                continue;
            Edge &e = edge[u][i];
            int v = e.to;
            if (!dfn[v])
            {
                tarjan(bridge, v, e.rev_idx);
                low[u] = min(low[u], low[v]);
            }
            else
                low[u] = min(low[u], dfn[v]);
            if (low[v] > dfn[u])
                bridge.insert(e.edge_idx);
        }
    }

    unordered_set<int> find_bridge()
    {
        unordered_set<int> bridge;
        tarjan(bridge, 1, -1);
        return bridge;
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m), c(m);
    Graph g(n);
    SubGraph sub(n);
    for (int i = 0; i < m; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        g.add_edge(a[i], b[i], c[i]);
    }
    vector<LL> dis1 = g.dijkstra(1);
    vector<LL> disn = g.dijkstra(n);
    for (int i = 0; i < m; i++)
    {
        int u = a[i], v = b[i], w = c[i];
        if (dis1[u] + w + disn[v] == dis1[n] || dis1[v] + w + disn[u] == dis1[n])
            sub.add_edge(u, v, i);
    }
    unordered_set<int> bridge = sub.find_bridge();
    for (int i = 0; i < m; i++)
        cout << (bridge.count(i) ? "Yes" : "No") << '\n';
    return 0;
}

---

---

最后更新: 2024-12-19
创建日期: 2024-12-19