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

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

思绪泉源

一开始想的着实是记搜，但是发现尚有先找更小的再找更大的这种路径，以是如许大概错过某些最优决议，如许不可。
于是我又想能不能从最大值出发往回搜，手玩了一下发现着实和记搜没什么区别，无非是把边给反向了。
那大概的做法就是强连通分量？我其时板子都掏出来了，但是模仿了一番之后就发现可以用并查集。
下面是正文。
算法：并查集

由于行列是同一套逻辑，以是下面只说同一列内的行操纵，同一行内的列操纵直接照抄即可。
设现在我们在                               (                      x                      ,                      y                      )                          (x, y)               (x,y)，且存在点                               (                      i                      ,                      y                      )                          (i, y)               (i,y) 满足                               i                      >                      x                          i > x               i>x 且                                        a                                   i                            ,                            y                                       <                               a                                   x                            ,                            y                                           a_{i, y} < a_{x, y}               ai,y​<ax,y​，那么我们可以从                               (                      x                      ,                      y                      )                          (x, y)               (x,y) 向                               (                      i                      ,                      y                      )                          (i, y)               (i,y) 连边表现                               (                      x                      ,                      y                      )                          (x, y)               (x,y) 可达                               (                      i                      ,                      y                      )                          (i, y)               (i,y)。
那么同理，假如我们在                               (                      i                      ,                      y                      )                          (i, y)               (i,y)，根据题中所说，                              (                      x                      ,                      y                      )                          (x, y)               (x,y) 满足                               x                      <                      i                          x < i               x<i 且                                        a                                   x                            ,                            y                                       >                               a                                   i                            ,                            y                                           a_{x, y} > a_{i, y}               ax,y​>ai,y​，同样可以从                               (                      i                      ,                      y                      )                          (i, y)               (i,y) 向                               (                      x                      ,                      y                      )                          (x, y)               (x,y) 连边。
也就是说，只要存在一个逆序对，就有一对 双向边！
但是直接                               O                      (                               n                         2                              )                          O(n^2)               O(n2) 遍历                               O                      (                      m                      )                          O(m)               O(m) 次来连边有点太狂野了，这复杂度也过不去，以是我们开始探求逆序对连边的等价命题。
先给出命题：
对于第                                    j                              j                  j 列，设                                    p                         r                         e                         [                         i                         ]                              pre                  pre 表现前                                    i                              i                  i 个元素的最大值，                                   s                         u                         f                         [                         i                         ]                              suf                  suf 表现                                    [                         i                         ,                         n                         ]                              [i, n]                  [i,n] 内元素的最小值，假如                                    p                         r                         e                         [                         i                         ]                         >                         s                         u                         f                         [                         i                         +                         1                         ]                              pre > suf[i + 1]                  pre>suf[i+1]，就连一条                                    (                         i                         ,                         j                         )                              (i, j)                  (i,j) 到                                    (                         i                         +                         1                         ,                         j                         )                              (i + 1, j)                  (i+1,j) 的边。
为了方便，做几点阐明。

• 逆序对连边天生的边集为                                              E                            0                                       E_0                  E0​，相邻连边天生的边集为                                              E                            1                                       E_1                  E1​；
  
• 简写                                    (                         l                         ,                         j                         )                              (l, j)                  (l,j) 到                                    (                         r                         ,                         j                         )                              (r, j)                  (r,j) 连双向边为                                    l                         ⟺                         r                              l \Longleftrightarrow r                  l⟺r。
  

下面证明二者等价。
如有                                        a                                   l                            ,                            j                                       >                               a                                   r                            ,                            j                                           a_{l, j} > a_{r, j}               al,j​>ar,j​，那么有                               l                      ⟺                      r                          l \Longleftrightarrow r               l⟺r，那么对于                               i                      ∈                      [                      l                      ,                      r                      )                          i \in [l, r)               i∈[l,r)，肯定有                               p                      r                      e                      [                      i                      ]                      >                      s                      u                      f                      [                      i                      +                      1                      ]                          pre > suf[i + 1]               pre>suf[i+1]，那也就是说，                                       E                         1                                  E_1               E1​ 会包罗                               l                      ⟺                      l                      +                      1                      ,                                              l                      +                      1                      ⟺                      l                      +                      2                      ,                                              ⋯                       ,                                              r                      −                      1                      ⟺                      r                          l \Longleftrightarrow l + 1, \ \ l + 1 \Longleftrightarrow l + 2, \ \ \cdots, \ \ r - 1 \Longleftrightarrow r               l⟺l+1,  l+1⟺l+2,  ⋯,  r−1⟺r，这相当于包罗了一条                               l                      ⟺                      r                          l \Longleftrightarrow r               l⟺r 的双向边，以是                                        E                         0                              ⊆                               E                         1                                  E_0 \subseteq E_1               E0​⊆E1​。
如有                               p                      r                      e                      [                      i                      ]                      >                      s                      u                      f                      [                      i                      +                      1                      ]                          pre > suf[i + 1]               pre>suf[i+1]，那么有                               i                      ⟺                      i                      +                      1                          i \Longleftrightarrow i + 1               i⟺i+1，同时，由前缀最大和后缀最小的性子可以得到，一定存在                               l                      ∈                      [                      1                      ,                      i                      ]                          l \in [1, i]               l∈[1,i] 和                               r                      ∈                      (                      i                      ,                      n                      ]                          r \in (i, n]               r∈(i,n]，使得                                        a                                   l                            ,                            j                                       >                               a                                   r                            ,                            j                                           a_{l, j} > a_{r, j}               al,j​>ar,j​，那么起首就有                               l                      ⟺                      r                          l \Longleftrightarrow r               l⟺r。假如                               l                      <                      i                          l < i               l<i，阐明                                        a                                   l                            ,                            j                                       >                               a                                   i                            ,                            j                                           a_{l, j} > a_{i, j}               al,j​>ai,j​，那么由标题条件有                               l                      ⟺                      i                          l \Longleftrightarrow i               l⟺i，同理假如                               i                      +                      1                      <                      r                          i + 1 < r               i+1<r，那么                               i                      +                      1                      ⟺                      r                          i + 1 \Longleftrightarrow r               i+1⟺r，将这三条边合起来，就包罗了一条                               i                      ⟺                      i                      +                      1                          i \Longleftrightarrow i + 1               i⟺i+1 的双向边，以是                                        E                         1                              ⊆                               E                         0                                  E_1 \subseteq E_0               E1​⊆E0​。
综上，                                       E                         0                              =                               E                         1                                  E_0 = E_1               E0​=E1​，二者等价。
设我们如许得到了                               N                          N               N 个连通块，第                               i                          i               i 个连通块的巨细为                               s                      i                               z                         i                                  siz_i               sizi​，其块内最大值为                                                  max                            ⁡                                  i                                  \max_i               maxi​，则终极答案为
                                              ∑                                       i                               =                               1                                      N                                  s                         i                                   z                            i                                  ×                         m                         a                                   x                            i                                  .                               \sum\limits_{i = 1}^{N}siz_i \times max_i.                   i=1∑N​sizi​×maxi​.
时间复杂度                               O                      (                                         n                            m                            ⋅                            α                            (                            n                            m                            )                                  )                                  O(\rm{nm \cdot \alpha(nm)})               O(nm⋅α(nm))

• 此中                                    α                         (                         n                         m                         )                              \rm{\alpha(nm)}                  α(nm) 是反阿克曼函数，一样平常可以看作                                    3                         ,                         4                              3, 4                  3,4 左右的常数。
  

C++ Code

1. #include <bits/stdc++.h>
3. using i64 = long long;
5. struct DSU {
6.     std::vector<int> f, sz;
7.     DSU() {}
8.     DSU(int n) {
9.         init(n);
10.     }
11.     void init(int n) {
12.         f.resize(n);
13.         std::iota(f.begin(), f.end(), 0);
14.         sz.assign(n, 1);
15.     }
16.     int find(int x) {
17.         while (x != f[x]) {
18.             x = f[x] = f[f[x]];
19.         }
20.         return x;
21.     }
22.     int size(int x) {
23.         return sz[find(x)];
24.     }
25.     bool merge(int x, int y) {
26.         x = find(x);
27.         y = find(y);
28.         if (x == y) {
29.             return false;
30.         }
31.         sz[x] += sz[y];
32.         f[y] = x;
33.         return true;
34.     }
35.     bool same(int x, int y) {
36.         return find(x) == find(y);
37.     }
38. };
40. template<class T>
41. void chmax(T &a, T b) {
42.     if (a < b) {
43.         a = b;
44.     }
45. }
46. constexpr int inf = std::numeric_limits<int>::max() / 2;
48. int main() {
49.     std::ios::sync_with_stdio(false);
50.     std::cin.tie(nullptr);
52.     std::cout << std::fixed << std::setprecision(6);
53.    
54.     int n, m;
55.     std::cin >> n >> m;
57.     const int N = n * m;
59.     std::vector<int> a(N);
60.     for (int i = 0; i < n; i++) {
61.         for (int j = 0; j < m; j++) {
62.             std::cin >> a[i * m + j];
63.         }
64.     }
66.     DSU dsu(N);
67.     for (int i = 0; i < n; i++) {
68.         std::vector pre(m + 1, 0);
69.         std::vector suf(m + 1, inf);
70.         for (int j = 0; j < m; j++) {
71.             pre[j + 1] = std::max(pre[j], a[i * m + j]);
72.         }
73.         for (int j = m - 1; j >= 0; j--) {
74.             suf[j] = std::min(suf[j + 1], a[i * m + j]);
75.         }
76.         for (int j = 1; j < m; j++) {
77.             if (pre[j] > suf[j]) {
78.                 dsu.merge(i * m + (j - 1), i * m + j);
79.             }
80.         }
81.     }
82.     for (int j = 0; j < m; j++) {
83.         std::vector pre(n + 1, 0);
84.         std::vector suf(n + 1, inf);
85.         for (int i = 0; i < n; i++) {
86.             pre[i + 1] = std::max(pre[i], a[i * m + j]);
87.         }
88.         for (int i = n - 1; i >= 0; i--) {
89.             suf[i] = std::min(suf[i + 1], a[i * m + j]);
90.         }
91.         for (int i = 1; i < n; i++) {
92.             if (pre[i] > suf[i]) {
93.                 dsu.merge((i - 1) * m + j, i * m + j);
94.             }
95.         }
96.     }
98.     std::vector max(N, 0);
99.     for (int i = 0; i < N; i++) {
100.         chmax(max[dsu.find(i)], a[i]);
101.     }
102.     i64 ans = 0;
103.     for (int i = 0; i < N; i++) {
104.         if (dsu.find(i) == i) {
105.             ans += 1LL * dsu.size(i) * max[i];
106.         }
107.     }
108.     std::cout << 1.* ans / n / m << "\n";
109.    
110.     return 0;
111. }

复制代码