CSP-S 2024 第一轮 第20题：当输入为 10 100 100 时，输出的第 100 个数是

题目

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

当输入为 10 100 100 时，输出的第 $100$ 个数是？（  ）

选项

• A. 91
• B. 94
• C. 95
• D. 98

答案

C

题解

答案是 C．95。

1. 化简 logic(x, y)

~x & y 中为 1 的位，在 x ^ y 中也一定为 1，所以： ``cpp (x ^ y) | (~x & y) == (x ^ y) ` 而 x & y 表示两者都为 1 的位，x ^ y 表示两者不同的位，两部分合起来就是按位或： `cpp logic(x, y) == (x | y) ` 因此生成的数组为： `cpp c[i] = (10 | i) % 101; // i = 0, 1, ..., 99 ``

2. 判断排序后的第 100 个数

recursion 是快速排序的划分过程，递归深度 100 足够将这 100 个数按升序排好。因此，第 100 个数就是数组的最大值。

3. 求最大值，注意取模

10 的二进制为 00001010，按位或相当于把对应的两位设为 1。

• 当 0 ≤ i ≤ 95 时，10 | i ≤ 95，且 i = 95 时恰好等于 95，取模后仍为 95。
• 当 i = 96, 97, 98, 99 时，10 | i 分别为 106, 107, 106, 107，模 101 后为 5, 6, 5, 6。

所以最大值为 95，选 C。