当前位置：首页 > ds >正文

CSP 2024 提高级第一轮（CSP-S 2024）阅读程序第一题解析

ds 2025/8/26 18:47:48

阅读程序第一题解析

#include <iostream>
using namespace std;const int N = 1000;
int c[N];int logic(int x, int y) {return (x & y) ^ ((x ^ y) | (~x & y));
}void generate(int a, int b, int *c) {for (int i = 0; i < b; i++)c[i] = logic(a, i) % (b + 1);
}void recursion(int depth, int *arr, int size) {if (depth <= 0 || size <= 1) return;int pivot = arr[0];int i = 0, j = size - 1;while (i <= j) {while (arr[i] < pivot) i++;while (arr[j] > pivot) j--;if (i <= j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++; j--;}}recursion(depth - 1, arr, j + 1);recursion(depth - 1, arr + i, size - i);
}int main() {int a, b, d;cin >> a >> b >> d;generate(a, b, c);recursion(d, c, b);for (int i = 0; i < b; ++i) cout << c[i] << " ";cout << endl;
}

程序分析

`logic`函数

int logic(int x, int y) {return (x & y) ^ ((x ^ y) | (~x & y));
}

我们列举一些x和y，发现(x & y) ^ ((x ^ y) | (~x & y))等同于x | y：

x	y	(x & y) ^ ((x ^ y) \| (~x & y))	x \| y
0	3	3	3
0	7	7	7
0	8	8	8
1	7	7	7
2	1	3	3

用C++证明：

`generate`函数

void generate(int a, int b, int *c) {for (int i = 0; i < b; i++)c[i] = logic(a, i) % (b + 1);
}

函数行为：

传入a，b（确保 c[i] 的值在 [0, b] 范围内），c数组。
循环，从0到b。
- 把a | i % (b + 1）赋值给c[i]。

`recursion`函数

void recursion(int depth, int *arr, int size) {if (depth <= 0 || size <= 1) return;int pivot = arr[0];int i = 0, j = size - 1;while (i <= j) {while (arr[i] < pivot) i++;while (arr[j] > pivot) j--;if (i <= j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;i++; j--;}}recursion(depth - 1, arr, j + 1);recursion(depth - 1, arr + i, size - i);
}

recursion函数是一个带深度限制的快速排序的实现，排完序后数组不完全有序。（快速排序运用了分治的思想，每次找到一个任意下标的数，将小于该数的数放于左边，大于该数的数放于右边）。

判断题

当1000≥d≥b 时，输出的序列是有序的。（正确）
解析：最坏情况下，快速排序的递归深度可能达到 b（退化为 O(n²)）。
但题目保证 d≥b，因此递归不会提前终止，最终数组会被完全排序。
当输入 5 5 1 时，输出为 1 1 5 5 5。（错误）
解析：
generate(a = 5, b = 5, c)：
c[i] = (5 | i) % 6

i	5 \| i（二进制）	5 \| i（十进制）	c[i] = (5 \| i) % 6
0	101 \| 000 = 101	5	5 % 6 = 5
1	101 \| 001 = 101	5	5 % 6 = 5
2	101 \| 010 = 111	7	7 % 6 = 1
3	101 \| 011 = 111	7	7 % 6 = 1
4	101 \| 100 = 101	5	5 % 6 = 5

c = {5, 5, 1, 1, 5}
recursion()：

来自DeepSeek的《睿智》
第1层递归（d=1）：
基准值 pivot = c[0] = 5。
分区过程：
i=0，j=4：
c[0]=5（>=5，不移动 i）
c[4]=5（<=5，不移动 j）
交换 c[0] 和 c[4]（数组不变，仍为 [5, 5, 1, 1, 5]）
i++ → i=1，j-- → j=3
i=1，j=3：
c[1]=5（>=5，不移动 i）
c[3]=1（<=5，不移动 j）
交换 c[1] 和 c[3] → 数组变为 [5, 1, 1, 5, 5]
i++ → i=2，j-- → j=2
i=2，j=2：
c[2]=1（<5，i++ → i=3）
c[2]=1（<=5，不移动 j）
循环终止（i > j）
分区结果：
左子数组：[5, 1, 1]（j + 1 = 3）
右子数组：[5, 5]（arr + i = c + 3，size - i = 2）
递归深度 d=0，不再继续递归。

假设数组 c 长度无限制，该程序所实现的算法的时间复杂度是 O(b) 的。（错误）
解析：recursion()函数的复杂度不是O(b)，若不考虑深度限制，平均复杂度是O(b log b)。

选择题

函数 int logic(int x, int y) 的功能是（B）
A. 按位与
B. 按位或
C. 按位异或
D. 以上都不是
解析：我们列举一些x和y，发现(x & y) ^ ((x ^ y) | (~x & y))等同于x | y：

x	y	(x & y) ^ ((x ^ y) \| (~x & y))	x \| y
0	3	3	3
0	7	7	7
0	8	8	8
1	7	7	7
2	1	3	3

当输入为 10 100 100 时，输出的第 100 个数是？（C）
A. 91
B. 94
C. 95
D. 98
解析：最坏情况下，快速排序需要n - 1重递归，而100 > 100 - 1，所以函数执行完毕c数组已经有序，答案就是(10 | i) % 101 i ∈ [0, 99]的最大值。
10的二进制形式为：1010，所以与10相或必定第一位和第三位为1（从右起）。