真题练习

CSP-J 2022 入门级 第一轮 第16题

题目：阅读程序

#include <iostream>

using namespace std;

int main() {
    // 声明两个 16 位无符号短整型变量 x 和 y
    unsigned short x, y;
    
    // 从标准输入读取两个不超过 15 的自然数
    cin >> x >> y;
    
    // 对 x 进行位运算：
    // 1. x << 2：将 x 左移 2 位（相当于乘 4）
    // 2. x | x << 2：将 x 与其左移 2 位后的值进行按位或操作
    // 3. & 0x33：将上述结果与 0x33 (二进制 00110011) 按位与
    x = (x | x << 2) & 0x33;

    // 对 x 继续进行位运算：
    // 1. x << 1：将 x 左移 1 位
    // 2. x | x << 1：将 x 与其左移 1 位后的值进行按位或操作
    // 3. & 0x55：将上述结果与 0x55 (二进制 01010101) 按位与
    x = (x | x << 1) & 0x55;

    // 对 y 进行与 x 相同的位运算
    y = (y | y << 2) & 0x33;
    y = (y | y << 1) & 0x55;

    // 计算 z：
    // 将 y 左移 1 位，并将结果与 x 进行按位或操作
    unsigned short z = x | y << 1;
    
    // 输出 z 的值
    cout << z << endl;
    
    return 0;
}

位移运算符

位移运算符（Shift Operators）在 C++ 中用于对整数类型的数据进行位操作。这些运算符包括左移运算符（<<）和右移运算符（>>）。

1. 左移运算符 (<<)

左移运算符会将二进制数向左移动指定的位数，在右边补零。这相当于对该数乘以 2 的指定次方。

语法

result = num << n;

• num 是要操作的数。
• n 是需要左移的位数。

示例

#include <iostream>

int main() {
    int num = 5;      // 二进制表示：0000 0101
    int result = num << 2; // 左移 2 位：0010 0100，相当于 5 * 2^2 = 20

    std::cout << "5 左移 2 位后的结果是: " << result << std::endl; // 输出 20

    return 0;
}

解释

• 5 的二进制表示为 0000 0101。
• 左移 2 位后，结果变为 0010 0100，即 20。

2. 右移运算符 (>>)

右移运算符会将二进制数向右移动指定的位数。如果是无符号数或正数，在左边补零；如果是负数，具体行为依赖于编译器（通常会补符号位，即补 1）。

语法

result = num >> n;

• num 是要操作的数。
• n 是需要右移的位数。

示例

#include <iostream>

int main() {
    int num = 20;     // 二进制表示：0001 0100
    int result = num >> 2; // 右移 2 位：0000 0101，相当于 20 / 2^2 = 5

    std::cout << "20 右移 2 位后的结果是: " << result << std::endl; // 输出 5

    return 0;
}

解释

• 20 的二进制表示为 0001 0100。
• 右移 2 位后，结果变为 0000 0101，即 5。

3. 带符号整数的右移

在处理负数时，右移运算符的行为可能会依赖编译器。通常情况下，右移会保留符号位（最高位），即进行符号扩展。

示例

#include <iostream>

int main() {
    int num = -20;    // 二进制表示：1111 1111 1110 1100（假设 32 位系统）
    int result = num >> 2; // 右移 2 位：1111 1111 1111 1011

    std::cout << "-20 右移 2 位后的结果是: " << result << std::endl; // 输出 -5

    return 0;
}

解释

• -20 在 32 位系统中通常表示为 1111 1111 1110 1100（使用补码表示）。
• 右移 2 位后，结果变为 1111 1111 1111 1011，即 -5。

4. 注意事项

• 溢出问题：移位操作不会改变操作数的大小，因此进行过大的移位操作可能导致溢出。例如，对于 32 位整数，左移超过 31 位会导致结果不确定。
• 无符号数：对于无符号整数，右移时总是用零填充左边的空位，而不会进行符号扩展。

判断题

1. 删去第 7 行与第 13 行的 unsigned ，程序行为不变。（ ）
2. 将第 7 行与第 13 行的 short 均改为 char ，程序行为不变。（ ）
3. 程序总是输出一个整数“0”。（ ）
4. 当输入为“2 2”时，输出为“10”。（ ）
5. 当输入为“2 2”时，输出为“59”。（ ）

单选题

1. 当输入为“13 8”时，输出为（ ）。
   • A. “0”
   • B. “209”
   • C. “197”
   • D. “226”

---

题目考点

• 位运算：本题的核心考点是位运算，特别是移位操作、按位或操作、按位与操作的组合使用。

解题思路

本题程序主要涉及一系列位运算操作，没有具体的业务意义。以下是对程序的详细分析和解析。

---

判断题解析

1. 删去第 7 行与第 13 行的 unsigned，程序行为不变。

   正确：
   声明变量时是否加 unsigned 只影响该变量是否表示无符号数（即是否允许表示负数），但不影响其实际存储的二进制机器数值。对于本题，所有操作都是在无符号数的基础上进行的位操作，删去 unsigned 并不会改变位运算的结果，因此程序行为不变。

2. 将第 7 行与第 13 行的 short 均改为 char，程序行为不变。

   错误：
   short 类型占 16 位，而 char 类型占 8 位。同样的位运算操作对于 16 位与 8 位机器数的结果会有所不同。
   例如，当机器数为 10000000，左移 1 位时，如果是 16 位机器数，结果为 100000000；如果是 8 位机器数，结果为 00000000。
   因此将 short 改为 char 后程序行为会发生改变。

3. 程序总是输出一个整数“0”。

   错误：
   通过具体计算不同输入下的输出可以验证，程序的输出不总是 0。例如当输入为 "13 8" 时，输出为 209。

4. 当输入为“2 2”时，输出为“10”。

   错误
   实际计算结果并非 10，后文有详细分析。

5. 当输入为“2 2”时，输出为“59”。

   错误
   实际计算结果也并非 59。通过具体分析可得，输入 "2 2" 时的输出为 12。

单选题解析

1. 当输入为“13 8”时，输出为（ ）？

   • 选择 B：209。

---

详细运算步骤解析

假设输入为 x = 2 和 y = 2，按照程序执行的步骤，详细运算过程如下：

第一步：计算 x = (x | x << 2) & 0x33

1. 初始 x 值为 2（即二进制 0000 0010）。
2. x << 2：0000 0010 左移 2 位得到 0000 1000。
3. x | x << 2：0000 0010 与 0000 1000 按位或，结果为 0000 1010。
4. 0x33 的二进制表示为 0011 0011。
5. (x | x << 2) & 0x33：0000 1010 与 0011 0011 按位与，结果为 0000 0010。

表达式	机器数
x	0000 0010
x << 2	0000 1000
x | x << 2	0000 1010
0x33	0011 0011
(x | x << 2) & 0x33	0000 0010

第二步：计算 x = (x | x << 1) & 0x55

1. 初始 x 值为 0000 0010。
2. x << 1：0000 0010 左移 1 位得到 0000 0100。
3. x | x << 1：0000 0010 与 0000 0100 按位或，结果为 0000 0110。
4. 0x55 的二进制表示为 0101 0101。
5. (x | x << 1) & 0x55：0000 0110 与 0101 0101 按位与，结果为 0000 0100。

表达式	机器数
x	0000 0010
x << 1	0000 0100
x | x << 1	0000 0110
0x55	0101 0101
(x | x << 1) & 0x55	0000 0100

因此，x 的最终结果为 0000 0100。

第三步：计算 y 的值

y 与 x 的初值相同，运算过程也完全相同。因此，经过计算后 y 的结果也为 0000 0100。

第四步：计算 z = x | y << 1

1. 初始 y 值为 0000 0100。
2. y << 1：0000 0100 左移 1 位得到 0000 1000。
3. x 当前值为 0000 0100。
4. x | y << 1：0000 0100 与 0000 1000 按位或，结果为 0000 1100。

表达式	机器数
y	0000 0100
y << 1	0000 1000
x	0000 0100
x | y << 1	0000 1100

最终，z 的值为 0000 1100，转换为十进制为 12。

---

CSP-J 2022 入门级 第一轮 第17题

题目：阅读程序

#include <algorithm>
#include <iostream>
#include <limits>

using namespace std;

const int MAXN = 105;  // 定义最大值，表示n的上限
const int MAXK = 105;  // 定义最大值，表示m的上限

int h[MAXN][MAXK];  // 定义二维数组h，用于存储中间计算结果

// 递归函数f，计算最坏情况下最少次数
int f(int n, int m) {
    if (m == 1) return n;  // 如果m为1，直接返回n
    if (n == 0) return 0;  // 如果n为0，返回0

    int ret = numeric_limits<int>::max();  // 初始化返回值为最大整数
    for (int i = 1; i <= n; i++)  // 枚举每一种可能的情况
        ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);  // 递归调用，求出最坏情况下最少的尝试次数
    return ret;  // 返回计算结果
}

// 动态规划函数g，计算最坏情况下最少次数
int g(int n, int m) {
    for (int i = 1; i <= n; i++)  // 初始化边界情况
        h[i][1] = i;  // 当m为1时，h[i][1] = i
    for (int j = 1; j <= m; j++)
        h[0][j] = 0;  // 当n为0时，h[0][j] = 0

    // 递推计算每个h[i][j]的值
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            h[i][j] = numeric_limits<int>::max();  // 初始化h[i][j]为最大值
            for (int k = 1; k <= i; k++)
                h[i][j] = min(h[i][j], max(h[i - k][j], h[k - 1][j - 1]) + 1);  // 更新h[i][j]的值
        }
    }

    return h[n][m];  // 返回最终结果
}

int main() {
    int n, m;
    cin >> n >> m;  // 输入n和m的值
    cout << f(n, m) << endl << g(n, m) << endl;  // 输出递归函数和动态规划函数的结果
    return 0;
}

假设输入的 n 、 m 均是不超过 100 的正整数，完成下面的判断题和单选题：

判断题

1. 当输入为“7 3”时，第19行用来取最小值的 min 函数执行了 449 次。（ ）
2. 输出的两行整数总是相同的。（ ）
3. 当 m 为 1 时，输出的第一行总为 n。（ ）

单选题

1. 算法 g(n, m) 最为准确的时间复杂度分析结果为（ ）

   • A. $O\left(\frac{n^{3/2}}{m}\right)$
   • B. $O(nm)$
   • C. $O(n^2m)$
   • D. $O(nm^2)$

2. 当输入为“20 2”时，输出的第一行为（ ）

   • A. "4"
   • B. "5"
   • C. "6"
   • D. "20"

3. 当输入为“100 100”时，输出的第一行为（ ）

   • A. "6"
   • B. "7"
   • C. "8"
   • D. "9"

---

题目考点

1. 递推/递归 动态规划

   • 本题考察递推和递归的相关知识，特别是如何通过动态规划的方法来优化递归算法的时间复杂度。

2. C++11 numeric_limits

   • 在 C++11 中，引入 <limits> 头文件后可以使用 numeric_limits 模板类来获取各种数据类型的特性值。
   • 常用函数：
     • numeric_limits<数据类型>::max()：返回该数据类型可以表示的最大值。
     • numeric_limits<数据类型>::min()：返回该数据类型可以表示的最小值。
     • numeric_limits<数据类型>::epsilon()：返回该数据类型可以区分的两个数值的最小差值（即如果两个数值的差值小于该值，计算机认为这两个数值相等）。

解题思路

1. 代码分析与递归算法

   • 观察代码，可以看出 f 函数使用了递归算法。
   • 递归关系：f(n, m) 的值为：在 i 从 1 循环到 n 的过程中，计算 max(f(n-i, m), f(i-1, m-1)) + 1 的最小值。
   • 递归出口：
     • 当 m 是 1 时，f(n, m) 的值为 n；
     • 当 n 是 0 时，f(n, m) 的值为 0。

2. 递推算法

   • g 函数使用了递推算法。
   • 初始状态：
     • 当 j 是 1 时，h[i][j] 的值为 i；
     • 当 i 是 0 时，h[i][j] 的值为 0。
   • 递推关系：h[i][j] 的值为：在 k 从 1 循环到 i 的过程中，计算 max(h[i-k][j], h[k-1][j-1]) + 1 的最小值。

3. 递归与递推的对比

   • 对比两者，可以发现：
     • 如果把 f 函数中的 n 替换为 i，m 替换为 j，i 替换为 k，递归出口对应递推初始状态，递归关系对应递推关系。
   • 递推和递归本就是可以相互转化的两种方法。两者实际上是在解决相同问题时采用的不同方法。

---

判断题解析

1. 当输入为“7 3”时，第19行用来取最小值的 min 函数执行了 449 次。

   • 答：错误。
   • 解析：
     • 对于一次调用 f(n, m)，for 循环中的内容会执行 n 次，也就是说 min 函数会被调用 n 次。
     • 统计所有的递归调用，将 n 累加即可。
     • 定义 c(n, m) 为 f(n, m) 运行时 min 函数的调用次数，其值为递归调用中 min 的调用次数的加和，再加上 f(n, m) 中对 min 的 n 次调用。
     • 使用填表法（实际是递推法），从 m、n 值较小的情况逐步推导到较大的情况。

   c(n, m)	m=2	m=3
   n=1	c(0,2) + c(0,1) + 1 = 1	c(0,3) + c(0,2) + 1 = 1
   n=2	c(1,2) + c(0,2) + 2 = 3	c(1,3) + c(0,3) + c(0,2) + c(1,2) + 2 = 4
   n=3	c(2,2) + c(1,2) + 3 = 7	c(2,3) + c(1,3) + c(1,2) + c(2,2) + 3 = 12
   n=4	c(3,2) + c(2,2) + c(1,2) + 4 = 15	c(3,3) + c(2,3) + c(1,3) + c(1,2) + c(2,2) + c(3,2) + 4 = 32
   n=5	c(4,2) + ... + c(1,2) + 5 = 31	c(4,3) + ... + c(1,3) + c(1,2) + ... + c(4,2) + 5 = 80
   n=6	c(5,2) + ... + c(1,2) + 6 = 63	c(5,3) + ... + c(1,3) + c(1,2) + ... + c(5,2) + 6 = 192
   n=7	c(6,2) + ... + c(1,2) + 7 = 127	c(6,3) + ... + c(1,3) + c(1,2) + ... + c(6,2) + 7 = 448

   • 根据递推公式可以得到：
     • $c(n, 2) = c(n-1, 2) \times 2 + 1$
     • $c(n, 3) = 2 \times c(n-1, 3) + c(n-1, 2) + 1$
   • 最终得出 f(7,3) 中 min 函数的调用次数为 448 次，而不是 449 次。

2. 输出的两行整数总是相同的。

   • 答：正确。
   • 解析：通过观察可知，f 函数使用递归，g 函数使用递推，两者解决的是相同的问题，输出的结果必然相同。

3. 当 m 为 1 时，输出的第一行总为 n。

   • 答：正确。
   • 解析：在递归函数 f 中，如果 m 为 1，函数会直接返回 n。而在递推函数 g 中，当 j 为 1 时，h[i][j] 为 i，因此返回值 h[n][m] 一定为 n。

单选题解析

1. 算法 g(n, m) 最为准确的时间复杂度分析结果为（ ）。

   • A. $O \left( \frac{n^{3/2}}{m} \right)$
   • B. $O(nm)$
   • C. $O(n^2m)$
   • D. $O(nm^2)$
   • 答： 选C
   • 解析：
     • 第25，26行循环n次，复杂度为 $O(n)$
     • 第27，28行循环m次，复杂度为 $O(m)$
     • 对于第30，31行，谁在内层谁在外层都不影响最内层代码执行的次数。
     • 我们把 for(int j = 2; j <= m; ++j) 当做外层，这一层近似于循环m次，
     • 对于第33行 for(int k = 1; k <= i; ++k)，i是1时循环1次，i是2时循环2次，...，i是n时循环n次，那么在j固定时，i从1循环到n，最内层循环体执行次数为：

       $1 + 2 + \cdots + n = \frac{(1 + n) \cdot n}{2}$

     • 总执行次数为：

       $m \cdot \frac{n \cdot (1 + n)}{2}$

     • 整段代码的时间复杂度为：

       $O(n) + O(m) + O(m \cdot \frac{n \cdot (1 + n)}{2}) = O(n^2m)$

2. 当输入为“20 2”时，输出的第一行为（ ）。

   • A. “4”
   • B. “5”
   • C. “6”
   • D. “20”
   • 答： 选C
   • 解析：
     • 模拟运行递推算法g函数，填表表中第i行第j列为h[i][j]的值
     • j为1时，h[i][j]的值为1。
     • h[i][j]的值为：k从1循环到i，max(h[i-k][j], h[k-1][j-1]) + 1 的最小值
     • 算过几个后就可以找到规律：j=1这一列从i=0开始从上向下看，j=2这一列从i-1开始从下向上看，对应位置的数值求最大值，看哪一组求得的最大值最大，结果再加1，就是h[i][j]的值。
     • 算出一些数字后，就能发现规律：1个1，2个2，3个3，…，6个6。

h[i][j]	j=1	j=2
i=0	0	0
i=1	1	1
i=2	2	2
i=3	3	2
i=4	4	3
i=5	5	3
i=6	6	3
i=7	7	4
i=8	8	4
i=9	9	4
i=10	10	4
i=11	11	5
i=12	12	5
i=13	13	5
i=14	14	5
i=15	15	5
i=16	16	6
i=17	17	6
i=18	18	6
i=19	19	6
i=20	20	6

    - 得到h[20][2]的值为6。

3. 当输入为“100 100”时，输出的第一行为（ ）。
   • A. “6”
   • B. “7”
   • C. “8”
   • D. “9”
   • 答： 选B
   • 解析：

• 尝试列出第三列，观察数值的变化规律

h[i][j]	j=1	j=2	j=3
i=0	0	0	0
i=1	1	1	1
i=2	2	2	2
i=3	3	2	2
i=4	4	3	3
i=5	5	3	3
i=6	6	3	3
i=7	7	4	3
i=8	8	4	4
i=9	9	4	4
i=10	10	4	4
…	…	…	…

• 举例：在填 h[4][3] 时，根据规则，j=2这一列从i=0开始向下看，j=3这一列从i=2开始向上看，先比较 h[0][2] 和 h[3][3]，再分别比较 h[1][2] 与 h[2][3]，h[2][2] 与 h[1][3]，h[3][2] 与 h[0][3]，最大值都是2，加1后是3。所以 h[4][3] 填3。

• 接下来用相同的方法填 h[5][3]，h[6][3]，h[7][3] 都是3。

• 填 h[8][3] 时就是4了，正是因为当填 h[8][3] 时，j=2这一列i从0到4值是0,1,2,2。j=3这一列i从7到4的值为3,3,3,3，最大值都为3，加1后是4。

• 设想 j=4 时，i从0到7，h[i][4] 的值与 h[i][3] 的值都相同，那么从 h[8][4] 开始，随着 i 的增大，需要填一些4，那么什么时候应该填5呢，需要让每个数对的最大值都是4，前面 h[0][3] 到 h[7][3] 是0,1,2,2,3,3,3,3，共8个数字，需要与后面8个数字4配对，这8个数字的位置应该为 h[15][4] 到 h[8][4]，这样最大值都是4，接下来 h[8][3] 往下都是4，与 j=4 的一列较小值配对，最大值都是4。

• 因此第一个填5的位置应该是 h[16][4]，在它前面一共有8个4。

• j是2时确定了有2个2，j是3时确定了有4个3，j是4时就能确定有8个4，…，在j=100时，各项数值一定都已经进行了充分的计算，计算后，一列之中应该有1个0，1个1，2个2，4个3，8个4，16个5，32个6，64个7，…

• 列举出每个数字第一次出现的位置：
  h[1][100]=1
h[2][100]=2
h[4][100]=3
h[8][100]=4
h[16][100]=5
h[32][100]=6
h[64][100]=7
h[128][100]=8

• 因此 h[100][100] 的值为7。

【其他解法】

• 本题的原题实质是信息学奥赛一本通 1300：鸡蛋的硬度 | OpenJudge NOI 2.6 7627:鸡蛋的硬度，除非你做过这一问题，能通过看代码得知这是个扔鸡蛋问题，否则很难在考场上就能从扔鸡蛋的角度来思考这一问题。
• 该题求的是最坏情况下最少扔鸡蛋的次数。
• 在了解这个代码是扔鸡蛋问题后，第26题解法为：
• 只有2个鸡蛋，设最坏情况下扔鸡蛋测出楼层高度最少需要扔x次
• 第一次最高也只能在第x层，如果在更高层扔，如果鸡蛋碎了，那么剩下1个鸡蛋在扔x-1次未必能测出鸡蛋硬度。
• 在第x层扔，如果碎了，那么剩下一个鸡蛋从第1层开始扔，如果没碎，就在第2层扔，不断升高楼层，当鸡蛋在第i层碎了时，鸡蛋硬度为i-1。
• 第一次在第x层扔鸡蛋如果没碎，那么剩下x-1次机会，楼层数是20-x，确定鸡蛋的硬度。
• 接下来在第x + x - 1层扔鸡蛋，如果没碎，那么剩下x-2次机会，楼层数是20-x-(x-1)，确定鸡蛋的硬度。
• 为了确定鸡蛋在20层楼内的硬度，需要

  $x + (x - 1) + (x - 2) + \cdots + 1 \geq 20$

• 即

  $\frac{(1 + x) \cdot x}{2} \geq 20$

• x是整数，可以取到的最小值为6。
• 第27题，100层楼有100个鸡蛋，确定鸡蛋硬度，鸡蛋足够了，就可以用二分查找的方法确定鸡蛋的硬度，二分查找最大比较次数为

  $\lfloor \log_2 100 \rfloor + 1 = 7$

---

CSP-J 2022 入门级 第一轮 第18题

题目：阅读程序

#include <iostream>       // 引入输入输出流库

using namespace std;      // 使用标准命名空间

int n, k;                 // 定义两个全局变量n和k

int solve1()              // 定义函数solve1，用于求解一个整数值
{
    int l = 0, r = n;     // 初始化l和r，分别表示左边界和右边界
    while (l <= r) {      // 使用二分法进行查找
        int mid = (l + r) / 2; // 计算中间值mid
        if (mid * mid <= n) l = mid + 1; // 如果mid的平方小于等于n，移动左边界
        else r = mid - 1;  // 否则移动右边界
    }
    return l - 1;          // 返回满足条件的最大mid值
}

double solve2(double x)    // 定义函数solve2，用于近似求解平方根
{
    if (x == 0) return x;  // 若x为0，直接返回
    for (int i = 0; i < k; i++) // 循环k次
        x = (x + n / x) / 2; // 更新x的值，逼近平方根
    return x;               // 返回近似的平方根
}

int main()                // 主函数
{
    cin >> n >> k;         // 输入n和k的值
    double ans = solve2(solve1()); // 先调用solve1，再将结果传给solve2
    cout << ans << ' ' << (ans * ans == n) << endl; // 输出ans及其平方是否等于n
    return 0;              // 程序结束
}

假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、 k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

判断题

1. 该算法最准确的时间复杂度分析结果为 𝑂(log 𝑛 + 𝑘)。（ ）
2. 当输入为“9801 1”时，输出的第一个数为“99” 。（ ）
3. 对于任意输入的 n ，随着所输入 k 的增大，输出的第二个数会变成“1” 。（ ）
4. 该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ）

单选题

1. 当输入为“2 1”时，输出的第一个数最接近（ ）。

   • A. 1
   • B. 1.414
   • C. 1.5
   • D. 2

2. 当输入为“3 10”时，输出的第一个数最接近（ ）。

   • A. 1.7
   • B. 1.732
   • C. 1.75
   • D. 2

3. 当输入为“256 11”时，输出的第一个数（ ）。

   • A. 等于 16
   • B. 接近但小于 16
   • C. 接近但大于 16
   • D. 前三种情况都有可能

---

题目考点

1. 二分查找

   • 本题考察了二分查找的应用，通过二分查找求解一个整数值。
   • 二分查找是一种高效的查找算法，适用于有序的数据集合。

2. 牛顿迭代法

   • 本题还考察了牛顿迭代法的应用，通过牛顿迭代法近似求解平方根。
   • 牛顿迭代法是一种求解方程近似解的方法，通过不断迭代逼近方程的根。

解题思路

观察 solve1 函数，明显是二分答案算法。

• 满足 mid * mid <= n 时，l = mid + 1 取右半边。
• 最后取 l - 1，由于 l 都是 mid + 1，所以最后取到的是满足条件的 mid。
• 可以看出，这个二分答案求的是：满足 mid * mid <= n 条件的，mid 的最大值。
• 实际就是求 ⌊√n⌋。

至于 solve2 函数：

• 传入的 x 是 ⌊√n⌋。
• 当 √n 不是整数时，n / x 是个略大于 √n 的数字。
• ⌊√n⌋ 与 n / x 二者取平均数后的值赋值给 x，x 变得更接近 √n。
• 重复这一过程，会使 x 不断逼近 √n。

判断题解析

1. 该算法最准确的时间复杂度分析结果为 O(log n + k)。（ ）

• 答：正确。
  • solve1 函数采用二分算法，二分查找的范围为 n，时间复杂度为 O(log n)。
  • solve1 函数计算出的结果传递给 solve2 函数。solve2 函数中包含 k 次循环，因此复杂度为 O(k)。
  • 所以整体复杂度为 O(log n + k)。

2. 当输入为“9801 1”时，输出的第一个数为“99”。（ ）

• 答：正确。
  • solve1 函数计算得到 ⌊√9801⌋ = 99。
  • 在 solve2 函数中，x = 99，k = 1，for 循环执行一次，计算得到 x = (x + n/x) / 2 = (99 + 9801/99) / 2 = 99。
  • 因此输出的 ans 为 99。

3. 对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。（ ）

• 答：错误。
  • 随着输入 k 的增大，输出的第二个数会接近或等于 √n。

4. 该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ）

• 答：错误。
  • 题目限定了 n 最大为 47000，第一次计算 mid = n/2 为 23500，此时 mid * mid = 23500^2 = 552250000，这个数可以用 int 类型表示，不会溢出。
  • （如果考虑 n 超过题目限定的 47000，那么即使将 mid 转为 64 位整数，在 n 极大时仍可能溢出。）

单选题解析

1. 当输入为“2 1”时，输出的第一个数最接近（ ）。

• A. 1
• B. 1.414
• C. 1.5
• D. 2
• 答：选 C。
  • solve1 函数传入 2，求出结果为 ⌊√2⌋ = 1。
  • 将 1 传入 solve2，x = 1，循环 1 次，计算 x = (x + n/x) / 2 = (1 + 2/1) / 2 = 1.5，函数的返回值，即 ans 的值为 1.5。

2. 当输入为“3 10”时，输出的第一个数最接近（ ）。

• A. 1.7
• B. 1.732
• C. 1.75
• D. 2
• 答：选 B。

  • solve1 函数传入 3，求出结果为 ⌊√3⌋ = 1。

  • 将 1 传入 solve2，x = 1，循环 10 次，每次循环后 x 的值如下：

    k	x
    0	2
    1	1.75
    2	1.732
    3	1.732

  • 之后无需继续计算，已知 x 最终会不断接近 √3，多次循环后结果的前几位将稳定在 1.732，不会改变。

3. 当输入为“256 11”时，输出的第一个数（ ）。

• A. 等于 16
• B. 接近但小于 16
• C. 接近但大于 16
• D. 前三种情况都有可能
• 答：选 A。
  • solve1 的结果为 ⌊√256⌋ = 16，已知 √256 = 16。
  • 在 solve2 中，x = (x + n/x) / 2 = (16 + 256/16) / 2 = 16，每次计算后 x 的值不变，均为 16。
  • 因此最后输出的值等于 16。

---

CSP-J 2022 入门级 第一轮 第19题

题目：补全程序

问题描述:
编写一个程序，从小到大打印正整数 n 的所有正因数，并补全程序中的空白部分。

#include <bits/stdc++.h>       // 引入所有C++标准库头文件
using namespace std;           // 使用标准命名空间

int main() {                   // 主函数
    int n;                     // 定义整数变量n
    cin >> n;                  // 输入n的值

    vector<int> fac;           // 定义一个保存因数的向量fac
    fac.reserve((int)ceil(sqrt(n)));  // 预先分配fac的容量为√n向上取整

    int i;                     // 定义整数变量i，用于循环
    for (i = 1; i * i < n; ++i) {  // 循环找到所有小于√n的因数
        if (n % i == 0) {       // 如果i是n的因数
            fac.push_back(i);   // 将i添加到因数向量fac中
        }
    }

    for (int k = 0; k < fac.size(); ++k) {  // 输出向量fac中存储的小于√n的因数
        cout << fac[k] << " ";  // 输出第k个因数
    }
    if (i * i == n) {           // 如果n是完全平方数，则输出√n
        cout << i << " ";       // 输出√n
    }
    for (int k = fac.size() - 1; k >= 0; --k) {  // 反向输出大于√n的因数
        cout << n / fac[k] << " ";  // 输出n除以fac[k]得到的因数
    }
}

选择题

在代码中的空白处填入合适的表达式：

1. ① 处应填（）

   • A. n % i == 0
   • B. n % i == 1
   • C. n % (i-1) == 0
   • D. n % (i-1) == 1

2. ② 处应填（）

   • A. n / fac[k]
   • B. fac[k]
   • C. fac[k]-1
   • D. n / (fac[k]-1)

3. ③ 处应填（）

   • A. (i-1) * (i-1) == n
   • B. (i-1) * i == n
   • C. i * i == n
   • D. i * (i-1) == n

4. ④ 处应填（）

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

5. ⑤ 处应填（）

   • A. n / fac[k]
   • B. fac[k]
   • C. fac[k]-1
   • D. n / (fac[k]-1)

题目考点

1. STL vector

   • 声明 vector 对象：vector<数据类型> 对象名
   • 例：vector<int> vec;
   • （以下示例中vec表示vector对象）

   容量管理:

   • vec.capacity() 返回 vec 的容量。
     容量指当前已经分配给该对象的内存空间。vector 对象会根据保存数据的数量自动改变自身的容量。当元素数量增加时，会让容量依次变为1，2，4，8，16…，但在元素减少时不会自动减少容量。
   • vec.reserve(容量)，手动设置 vector 的容量，预先为 vector 对象分配空间，以免在运行过程中触发扩容。

2. 因数

   • 因数指能够整除某个整数的数。例如，整数 n 的因数是能够被 n 整除的所有整数。

解题思路

• 输入部分

  int n;                     // 定义整数变量n
  cin >> n;                  // 输入n的值
  vector<int> fac;           // 定义一个保存因数的向量fac
  fac.reserve((int)ceil(sqrt(n)));  // 预先分配fac的容量为√n向上取整
  

  先输入了 n，第8行声明了一个 vector 类对象，名字为 fac 。factor是因数的意思，所以fac这个vector保存的是因数。第9行使用 ceil 向上取整（返回值类型是double），sqrt 是开根号运算，将第9行做的事情是把fac的容量设为⌈√n⌉。

• 枚举因数部分

  int i;                     // 定义整数变量i，用于循环
  for (i = 1; i * i < n; ++i) {  // 循环找到所有小于√n的因数
      if (n % i == 0) {       // 如果i是n的因数 ① 
          fac.push_back(i);   // 将i添加到因数向量fac中
      }
  }
  

  枚举 n 的所有小于 √n 的因数。就是把n的所有$i^2$ < n的因数保存在fac之中。
  如果 i 是 n 的因数，则 n 能整除 i，即 n % i == 0。
  因此，① 选择 A：n % i == 0。

• 打印因数部分

  for (int k = 0; k < fac.size(); ++k) {  // 输出向量fac中存储的小于√n的因数
      cout << fac[k] << " ";  // 输出第k个因数  ②
  }
  

  为了从小到大打印 n 的所有因数，先输出保存在 fac 中的小于 √n 的因数。此处输出 fac 中的第 k 个元素：fac[k]。
  因此， ② 选择 B：fac[k]。

• 判断并打印平方数因数

  if (i * i == n) {           // 如果n是完全平方数，则输出√n ③
      cout << i << " ";       // 输出√n ④
  }
  

  接着是看是否有i^2=n的情况，如果有则输出i。
  因此，③ 选择 C：i * i == n，④ 选择 D：i。

• 打印大于 √n 的因数

  for (int k = fac.size() - 1; k >= 0; --k) {  // 反向输出大于√n的因数
      cout << n / fac[k] << " ";  // 输出n除以fac[k]得到的因数 ⑤
  }
  

  最后输出$i^2$>n的n的因数i。如果 fac 中的元素为 a, b, c, d，则接下来输出 n/d, n/c, n/b, n/a。
  fac中的元素为：fac[0], fac[1], …, fac[fax.size()-1]，接下来应该输出的是:n/fac[fax.size()-1], n/fac[fax.size()-2], …, n/fac[0]。 因此，⑤ 选择 A：n / fac[k]。

---

CSP-J 2022 入门级 第一轮 第20题

题目：补全程序

问题描述:
（洪水填充）现有一个用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同）替换为给定的颜色。请补全程序。

#include <bits/stdc++.h>       // 引入所有C++标准库头文件
using namespace std;           // 使用标准命名空间

const int ROWS = 8;            // 定义常量行数为8
const int COLS = 8;            // 定义常量列数为8

struct Point {                 // 定义Point结构体表示一个点
    int r, c;                  // r为行，c为列
    Point(int r, int c) : r(r), c(c) {}  // 构造函数初始化列表
};

bool is_valid(char image[ROWS][COLS], Point pt, int prev_color, int new_color) {
    int r = pt.r;              // 获取点的行号
    int c = pt.c;              // 获取点的列号
    return (0 <= r && r < ROWS && 0 <= c && c < COLS &&  // 检查点是否在图像内
            ① && image[r][c] != new_color);  // 检查点是否满足颜色条件
}

void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
    queue<Point> queue;        // 定义一个队列存储待处理的点
    queue.push(cur);           // 将当前点加入队列

    int prev_color = image[cur.r][cur.c];  // 获取当前点的初始颜色
    ② ;                       // 修改当前点的颜色

    while (!queue.empty()) {   // 当队列不为空时，继续处理
        Point pt = queue.front();  // 获取队首元素
        queue.pop();           // 将队首元素出队

        Point points[4] = { ③ , Point(pt.r - 1, pt.c),  // 存储上下左右四个相邻点
                             Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
        for (auto p : points) {  // 遍历四个相邻点
            if (is_valid(image, p, prev_color, new_color)) {  // 判断点是否合法
                ④ ;           // 修改点的颜色
                ⑤ ;           // 将点加入队列
            }
        }
    }
}

int main() {                  // 主函数
    char image[ROWS][COLS] = {  // 定义一个8x8字符数组表示图像
        {'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
        {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
        {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
        {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
        {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
        {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
        {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
        {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}
    };

    Point cur(4, 4);           // 定义初始点为(4, 4)
    char new_color = 'y';      // 定义新的颜色为黄色

    flood_fill(image, cur, new_color);  // 调用洪水填充函数

    for (int r = 0; r < ROWS; r++) {  // 输出填充后的图像
        for (int c = 0; c < COLS; c++) {
            cout << image[r][c] << " ";  // 输出每个像素的颜色
        }
        cout << endl;
    }
    return 0;
}

选择题

在代码中的空白处填入合适的表达式：

1. ① 处应填（）

   • A. image[r][c] == prev_color
   • B. image[r][c] != prev_color
   • C. image[r][c] == new_color
   • D. image[r][c] != new_color

2. ② 处应填（）

   • A. image[cur.r+1][cur.c] = new_color
   • B. image[cur.r][cur.c] = new_color
   • C. image[cur.r][cur.c+1] = new_color
   • D. image[cur.r][cur.c] = prev_color

3. ③ 处应填（）

   • A. Point(pt.r, pt.c)
   • B. Point(pt.r, pt.c+1)
   • C. Point(pt.r+1, pt.c)
   • D. Point(pt.r+1, pt.c+1)

4. ④ 处应填（）

   • A. prev_color = image[p.r][p.c]
   • B. new_color = image[p.r][p.c]
   • C. image[p.r][p.c] = prev_color
   • D. image[p.r][p.c] = new_color

5. ⑤ 处应填（）

   • A. queue.push(p)
   • B. queue.push(pt)
   • C. queue.push(cur)
   • D. queue.push(Point(ROWS,COLS))

题目考点

1. 广搜
   使用广度优先搜索（BFS）解决连通块问题。广搜适合在二维图像或网格中寻找相邻区域或路径。

2. auto关键字 使用 auto 关键字可以让编译器自动确定变量的类型。例如：

   • auto p = 3.2;（auto 相当于 double）
   • vector<int> vec; auto it = vec.begin();（auto 相当于 vector<int>::iterator）

3. for 冒号语法 用于遍历一个可迭代对象中的所有元素，如数组或 STL 容器。例如：

   for (元素类型 变量名 : 可迭代对象) {
       // 循环体
   }
   

   使用 auto 可以自动设置元素类型。对于需要修改的遍历，可以使用引用遍历：

   for (元素类型 &变量名 : 可迭代对象) {
       // 修改元素
   }
   

解题思路

该题是连通块问题。看代码可知，题目使用了广搜算法。

• 数据定义部分

  const int ROWS = 8;            // 定义常量行数为8
  const int COLS = 8;            // 定义常量列数为8
  struct Point {                 // 定义Point结构体表示一个点
      int r, c;                  // r为行，c为列
      Point(int r, int c) : r(r), c(c) {}  // 构造函数初始化列表
  }
  

  ROWS 和 COLS 分别定义了图像的行数和列数，Point 结构体用于表示图像中的一个像素点，其成员变量 r 和 c 分别代表该像素的行号和列号。
  Point(int r, int c):r(r),c(c){}是构造函数成员初始化列表的写法，意思是在调用构造函数时，将传入的第一个参数赋值给成员变量r，第二个参数赋值给成员变量c。
  接下来的is_valid函数在调用时再看。

• 颜色填充的广搜部分

  void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
      queue<Point> queue;        // 定义一个队列存储待处理的点
      queue.push(cur);           // 将当前点加入队列
      int prev_color = image[cur.r][cur.c];  // 获取当前点的初始颜色
      image[cur.r][cur.c] = new_color;  // 修改当前点的颜色 ②
  

  flood_fill 函数使用广度优先搜索（BFS）算法来实现颜色填充。首先将起始点加入队列，并将其颜色修改为 new_color。

  • 函数名是：洪水填充，看函数内的结构就能看出用了广搜算法。
  • 先设队列，而后初始结点入队。
  • cur是起始位置，prev_color就是起始位置的颜色。
  • 该题要做的是将包含起始位置的连通块的颜色从原颜色(prev_color)变为新颜色(new_color)。
  • 初始位置已经入队了，初始位置应该改变颜色。
  • 看第②空，可知这里要写的是使初始位置改变颜色，初始位置是(cur.r, cur.c)，所以应该写：image[cur.r][cur.c] = new_color，选B。

• 遍历四个相邻点

      while (!queue.empty()) {   // 当队列不为空时，继续处理
          Point pt = queue.front();  // 获取队首元素
          queue.pop();           // 将队首元素出队
          Point points[4] = { Point(pt.r + 1, pt.c), Point(pt.r - 1, pt.c),  // 存储上下左右四个相邻点 ③
                              Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
          for (auto p : points) {  // 遍历四个相邻点
              if (is_valid(image, p, prev_color, new_color)) {  // 判断点是否合法
                  image[p.r][p.c] = new_color;  // 修改点的颜色 ④
                  queue.push(p);           // 将点加入队列 ⑤
              }
          }
      }
  

  • 接着开始循环，只要队列不空，每次循环出队一个位置pt。接下来确定pt位置上下左右的四个位置，保存在points数组中。
  • Point(pt.r - 1, pt.c)是pt上方位置
  • Point(pt.r, pt.c + 1)是pt右侧位置
  • Point(pt.r, pt.c - 1)是pt左侧位置
  • 还缺下方位置，应该是Point(pt.r+1, pt.c)。
  • 第③空应该选C。
  • 接下来遍历points数组，这里用到了for冒号的写法，遍历points数组中的每个元素。
  • 在循环内，先判断pt位置是否合法，判断函数为is_valid

• 判断点是否合法

  bool is_valid(char image[ROWS][COLS], Point pt, int prev_color, int new_color) {
      int r = pt.r;              // 获取点的行号
      int c = pt.c;              // 获取点的列号
      return (0 <= r && r < ROWS && 0 <= c && c < COLS &&  // 检查点是否在图像内
              image[r][c] == prev_color && image[r][c] != new_color);  // 检查点是否满足颜色条件 ①
  }
  

  is_valid 函数用于检查某点是否在图像范围内、颜色是否与起始颜色相同且未被填充。

  • 传入的image为图像二维数组，pt为被判断是否合法的位置，prev_color为起始位置颜色，new_color为要改变为的新颜色。
  • 这里r，c为pt的行号和列号，首先0 <= r && r < ROWS && 0 <= c && c < COLS判断pt位置需要在地图内，image[r][c] != new_color表示新位置的颜色应该不与新颜色相同（如果与新颜色相同，说明这里已经变色了），还差一点需要填空。由于要把与起始位置颜色相同的在同一连通块内的位置都变色，因此这里需要与起始位置颜色相同，才是合法的，才需要进行变色。所以①这里应该填image[r][c] == prev_color，选A。

• 修改点的颜色

      if (is_valid(image, p, prev_color, new_color)) {  // 判断点是否合法
          image[p.r][p.c] = new_color;  // 修改点的颜色 ④
          queue.push(p);           // 将点加入队列 ⑤
      }
  

  • 回到这里，如果该位置合法，那么按照广搜模板，这里应该访问p位置，然后pt位置入队。
  • 这里所谓的访问，应该是将p位置设为新颜色:image[p.r][p.c] = new_color，第④空选D。
  • 而后把新位置p入队:que.push(p)，选A。