Solution

F1

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

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

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

时间复杂度 O(n + m)，空间复杂度 O(n)，可以通过本题。 #### F2 考虑一种情况，当 n 的范围非常大，以至于无法开一个数组记录时，应该如何解决呢？

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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;
}
#### F2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}