「HCOI-R1」孤独的 sxz 题解

robinyqc · 2023-12-24 21:52:16 · 题解

几个挺有意思的解法。

题意简述

给定一个 n\times m 的表格，上面有 k 个格子被涂黑了。求一个白色格子，到所有黑色格子的曼哈顿距离之和最大。n, m\leq 10^9, k\leq 4\times 10^5。

主要思路

若没有 n, m 的限制，答案是无限大的，选一个特别远的点即可。所以自然地想到，加上 n, m 的限制，应当尽量选边角上的点。

为啥呢？不妨先钦定选择的点在第 x 行。那么纵坐标的贡献对这一行都是相等的。那么问题变成一维的，数轴上若干个点，离他们距离和最远的点，要么是最右的点，要么是最左的点，这个很显然。所以对于每一行，答案要么是最左边那个白点，要么是最右边那个白点。对列可以类似地分析。我们称这种最左/右的点为关键点。

解法一

直接暴力做即可，复杂度 O(k\sqrt k)。

枚举行，若这一行最左边的白点比前面所有行最左边的白点都更左，那么它有可能成为答案。求出一行最左边的点可以 O(l\log k)，其中 l 是最左边的点的横坐标。所以求出所有行有贡献最左边点的复杂度为 O(\log k\sum l) = O(k\log k)。也可以这么理解：每个黑点最多只被遍历一次，所以总复杂度 O(k\log k)。

注意到，一个横坐标为 x 的关键点，前面一定有 x - 1 个黑点作为支撑。并且按行看，没有横坐标相同的靠左的关键点。由于 1 + 2 + 3 + \dots + n = O(n^2)，且 \sum_{p\in \{\text{关键点}\}} p_x \leq k，极端情况下，p_x 就是 1..n 的形式。所以关键点的个数是 O(\sqrt k) 级别的。

这是个很经典的结论。例题：喵星球上的点名。

所以直接暴力 O(k) 计算每个关键点的答案即可。总复杂度 O(k\log k + k\sqrt k) = O(k\sqrt k)，思路极简单，代码也好写。

下面是两段比较关键的代码。

• 找出一行靠左的关键点：

  pair<int, int> find_p(int x)
  {
     for (int i = 0; i < m; i++) {
         pair<int, int> s(x + d1 * i, y + d2 * i);
         // 如果发现 s 不在黑点集合中，返回 s。
         if (!binary_search(o + 1, o + 1 + k, s)) {
             return s;
         }
     }
     return {x, m + 1};
  }

• 统计可能成为答案的点：

  int bf = m + 1; // 之前行最左边的点的横坐标。
  for (int i = 1, bf = m + 1; i <= n; i++) {
     auto x = find_p(i);
     if (x.second < bf) {
         // 将 x 加入可能成为关键点集中。
         qr.push_back(x);
         bf = x.second;
     }
     // 若 bf <= 1 那么显然不会有更左的点了，
     // 直接退出循环，否则复杂度显然是错误的。
     if (bf <= 1) break;
  }

  对于其它方向（总共八个方向）都可以类似地求。

这个做法复杂度比较高，不过出题人没有卡。我造了组极限数据，这种做法要跑 900 ms，也确实能过。

解法二