初赛程序题专项（三）

二、阅读程序

(1)

01 #include <iostream>
02
03 using namespace std;
04
05 int countSetBits(int n) {
06     int count = 0;
07     while (n > 0) {
08         n &= (n - 1);
09         count++;
10     }
11     return count;
12 }
13
14 int main() {
15     int n, k;
16     cin >> n >> k;
17     int result = -1;
18     for (int i = 1; i <= n; ++i) {
19         if (countSetBits(i) == k) {
20             result = i;
21             break;
22         }
23     }
24     cout << result << endl;
25     return 0;
26 }

判断题

1. countSetBits(n) 函数的功能是计算正整数 n 在二进制表示下 1 的个数。 ( )
2. 第 08 行的 n &= (n - 1) 操作，其作用是清除 n 的二进制表示中最左边（最高位）的 1。 ( )
3. countSetBits(n) 函数的时间复杂度与 n 的二进制表示中 1 的数量成正比。 ( )

选择题

4. 该程序旨在解决的问题是 ( )。

   • A. 寻找 n 的第 k 个约数
   • B. 寻找 k 的第 n 个倍数
   • C. 寻找 1 到 n 之间最小的、二进制表示恰好有 k 个 1 的整数
   • D. 计算 1 到 n 之间所有二进制表示恰好有 k 个 1 的整数的和

5. 若输入为 100 3，则输出为 ( )。

   • A. 7
   • B. 11
   • C. 13
   • D. 14

(2)

01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int n, m;
07 vector<vector<int>> dp;
08
09 int countPaths(int r, int c) {
10     if (r < 0 || c < 0) {
11         return 0;
12     }
13     if (r == 0 && c == 0) {
14         return 1;
15     }
16     if (dp[r][c] != -1) {
17         return dp[r][c];
18     }
19     dp[r][c] = countPaths(r - 1, c) + countPaths(r, c - 1);
20     return dp[r][c];
21 }
22
23 int main() {
24     cin >> n >> m;
25     dp.assign(n, vector<int>(m, -1));
26     cout << countPaths(n - 1, m - 1) << endl;
27     return 0;
28 }

判断题

6. 该程序使用递归和记忆化的方法解决了问题。 ( )
7. dp[r][c] 的值等于组合数 C(r+c, r)（即从 r+c 个物品中选 r 个的方案数）。 ( )
8. 如果将第 19 行 dp[r][c] = countPaths(r - 1, c) + countPaths(r, c - 1); 改为 dp[r][c] = countPaths(n - 2, m - 1) + countPaths(n - 1, m - 2);，程序的功能不变。 ( )

选择题

9. 该程序解决的问题是 ( )。

   • A. 在 n x m 棋盘上从左上角走到右下角的最短路径长度
   • B. 在 n x m 棋盘上放置 k 个互不攻击的象的方法数
   • C. 在 n x m 棋盘上从左上角走到右下角，每次只能向右或向下走的路径总数
   • D. n 个球放入 m 个盒子的总方案数

10. 若输入为 4 3，则输出为 ( )。

    • A. 10
    • B. 12
    • C. 15
    • D. 20

(3)

01 #include <iostream>
02 #include <vector>
03 #include <string>
04 #include <numeric>
05 #include <algorithm>
06
07 using namespace std;
08
09 int main() {
10     int n, k;
11     cin >> n >> k;
12     k--; 
13
14     vector<char> chars;
15     for (int i = 0; i < n; ++i) {
16         chars.push_back('A' + i);
17     }
18
19     vector<long long> fact(n + 1, 1);
20     for (int i = 2; i <= n; ++i) {
21         fact[i] = fact[i - 1] * i;
22     }
23
24     string result = "";
25     for (int i = n; i >= 1; --i) {
26         int index = k / fact[i - 1];
27         result += chars[index];
28         chars.erase(chars.begin() + index);
29         k %= fact[i - 1];
30     }
31
32     cout << result << endl;
33     return 0;
34 }

判断题

11. 该程序预计算了阶乘，是为了进行组合数的计算。 ( )
12. 第 28 行 chars.erase(...) 操作是程序能够正确运行的关键一步，它确保了每个字符只被使用一次。 ( )
13. 若输入 n 极大，k 也极大，程序可能因为第 21 行的阶乘计算而发生整数溢出，导致错误结果。 ( )

选择题

14. 该程序的功能是 ( )。

    • A. 生成杨辉三角的第 n 行第 k 列
    • B. 求解 n 个字符的字符串中长度为 k 的子序列个数
    • C. 生成由前 n 个大写字母构成的第 k 个字典序排列
    • D. 将整数 k 转换为 n 进制表示

15. 若输入为 4 10，则输出为 ( )。

    • A. "BADC"
    • B. "BCDA"
    • C. "CADB"
    • D. "BDCA"

三、完善程序

(1) 统计岛屿数量

题目描述: 给定一个由 '1' (陆地) 和 '0' (水) 组成的 m x n 的二维网格，计算岛屿的数量。一个岛屿被水包围，并通过水平或垂直方向上相邻的陆地连接形成。你可以假设网格的四个边均被水包围。

01 #include <iostream>
02 #include <vector>
03 #include <queue>
04
05 using namespace std;
06
07 void bfs(int r, int c, int m, int n, vector<vector<char>>& grid) {
08     queue<pair<int, int>> q;
09     q.push({r, c});
10     ①;
11     int dr[] = {-1, 1, 0, 0};
12     int dc[] = {0, 0, -1, 1};
13
14     while (②) {
15         pair<int, int> curr = q.front();
16         q.pop();
17
18         for (int i = 0; i < 4; ++i) {
19             int nr = curr.first + dr[i];
20             int nc = curr.second + dc[i];
21
22             if (③ && grid[nr][nc] == '1') {
23                 ④;
24                 q.push({nr, nc});
25             }
26         }
27     }
28 }
29
30 int main() {
31     
32     int m, n;
33     cin >> m >> n;
34     vector<vector<char>> grid(m, vector<char>(n));
35     for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) cin >> grid[i][j];
36
37     int count = 0;
38     for (int i = 0; i < m; ++i) {
39         for (int j = 0; j < n; ++j) {
40             if (grid[i][j] == '1') {
41                 count++;
42                 ⑤(i, j, m, n, grid);
43             }
44         }
45     }
46     cout << count << endl;
47     return 0;
48 }

16. ①处应填 ( )，用于标记起点已被访问。

    • A. grid[r][c] = '0'
    • B. q.pop()
    • C. return
    • D. count++

17. ②处应填 ( )，作为广度优先搜索的循环条件。

    • A. !q.empty()
    • B. q.size() < m*n
    • C. q.front().first < m
    • D. true

18. ③处应填 ( )，用于检查新坐标是否越界。

    • A. nr >= 0 && nr < m && nc >= 0 && nc < n
    • B. nr > 0 || nr < m || nc > 0 || nc < n
    • C. nr != r && nc != c
    • D. grid[nr][nc] != '0'

19. ④处应填 ( )，用于标记新发现的陆地已被访问。

    • A. grid[nr][nc] = grid[r][c]
    • B. grid[nr][nc] = '1'
    • C. grid[nr][nc] = '0'
    • D. continue

20. ⑤处应填 ( )，用于淹没整个岛屿。

    • A. main
    • B. countIslands
    • C. dfs
    • D. bfs

(2) 互质数对统计

题目描述: 给定一个正整数 n，统计满足 1 <= i < j <= n 且 gcd(i, j) = 1 的数对 (i, j) 的数量。gcd(a, b) 指 a 和 b 的最大公约数。

01 #include <iostream>
02
03 using namespace std;
04
05 int gcd(int a, int b) {
06     if (b == 0) {
07         return ①;
08     }
09     return ②;
10 }
11
12 int main() {
13     int n;
14     cin >> n;
15     int count = 0;
16     for (int i = 1; i <= n; ++i) {
17         for (int j = ③; j <= n; ++j) {
18             if (④ == 1) {
19                 count++;
20             }
21         }
22     }
23     cout << count << endl;
24     return 0;
25 }

21. ①处是辗转相除法（欧几里得算法）的递归基例，应填 ( )。

    • A. 0
    • B. 1
    • C. a
    • D. b

22. ②处是算法的递归步骤，应填 ( )。

    • A. gcd(b, a)
    • B. gcd(a, a % b)
    • C. gcd(b, a - b)
    • D. gcd(b, a % b)

23. ③处是内层循环的起始条件，根据题目要求 i < j，应填 ( )。

    • A. 1
    • B. i
    • C. i + 1
    • D. n

24. ④处应调用函数来判断是否互质，应填 ( )。

    • A. gcd(i, j)
    • B. count
    • C. gcd(n, i)
    • D. gcd(n, j)