题解：B3701 [语言月赛202301] 避雷针

残阳如血 · 2024-06-08 21:08:29 · 题解

\textbf{Solution}

\textbf{F}_{\textbf{1}}

观察 n 的范围，由于 1\le n\le10^6，足以开下一个完整的数组，所以可以直接进行模拟。

对于每一个输入的 a，枚举 \max\{a-2,1\}\sim\min\{a+2,n\}，这样就不会越界了。可以开一个计数数组 \rm cnt，\rm cnt_i 表示 i 位置被劈中的次数。

最后遍历整个数组，统计即可。

时间复杂度 O(n+m)，空间复杂度 O(n)，可以通过本题。

\textbf{F}_{\textbf{2}}

考虑一种情况，当 n 的范围非常大，以至于无法开一个数组记录时，应该如何解决呢？

首先，我们要使得时空复杂度与 n 无关。对于每一个 a，影响的位置只有 5 个，开一个数组记录的话很大一部分空间都被浪费了。

所以，我们只需要存储被劈过的位置，并且为了方便去重，并且使得时间复杂度较低，可以使用哈希表存储被劈过的位置。

\textbf{Code}

\textbf{F}_{\textbf{1}}

#include <iostream>
const int MAX = 1e6 + 10;

int n, m, ans, t[MAX];
// t 为计数数组

int main() {
  std::cin >> n >> m;
  for (int i = 0, a; i < m; ++i) {
    std::cin >> a;
    for (int j = std::max(a - 2, 1); j <= std::min(a + 2, n); ++j) ++t[j];
    // 枚举
  }
  for (int i = 1; i <= n; ++i) ans += t[i] >= 1;
  // 统计最终结果
  std::cout << ans << std::endl;
  return 0;
}

\textbf{F}_{\textbf{2}}

#include <iostream>
#include <unordered_set> // 使用哈希表的头文件
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

int n, m;
std::unordered_set<int> set;

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cin >> n >> m;
    for (int a; m; --m) {
        std::cin >> a;
        for (int i = max(1, a - 2); i <= min(a + 2, n); ++i) set.insert(i);
      // 枚举并插入哈希表
    }
  // 由于哈希表自动去重，所以哈希表的大小就是最终结果
    std::cout << set.size() << std::endl;
    return 0;
}