CSP-S 2024 第一轮 第17题：当输入"551"时，输出为"11555"。

题目

#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;
}

当输入 5 5 1 时，输出为 1 1 5 5 5。（  ）

选项

• T. 正确
• F. 错误

答案

F

题解

选 F（错误）。实际输出为：

``text 5 1 1 5 5 ``

先化简 logic(x, y)：

``cpp (x ^ y) | (~x & y) == (x ^ y) ``

因为 ~x & y 中为 1 的位，在 x ^ y 中也一定为 1。因此：

``cpp logic(x, y) == (x & y) ^ (x ^ y) == (x | y) ``

所以 generate(5, 5, c) 生成的数组是：

初始数组为 5 5 1 1 5。

接着执行 recursion(1, c, 5)，基准值 pivot = 5：

1. i = 0，j = 4：两端都等于 5，交换后数组不变；然后 i = 1，j = 3。
2. 交换 arr[1] = 5 和 arr[3] = 1，数组变为 5 1 1 5 5；然后 i = 2，j = 2。
3. 因为 arr[2] < 5，i 前进到 3；j 保持 2。此时 i > j，结束划分。

后续递归的 depth 都是 0，直接返回。这里只进行一轮划分，并未完成排序，所以题目中的输出不正确。