CSP-J 卷

（质因数分解）给出正整数 $n$，请输出将 $n$ 质因数分解的结果，结果从小到大输出。

例如：输入 n=120，程序应该输出 2 2 2 3 5，表示 $120=2\times2\times2\times3\times5$。输入保证 $2\le n\le10^9$。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。

试补全程序。

1  #include <cstdio>
2  using namespace std;
3 
4  int n, i;
5 
6  int main() {
7      scanf("%d", &n);
8      for (i = ①; ② <= n; i++) {
9          ③ {
10              printf("%d ", i);
11              n = n / i;
12          }
13      }
14      if (④)
15          printf("%d ", ⑤);
16      return 0;
17  }

（矩阵变幻）有一个奇幻的矩阵，在不停地变幻，其变幻方式为：数字 $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  }

（最小区间覆盖）给出 $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  }

（Josephus 问题）有 $n$ 个人围成一个圈，依次标号 $0$ 至 $n-1$。从 $0$ 号开始，依次 $0,1,0,1,\ldots$ 交替报数，报到 $1$ 的人会离开，直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

1  #include <iostream>
2 
3  using namespace std;
4 
5  const int MAXN = 1000000;
6  int F[MAXN];
7 
8  int main() {
9      int n;
10      cin >> n;
11      int i = 0, p = 0, c = 0;
12      while (①) {
13          if (F[i] == 0) {
14              if (②) {
15                  F[i] = 1;
16                  ③;
17              }
18              ④;
19          }
20          ⑤;
21      }
22      int ans = -1;
23      for (i = 0; i < n; i++)
24          if (F[i] == 0)
25              ans = i;
26      cout << ans << endl;
27      return 0;
28  }

试补全程序。

1  #include <bits/stdc++.h>
2  using namespace std;
3 
4  int main() {
5    int n;
6    cin >> n;
7 
8    vector<int> fac;
9    fac.reserve((int)ceil(sqrt(n)));
10 
11    int i;
12    for (i = 1; i * i < n; ++i) {
13      if (①) {
14        fac.push_back(i);
15      }
16    }
17 
18    for (int k = 0; k < fac.size(); ++k) {
19      cout << ② << " ";
20    }
21    if (③) {
22      cout << ④ << " ";
23    }
24    for (int k = fac.size() - 1; k >= 0; --k) {
25      cout << ⑤ << " ";
26    }
27  }

试补全程序。

1  #include <bits/stdc++.h>
2  using namespace std;
3 
4  const int ROWS = 8;
5  const int COLS = 8;
6 
7  struct Point {
8    int r, c;
9    Point(int r, int c) : r(r), c(c) {}
10  };
11 
12  bool is_valid(char image[ROWS][COLS], Point pt,
13                  int prev_color, int new_color) {
14    int r = pt.r;
15    int c = pt.c;
16    return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
17            ① && image[r][c] != new_color);
18  }
19 
20  void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
21    queue<Point> queue;
22    queue.push(cur);
23 
24    int prev_color = image[cur.r][cur.c];
25    ②;
26 
27    while (!queue.empty()) {
28      Point pt = queue.front();
29      queue.pop();
30 
31      Point points[4] = {③, Point(pt.r - 1, pt.c),
32                          Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
33      for (auto p : points) {
34        if (is_valid(image, p, prev_color, new_color)) {
35          ④;
36          ⑤;
37        }
38      }
39    }
40  }
41 
42  int main() {
43    char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
44                                {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
45                                {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
46                                {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
47                                {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
48                                {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
49                                {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
50                               {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
51 
52    Point cur(4, 4);
53    char new_color = 'y';
54 
55    flood_fill(image, cur, new_color);
56 
57    for (int r = 0; r < ROWS; r++) {
58      for (int c = 0; c < COLS; c++) {
59        cout << image[r][c] << " ";
60      }
61      cout << endl;
62    }
63    // 输出：
64    // g g g g g g g g
65    // g g g g g g r r
66    // g r r g g r g g
67    // g y y y y r g r
68    // g g g y y r g r
69    // g g g y y y y r
70    // g g g g g y g g
71    // g g g g g y y g
72 
73    return 0;
74  }

试补全程序。

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  }

试补全程序。

1  #include<iostream>
2  #include<vector>
3  using namespace std;
4 
5  bool isSquare(int num) {
6    int i = ① ;
7    int bound = ② ;
8    for (; i <= bound; ++i) {
9      if ( ③ ) {
10        return ④ ;
11      }
12    }
13    return ⑤ ;
14  }
15  int main() {
16    int n;
17    cin >> n;
18    if (isSquare(n)) {
19      cout << n << " is a square number" << endl;
20    } else {
21      cout << n << " is not a square number" << endl;
22    }
23    return 0;
}

（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将 $n$ 对 $10000$ 以内的整数，从小到大排序。

例如有三对整数 $(3,4)$、$(2,4)$、$(3,3)$，那么排序之后应该是 $(2,4)$、$(3,3)$、$(3,4)$。

输入第一行为 $n$，接下来 $n$ 行，第 $i$ 行有两个数 a[i] 和 b[i]，分别表示第 $i$ 对整数的第一关键字和第二关键字。

从小到大排序后输出。

数据范围 $1\le n\le 10^7$，$1\le a[i],b[i]\le 10^4$。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord[] 存储第二关键字排序的结果，数组 res[] 存储双关键字排序的结果。

试补全程序。

1  #include <cstdio>
2  #include <cstring>
3  using namespace std;
4  const int maxn = 10000000;
5  const int maxs = 10000;
6 
7  int n;
8  unsigned a[maxn], b[maxn], res[maxn], ord[maxn];
9  unsigned cnt[maxs + 1];
10 
11  int main() {
12      scanf("%d", &n);
13      for (int i = 0; i < n; ++i)
14          scanf("%d%d", &a[i], &b[i]);
15      memset(cnt, 0, sizeof(cnt));
16      for (int i = 0; i < n; ++i)
17          ①;  // 利用 cnt 数组统计数量
18      for (int i = 0; i < maxs; ++i)
19          cnt[i + 1] += cnt[i];
20      for (int i = 0; i < n; ++i)
21          ②;  // 记录初步排序结果
22      memset(cnt, 0, sizeof(cnt));
23      for (int i = 0; i < n; ++i)
24          ③;  // 利用 cnt 数组统计数量
25      for (int i = 0; i < maxs; ++i)
26          cnt[i + 1] += cnt[i];
27      for (int i = n - 1; i >= 0; --i)
28          ④;  // 记录最终排序结果
29      for (int i = 0; i < n; ++i)
30          printf("%d %d\n", ⑤);
31      return 0;
32  }

（矩形计数）平面上有 $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  #include <string>
3  #include <vector>
4  using namespace std;
5 
6  int min(int x, int y, int z) {
7      return min(min(x, y), z);
8  }
9 
10  int edit_dist_dp(string str1, string str2) {
11      int m = str1.length();
12      int n = str2.length();
13      vector<vector<int>> dp(m + 1, vector<int>(n + 1));
14 
15      for (int i = 0; i <= m; i++) {
16          for (int j = 0; j <= n; j++) {
17              if (i == 0)
18                  dp[i][j] = ①;
19              else if (j == 0)
20                  dp[i][j] = ②;
21              else if (③)
22                  dp[i][j] =④;
23              else
24                  dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
25          }
26      }
27      return dp[m][n];
28  }
29 
30  int main() {
31      string str1, str2;
32      cin >> str1 >> str2;
33      cout << "Minimum number of operations: "
34          << edit_dist_dp(str1, str2) << endl;
35      return 0;
36  }

试补全程序。

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4 
5  void move(char src, char tgt) {
6    cout << "从柱子" << src << "挪到柱子" << tgt << endl;
7  }
8  void dfs(int i, char src, char tmp, char tgt) {
9    if (i == ① ) {
10      move( ② );
11      return;
12    }
13    dfs(i - 1, ③ );
14    move(src, tgt);
15    dfs( ⑤ , ④ );
16  }
17 
18  int main() {
19    int n;
20    cin >> n;
21    dfs(n, 'A', 'B', 'C');
22  }

（字符串解码）“行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：

i) 如果原始字符串中一个字符连续出现 $N$ 次（$N > 2$），在压缩字符串中它被表示为“字符 + 数字 $N$”。例如，编码 A12 代表 $12$ 个连续的字符 A。

ii) 如果原始字符串中一个字符只出现 $1$ 次，在压缩字符串中它就表示为该字符本身。例如，编码 B 代表 $1$ 个字符 B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

1  #include <cctype>
2  #include <iostream>
3  #include <string>
4  using namespace std;
5 
6  int main() {
7      string z;
8      cin >> z;
9      string s = "";
10 
11      for (int i = 0; i < z.length(); ) {
12          char ch = z[i];
13 
14          if (___①___ && isdigit(z[i + 1])) {
15              i++;
16              int count = 0;
17              while (i < z.length() && isdigit(z[i])) {
18                  count = ___②___;
19                  i++;
20              }
21              for (int j = 0; j < ___③___; ++j) {
22                  s += ch;
23              }
24          } else {
25              s += ___④___;
26              ___⑤___;
27          }
28      }
29 
30      cout << s << endl;
31      return 0;
32  }

（精明与糊涂）有 $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  }