当前位置：首页 > news >正文

【第十六届蓝桥杯省 C/Python A/Java C 登山】题解

news 来源：原创 2025/7/23 2:08:12

题目链接：P12169 [蓝桥杯 2025 省 C/Python A/Java C] 登山

思路来源

一开始想的其实是记搜，但是发现还有先找更小的再找更大的这种路径，所以这样可能错过某些最优决策，这样不行。

于是我又想能不能从最大值出发往回搜，手玩了一下发现其实和记搜没什么区别，无非是把边给反向了。

那可能的做法就是强连通分量？我当时板子都掏出来了，但是模拟了一番之后就发现可以用并查集。

下面是正文。

算法：并查集

由于行列是同一套逻辑，所以下面只说同一列内的行操作，同一行内的列操作直接照抄即可。

设现在我们在 $(x, y)$ ，且存在点 $(i, y)$ 满足 $i > x$ 且 $a_{i, y} < a_{x, y}$ ，那么我们可以从 $(x, y)$ 向 $(i, y)$ 连边表示 $(x, y)$ 可达 $(i, y)$ 。

那么同理，如果我们在 $(i, y)$ ，根据题中所说， $(x, y)$ 满足 $x < i$ 且 $a_{x, y} > a_{i, y}$ ，同样可以从 $(i, y)$ 向 $(x, y)$ 连边。

也就是说，只要存在一个逆序对，就有一对 双向边！

但是直接 $O(n^2)$ 遍历 $O (m)$ 次来连边有点太狂野了，这复杂度也过不去，所以我们开始寻找逆序对连边的等价命题。

先给出命题：

对于第 $j$ 列，设 $p re [i]$ 表示前 $i$ 个元素的最大值， $s u f [i]$ 表示 $[i, n]$ 内元素的最小值，如果 $p re [i] > s u f [i + 1]$ ，就连一条 $(i, j)$ 到 $(i + 1, j)$ 的边。

为了方便，做几点说明。

逆序对连边生成的边集为 $E_0$ ，相邻连边生成的边集为 $E_1$ ；
简写 $(l, j)$ 到 $(r, j)$ 连双向边为 $\Longleftrightarrow r$ 。

下面证明二者等价。

若有 $a_{l, j} > a_{r, j}$ ，那么有 $\Longleftrightarrow r$ ，那么对于 $\in [l, r)$ ，一定有 $p re [i] > s u f [i + 1]$ ，那也就是说， $E_1$ 会包含 $\Longleftrightarrow l + 1, \ \ l + 1 \Longleftrightarrow l + 2, \ \ \cdots, \ \ r - 1 \Longleftrightarrow r$ ，这相当于包含了一条 $\Longleftrightarrow r$ 的双向边，所以 $E_0 \subseteq E_1$ 。

若有 $p re [i] > s u f [i + 1]$ ，那么有 $\Longleftrightarrow i + 1$ ，同时，由前缀最大和后缀最小的性质可以得到，必然存在 $\in [1, i]$ 和 $\in (i, n]$ ，使得 $a_{l, j} > a_{r, j}$ ，那么首先就有 $\Longleftrightarrow r$ 。如果 $l < i$ ，说明 $a_{l, j} > a_{i, j}$ ，那么由题目条件有 $\Longleftrightarrow i$ ，同理如果 $i + 1 < r$ ，那么 $\Longleftrightarrow r$ ，将这三条边合起来，就包含了一条 $\Longleftrightarrow i + 1$ 的双向边，所以 $E_1 \subseteq E_0$ 。

综上， $E_0 = E_1$ ，二者等价。

设我们这样得到了 $N$ 个连通块，第 $i$ 个连通块的大小为 $siz_i$ ，其块内最大值为 $max_i$ ，则最终答案为

$\sum\limits_{i = 1}^{N}siz_i \times max_i.$

时间复杂度 $O(\rm{nm \cdot \alpha(nm)})$

其中 $\rm{\alpha(nm)}$ 是反阿克曼函数，一般可以看作 $3, 4$ 左右的常数。

C++ Code

#include <bits/stdc++.h>using i64 = long long;struct DSU {std::vector<int> f, sz;DSU() {}DSU(int n) {init(n);}void init(int n) {f.resize(n);std::iota(f.begin(), f.end(), 0);sz.assign(n, 1);}int find(int x) {while (x != f[x]) {x = f[x] = f[f[x]];}return x;}int size(int x) {return sz[find(x)];}bool merge(int x, int y) {x = find(x);y = find(y);if (x == y) {return false;}sz[x] += sz[y];f[y] = x;return true;}bool same(int x, int y) {return find(x) == find(y);}
};template<class T>
void chmax(T &a, T b) {if (a < b) {a = b;}
}
constexpr int inf = std::numeric_limits<int>::max() / 2;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(6);int n, m;std::cin >> n >> m;const int N = n * m;std::vector<int> a(N);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {std::cin >> a[i * m + j];}}DSU dsu(N);for (int i = 0; i < n; i++) {std::vector pre(m + 1, 0);std::vector suf(m + 1, inf);for (int j = 0; j < m; j++) {pre[j + 1] = std::max(pre[j], a[i * m + j]);}for (int j = m - 1; j >= 0; j--) {suf[j] = std::min(suf[j + 1], a[i * m + j]);}for (int j = 1; j < m; j++) {if (pre[j] > suf[j]) {dsu.merge(i * m + (j - 1), i * m + j);}}}for (int j = 0; j < m; j++) {std::vector pre(n + 1, 0);std::vector suf(n + 1, inf);for (int i = 0; i < n; i++) {pre[i + 1] = std::max(pre[i], a[i * m + j]);}for (int i = n - 1; i >= 0; i--) {suf[i] = std::min(suf[i + 1], a[i * m + j]);}for (int i = 1; i < n; i++) {if (pre[i] > suf[i]) {dsu.merge((i - 1) * m + j, i * m + j);}}}std::vector max(N, 0);for (int i = 0; i < N; i++) {chmax(max[dsu.find(i)], a[i]);}i64 ans = 0;for (int i = 0; i < N; i++) {if (dsu.find(i) == i) {ans += 1LL * dsu.size(i) * max[i];}}std::cout << 1.* ans / n / m << "\n";return 0;
}

题目链接：P12169 [蓝桥杯 2025 省 C/Python A/Java C] 登山

思路来源

算法：并查集

时间复杂度 O ( n m ⋅ α ( n m ) ) O(\rm{nm \cdot \alpha(nm)}) O(nm⋅α(nm))

C++ Code

相关文章：

时间复杂度 $O(\rm{nm \cdot \alpha(nm)})$