CSP-J 复习卷 J01 · 基础算法

贪心算法的核心特征是？

对一个数组做二分查找，必须满足的前提是？

一个递归函数要能正确终止，必须具备？

用数组递推斐波那契 f[i]=f[i-1]+f[i-2]，正确的填表顺序是？

在 1000 个有序元素中做二分查找，最坏情况大约比较多少次？

下列哪种情形最容易导致调用栈溢出？

阅读标准二分（闭区间写法）：

01int a[] = {2, 5, 8, 11, 15, 19, 23};   // 下标 0..6
02int l = 0, r = 6, x = 19;
03while (l <= r) {
04    int mid = (l + r) / 2;
05    if (a[mid] == x) { cout << mid; break; }
06    else if (a[mid] < x) l = mid + 1;
07    else r = mid - 1;
08}

预处理「跳 1、2、4、8、…、2ᵏ 步」的信息，任意大步长由若干 2 的幂拼出。这种思想是？

用快速幂计算 $a^k$，乘法次数的量级是？

爬楼梯递推 f[i]=f[i-1]+f[i-2] 忘记初始化 f[1]=1, f[2]=2，会导致？

蛋糕切成 4 段：6、9、7、12 厘米。分给 6 人，每份为整数厘米、必须来自同一段（段可切开、不可拼接）。每人最多分到几厘米？

3 根原木长 10、24、15 厘米，切出 7 段等长木条（整数厘米，碎料丢弃、不可拼接）。每段最长几厘米？

5 人接水需 3、6、1、4、2 分钟，只有一个水龙头。每个人的等待时间为排在前面的人接水时间之和（第一人等待 0）。最短的总等待时间是？

6 个活动起止时间为 [1,4]、[2,6]、[3,5]、[5,7]、[6,9]、[8,10]。同一时间只能参加一个，端点相接不算冲突。最多能参加几个？

4 堆果子有 1、2、3、4 个。每次合并任意两堆，体力消耗等于两堆个数之和，直到只剩一堆。最小总体力消耗是？

「二分答案」能够使用的核心前提是？

求「check 为真的最大 x」：

01int l = 0, r = n;
02while (l < r) {
03    int mid = (l + r) / 2;
04    if (check(mid)) l = mid;
05    else r = mid - 1;
06}

左闭右开模板找「第一个 ≥ x 的位置」：

01int l = 0, r = n;
02while (l < r) {
03    int mid = (l + r) / 2;
04    if (a[mid] >= x) r = mid;
05    else l = mid + 1;
06}

实数域二分求 $\sqrt{x}$：

01double l = 0, r = x;
02for (int _ = 0; _ < 100; _++) {
03    double mid = (l + r) / 2;
04    if (mid * mid <= x) l = mid;
05    else r = mid;
06}

上 n 阶楼梯，每次可上 1 阶或 2 阶。方案数 f(n) 满足的递推是？

数字三角形：

    2
   3 4
  6 5 1

杨辉三角按 C(n,k)=C(n-1,k-1)+C(n-1,k) 逐行递推。推到第 5 行（n=5），该行中间三个数依次是？

汉诺塔递归：

01void hanoi(int n, char from, char to, char via) {
02    if (n == 0) return;
03    hanoi(n - 1, from, via, to);
04    cout << "move " << n << ": " << from << "->" << to << "\n";
05    hanoi(n - 1, via, to, from);
06}

约瑟夫环线性递推（从 0 报数，报到 k-1 出列）：

01int f = 0;
02for (int m = 2; m <= n; m++)
03    f = ____;

有序数组 a = {1, 3, 3, 7}，表达式 lower_bound(a, a + 4, 3) - a 的值是？

证明「按结束时间排序的活动选择」最优，常用的证明手法是？

起点到终点相距 25 米，其间 5 块石头距起点分别为 2、11、14、17、21 米。选手必须从起点跳到终点，只能落在石头或起终点上。最多搬走 2 块石头，要使最短单步距离尽量大，这个最大值是？

「数轴上选 m 个点，最大化最小间距」的模板：

01bool check(int d) {
02    int cnt = 1, last = x[0];
03    for (int i = 1; i < n; i++)
04        if (x[i] - last >= d) { cnt++; last = x[i]; }
05    return cnt >= m;
06}

n 封信全部装错（每封都不在自己的信封里）的方案数 D(n) 满足？

n 个元素依次进栈、任意时刻可出栈，不同的出栈序列共有（递推表示，C(0)=1）？

0/1 背包容量 10：物品 A（重 7，值 9）、B（重 5，值 5）、C（重 5，值 5）。按性价比贪心选 A 后总价值 9，而选 B+C 总价值 10。这说明了？

整数二分中，分支包含 l = mid（mid 留在区间内）时，mid 应取？

斐波那契滚动写法：

01int a = 0, b = 1;                 // f(0), f(1)
02for (int i = 2; i <= n; i++) {
03    int c = a + b;
04    a = b; b = c;
05}

倍增求「从 i 跳 k 步到哪」的预处理：

01up[0][i] = next[i];
02for (int k = 1; (1 << k) <= n; k++)
03    for (int i = 0; i < n; i++)
04        up[k][i] = ____;

关于二分与倍增的适用条件，下列说法正确的是？

递归式 T(n) = 2T(n-1) + 1，T(1)=1（如汉诺塔）展开后 T(n) 的量级是？

计算 a¹³ 时，13 的二进制为 1101，快速幂把 a¹³ 拆成？

设有 $100$ 个已排好序的数据元素，采用折半查找时，最大比较次数为（ ）。

新学期开学了，小胖想减肥，健身教练给小胖制定了两个训练方案。方案一：每次连续跑 $3$ 公里可以消耗 $300$ 千卡（耗时半小时）；方案二：每次连续跑 $5$ 公里可以消耗 $600$ 千卡（耗时 $1$ 小时）。小胖每周周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。另外，教练建议小胖每周最多跑 $21$ 公里，否则会损伤膝盖。请问如果小胖想严格执行教练的训练方案，并且不想损伤膝盖，每周最多通过跑步消耗多少千卡？（ ）

1  #include <iostream>
2  using namespace std;
3  const int maxn = 10000;
4  int n;
5  int a[maxn];
6  int b[maxn];
7  int f(int l, int r, int depth) {
8      if (l > r)
9          return 0;
10      int min = maxn, mink;
11      for (int i = l; i <= r; ++i) {
12          if (min > a[i]) {
13              min = a[i];
14              mink = i;
15          }
16      }
17      int lres = f(l, mink - 1, depth + 1);
18      int rres = f(mink + 1, r, depth + 1);
19      return lres + rres + depth * b[mink];
20  }
21  int main() {
22      cin >> n;
23      for (int i = 0; i < n; ++i)
24          cin >> a[i];
25      for (int i = 0; i < n; ++i)
26          cin >> b[i];
27      cout << f(0, n - 1, 1) << endl;
28      return 0;
29  }

（矩阵变幻）有一个奇幻的矩阵，在不停地变幻，其变幻方式为：数字 $0$ 变成矩阵 $\begin{bmatrix}0&0\\0&1\end{bmatrix}$，数字 $1$ 变成矩阵 $\begin{bmatrix}1&1\\1&0\end{bmatrix}$。最初该矩阵只有一个元素 $0$，变幻 $n$ 次后，矩阵会变成什么样？

例如，矩阵最初为：$\begin{bmatrix}0\end{bmatrix}$；矩阵变幻 $1$ 次后：$\begin{bmatrix}0&0\\0&1\end{bmatrix}$；矩阵变幻 $2$ 次后：$\begin{bmatrix}0&0&0&0\\0&1&0&1\\0&0&1&1\\0&1&1&0\end{bmatrix}$。

输入一行一个不超过 $10$ 的正整数 $n$。输出变幻 $n$ 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如 $(11)_2$ << $2=(1100)_2$；

而 ^ 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$，反之为 $1$。

1  #include <cstdio>
2  using namespace std;
3  int n;
4  const int max_size = 1 << 10;
5 
6  int res[max_size][max_size];
7 
8  void recursive(int x, int y, int n, int t) {
9      if (n == 0) {
10          res[x][y] = ①;
11          return;
12      }
13      int step = 1 << (n - 1);
14      recursive(②, n - 1, t);
15      recursive(x, y + step, n - 1, t);
16      recursive(x + step, y, n - 1, t);
17      recursive(③, n - 1, !t);
18  }
19 
20  int main() {
21      scanf("%d", &n);
22      recursive(0, 0, ④);
23      int size = ⑤;
24      for (int i = 0; i < size; ++i) {
25          for (int j = 0; j < size; ++j)
26              printf("%d", res[i][j]);
27          puts("");
28      }
29      return 0;
30  }

设 $A$ 是 $n$ 个实数的数组，考虑下面的递归算法：

XYZ(A[1..n])
1 if n = 1 then return A[1]
2 else temp ← XYZ(A[1..n-1])
3      if temp < A[n]
4          then return temp
5          else return A[n]

请问算法 XYZ 的输出是什么？（ ）

1  #include <algorithm>
2  #include <iostream>
3  using namespace std;
4 
5  int n;
6  int d[50][2];
7  int ans;
8 
9  void dfs(int n, int sum) {
10      if (n == 1) {
11          ans = max(sum, ans);
12          return;
13      }
14      for (int i = 1; i < n; ++i) {
15          int a = d[i - 1][0], b = d[i - 1][1];
16          int x = d[i][0], y = d[i][1];
17          d[i - 1][0] = a + x;
18          d[i - 1][1] = b + y;
19          for (int j = i; j < n - 1; ++j)
20              d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
21          int s = a + x + abs(b - y);
22          dfs(n - 1, sum + s);
23          for (int j = n - 1; j > i; --j)
24              d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
25          d[i - 1][0] = a, d[i - 1][1] = b;
26          d[i][0] = x, d[i][1] = y;
27      }
28  }
29 
30  int main() {
31      cin >> n;
32      for (int i = 0; i < n; ++i)
33          cin >> d[i][0];
34      for (int i = 0; i < n; ++i)
35          cin >> d[i][1];
36      ans = 0;
37      dfs(n, 0);
38      cout << ans << endl;
39      return 0;
40  }

假设输入的 $n$ 是不超过 $50$ 的正整数，d[i][0]、d[i][1] 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题。

（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0,m]$ 被所选区间的并覆盖（即每一个 $0\le i\le m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 $n$ 和 $m$（$1\le n\le5000$，$1\le m\le10^9$）。

接下来 $n$ 行，每行两个整数 $a_i$、$b_i$（$0\le a_i,b_i\le m$）。

提示：使用贪心法解决这个问题。先用 $\Theta(n^2)$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

1  #include <iostream>
2 
3  using namespace std;
4 
5  const int MAXN = 5000;
6  int n, m;
7  struct segment { int a, b; } A[MAXN];
8 
9  void sort() // 排序
10  {
11      for (int i = 0; i < n; i++)
12          for (int j = 1; j < n; j++)
13              if (①)
14              {
15                  segment t = A[j];
16                  ②
17              }
18  }
19 
20  int main()
21  {
22      cin >> n >> m;
23      for (int i = 0; i < n; i++)
24          cin >> A[i].a >> A[i].b;
25      sort();
26      int p = 1;
27      for (int i = 1; i < n; i++)
28          if (③)
29              A[p++] = A[i];
30      n = p;
31      int ans = 0, r = 0;
32      int q = 0;
33      while (r < m)
34      {
35          while (④)
36              q++;
37          ⑤;
38          ans++;
39      }
40      cout << ans << endl;
41      return 0;
42  }

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

有四个人要从 $A$ 点坐一条船过河到 $B$ 点，船一开始在 $A$ 点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为 $1$、$2$、$4$、$8$，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人都过河到 $B$ 点（包括从 $B$ 点把船开回 $A$ 点的时间）。

（矩形计数）平面上有 $n$ 个关键点，求有多少个四条边都和 x 轴或者 y 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

1  #include <iostream>
2 
3  using namespace std;
4 
5  struct point {
6      int x, y, id;
7  };
8 
9  bool equals(point a, point b) {
10      return a.x == b.x && a.y == b.y;
11  }
12 
13  bool cmp(point a, point b) {
14      return ①;
15  }
16 
17  void sort(point A[], int n) {
18      for (int i = 0; i < n; i++)
19          for (int j = 1; j < n; j++)
20              if (cmp(A[j], A[j - 1])) {
21                  point t = A[j];
22                  A[j] = A[j - 1];
23                  A[j - 1] = t;
24              }
25  }
26 
27  int unique(point A[], int n) {
28      int t = 0;
29      for (int i = 0; i < n; i++)
30          if (②)
31              A[t++] = A[i];
32      return t;
33  }
34 
35  bool binary_search(point A[], int n, int x, int y) {
36      point p;
37      p.x = x;
38      p.y = y;
39      p.id = n;
40      int a = 0, b = n - 1;
41      while (a < b) {
42          int mid = ③;
43          if (④)
44              a = mid + 1;
45          else
46              b = mid;
47      }
48      return equals(A[a], p);
49  }
50 
51  const int MAXN = 1000;
52  point A[MAXN];
53 
54  int main() {
55      int n;
56      cin >> n;
57      for (int i = 0; i < n; i++) {
58          cin >> A[i].x >> A[i].y;
59          A[i].id = i;
60      }
61      sort(A, n);
62      n = unique(A, n);
63      int ans = 0;
64      for (int i = 0; i < n; i++)
65          for (int j = 0; j < n; j++)
66              if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) {
67                  ans++;
68              }
69      cout << ans << endl;
70      return 0;
71  }

1  #include <iostream>
2 
3  using namespace std;
4 
5  int n, k;
6 
7  int solve1()
8  {
9      int l = 0, r = n;
10      while (l <= r) {
11          int mid = (l + r) / 2;
12          if (mid * mid <= n) l = mid + 1;
13          else r = mid - 1;
14      }
15      return l - 1;
16  }
17 
18  double solve2(double x)
19  {
20      if (x == 0) return x;
21      for (int i = 0; i < k; i++)
22          x = (x + n / x) / 2;
23      return x;
24  }
25 
26  int main()
27  {
28      cin >> n >> k;
29      double ans = solve2(solve1());
30      cout << ans << ' ' << (ans * ans == n) << endl;
31      return 0;
32  }

假设 int 为 $32$ 位有符号整数类型，输入的 n 是不超过 $47000$ 的自然数、k 是不超过 int 表示范围的自然数，

试补全程序。

1  #include <iostream>
2  #include <vector>
3 
4  using namespace std;
5 
6  int find_missing(vector<int>& nums) {
7      int left = 0, right = nums.size() - 1;
8      while (left < right) {
9          int mid = left + (right - left) / 2;
10          if (nums[mid] == mid + ①) {
11              ②;
12          } else {
13              ③;
14          }
15      }
16      return ④;
17  }
18 
19  int main() {
20      int n;
21      cin >> n;
22      vector<int> nums(n);
23      for (int i = 0; i < n; i++) cin >> nums[i];
24      int missing_number = find_missing(nums);
25      if (missing_number == ⑤) {
26          cout << "Sequence is consecutive" << endl;
27      } else {
28          cout << "Missing number is " << missing_number << endl;
29      }
30      return 0;
31  }

假设有序表中有 1000 个元素，则用二分法查找元素 X 最多需要比较（ ）次。

已知 $f[0] = 1 , f[1] = 1$，并且对于所有 $n \geq 2$ 有 $f[n] = (f[n-1] + f[n-2]) \% 7$。那么 $f[2025]$ 的值是多少？（ ）

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  #define ll long long
5 
6  int n, k;
7  int a[200007];
8  int ans[200007];
9 
10  int main() {
11      scanf("%d%d", &n, &k);
12      for (int i = 1; i <= n; ++i) {
13          scanf("%d", &a[i]);
14      }
15      std::sort(a + 1, a + n + 1);
16      n = std::unique(a + 1, a + n + 1) - a - 1;
17      for (int i = 1, j = 0; i <= n; ++i) {
18          for (; j < i && a[i] - a[j + 1] > k; ++j)
19          ;
20          ans[i] = ans[j] + 1;
21      }
22      printf("%d\n", ans[n]);
23      return 0;
24  }

（精明与糊涂）有 $N$ 个人，分为两类：

i) 精明人：永远能正确判断其他人是精明还是糊涂。

ii) 糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > \frac{N}{2}$。

你只能通过函数 query(i, j) 让第 $i$ 个人判断第 $j$ 个人：返回 true 表示判断结果为“精明人”；返回 false 表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心 query(i, j) 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。

例如，假设有三个人 $0$、$1$、$2$。如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$。由于三人里至少有两个精明人，我们确定 $2$ 是精明人。试补全程序。

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4 
5  int N;
6  bool query(int i, int j);
7 
8  int main() {
9      cin >> N;
10 
11      int candidate = 0;
12      int count = ___①___;
13 
14      for (int i = 1; i < N; ++i) {
15          if (___②___) {
16              candidate = i;
17              count = 1;
18          } else {
19              if (___③___) {
20                  ___④___;
21              } else {
22                  count++;
23              }
24          }
25      }
26 
27      cout << ___⑤___ << endl;
28      return 0;
29  }