The 2023 ICPC Asia Hefei Regional Contest (The 2nd Universal Cup. Stage 12: Hefei) (opens new window)

E - Matrix Distances

Question

有一个大小为 $n \times m$ 的矩阵，每个单元格填充了颜色值 $c_{i,j}$。计算所有具有相同颜色的单元格对之间曼哈顿距离的总和。

具体而言，请计算：

$\text{Total Sum} = \sum_C \sum_{(x_i, y_i) \in S_C} \sum_{(x_j, y_j)\in S_C} \left|x_i-x_j\right|+\left|y_i-y_j\right|$

这里，$C$ 表示所有不同颜色的集合。$S_C$ 表示颜色等于指定颜色 $C$ 的坐标集合 $(x, y)$。

Solution

很显然，需要一个一个颜色计算，对于一个颜色 $c$ 发现 $x,y$ 对答案的贡献是独立的，所以可以拆开来计算

考虑如何计算 $x$ 对答案的贡献

先将 $x$ 从小到大排序，计算前缀和数组 $s$，当枚举到一个 $x_i$，有 $i-1$ 个 $x$ 比当前的 $x$ 小，对答案的贡献就是 $x_i\times i-s_i$，同时，有 $m-i$ 个 $x$ 比当前的 $x_i$ 大，对答案的贡献就是 $s_i-x_i\times(m-i)$，其中 $m$ 表示当前颜色方块的个数

$y$ 和 $x$ 的计算方法相同

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    vector<int> b;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            b.push_back(a[i][j]);
        }
    }
    sort(b.begin(), b.end());
    int cnt = unique(b.begin(), b.end()) - b.begin();
    vector<vector<int>> X(cnt + 1), Y(cnt + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = lower_bound(b.begin(), b.begin() + cnt, a[i][j]) - b.begin() + 1;
            X[a[i][j]].push_back(i);
            Y[a[i][j]].push_back(j);
        }
    }
    long long ans = 0;
    auto calc = [&] (vector<int>& v) {
        int n = v.size();
        if (n == 0) return 0ll;
        vector<long long> sum(n);
        sort(v.begin(), v.end());
        sum[0] = v[0];
        for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + v[i];
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            ret += 1ll * v[i] * (i + 1) - sum[i];
            ret += sum[n - 1] - sum[i] - 1ll * v[i] * (n - (i + 1));
        }
        return ret;
    };

    for (auto v : X) ans += calc(v);
    for (auto v : Y) ans += calc(v);
    cout << ans << '\n';
    return 0;
}

F - Colorful Balloons

Solution

签到题

Code

#include<bits/stdc++.h>
using namespace std;
int n, mx;
string s, ans;
map<string, int> mp;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> s;
        mp[s] ++;
        if(mx < mp[s]){
            mx = mp[s];
            ans = s;
        }
    }
    if(mx > n / 2) cout << ans << endl;
    else cout << "uh-oh" << endl;
    return 0;
}

G - Streak Manipulation

Question

给定一个 01 串，长度为 $n$，最多可以操作 $m$ 次，每次操作把一个 $0$ 变成 $1$，求不超过 $m$ 次操作后，第 $k$ 长的连续为 $1$ 的串的长度

Solution

考虑二分答案 $mid$，即在最多 $m$ 次操作之后，第 $k$ 长的串的大小为 $mid$

考虑如何 check，注意到 $k$ 其实很小，可以被定义到动态规划的状态里面去

定义 $dp[i][j][0/1]$ 表示：前 $i$ 个字符，有 $j$ 段长度大于等于 $mid$ 的连续 $1$ 串，且当前字符是否位于第 $j$ 段连续 $1$ 串的末尾，所需的最少操作次数

考虑状态转移

• $s[i]=0$
  • $dp[i][j][0]=\min(dp[i][j][0],dp[i-1][j][0],dp[i-1][j][1])$
  • $dp[i][j][1]=\min(dp[i][j][1],dp[i-1][j][1]+1)$
• $s[i]=1$
  • $dp[i][j][0]=\min(dp[i][j][0],dp[i][j][0])$
  • $dp[i][j][1]=\min(dp[i][j][1],dp[i-1][j][1])$
• 此外，在 $i\ge mid$ 且 $j>0$ 时
  • $dp[i][j][1]=\min(dp[i][j][1],dp[i-mid][j-1][0]+\sum_{k=i-mid+1}^i [s[k]=0])$

其中，$\sum_{k=i-mid+1}^i [s[k]=0]$ 可以用前缀和数组快速求出

总时间复杂度为 $O(kn\log n)$

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 5;
int dp[MAXN][6][2];

int main() {
    ios::sync_with_stdio(false);
    int n, m, k; cin >> n >> m >> k;
    string s; cin >> s; s = " " + s;
    vector<int> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) 
        pre[i] = pre[i - 1] + (s[i] == '0');
    
    int l = 0, r = n + 1;

    auto check = [&] (int x) {
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= k; j++)
                dp[i][j][0] = dp[i][j][1] = INF;

        dp[0][0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= k; j++) {
                if (s[i] == '0') {
                    dp[i][j][0] = min({dp[i][j][0], dp[i - 1][j][0], dp[i - 1][j][1]});
                    dp[i][j][1] = min({dp[i][j][1], dp[i - 1][j][1] + 1});
                }
                else {
                    dp[i][j][0] = min({dp[i][j][0], dp[i - 1][j][0]});
                    dp[i][j][1] = min({dp[i][j][1], dp[i - 1][j][1]});
                }
                if (i >= x && j > 0) 
                    dp[i][j][1] = min({dp[i][j][1], dp[i - x][j - 1][0] + pre[i] - pre[i - x]});
            }
        return min(dp[n][k][0], dp[n][k][1]) <= m;
    };

    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (check (mid)) l = mid;
        else r = mid;
    }
    if (l <= 0) cout << -1 << '\n';
    else cout << l << '\n';
    return 0;
}

J - Takeout Delivering

Question

给你一个无向连通图，定义最短路为路径中边权最大的两条边的边权和，求 $1$ 到 $n$ 的最短路

• $2\le n\le 3\times 10^5,m\le 10^6$

Solution

当时考虑了很久二分，后来发现方向错了

我们需要求一条路径上的路径最大值和次大值的和

那么我们枚举每一条边，假设这条边就是路径上的最大值，那么次大值就应该出现在从 $1\sim u,v\sim n$ 或者 $1\sim v,u\sim n$

提前用 dijkstra 提前预处理出 $1\sim x$ 的最小路径最大值，同理也能处理出 $x\sim n$ 的最小路径最大值

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;
int main() {
    freopen ("J.in", "r", stdin);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    auto dijkstra = [&] (int s) {
        vector<int> dis(n + 1, INF);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> vis(n + 1, 0);
        dis[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto [v, w] : g[u]) {
                int tmp = max(dis[u], w);
                if (tmp < dis[v]) {
                    dis[v] = tmp;
                    pq.push({dis[v], v});
                }
            }
        }
        return dis;
    };

    auto dis1 = dijkstra(1);
    auto disn = dijkstra(n);

    int ans = INF + INF;
    
    for (int u = 1; u <= n; u++) {
        for (auto [v, w] : g[u]) {
            if (w >= max(dis1[u], disn[v]))
                ans = min(ans, max(dis1[u], disn[v]) + w);
            if (w >= max(dis1[v], disn[u]))
                ans = min(ans, max(dis1[v], disn[u]) + w);
        }
    }
    cout << ans << '\n';
    return 0;
}

summary

对于这种需要维护一个最大值和一个次大值

1. 考虑开一个 pair<int,int> 或者什么结构，使用最大值和次大值只增不减的特性
2. 考虑二分其中一个
3. 考虑枚举其中一个，看能否快速求出另外一个