CSP-S 2020 第一轮 第21题：若输出的数大于θ，则下面说法正确的是（）

题目

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> d[i];
  int ans = -1;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (d[i] < d[j])
         ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

  假设输入的 $n$ 和 $d[i]$ 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题：

若输出的数大于 $0$，则下面说法正确的是(  ）。

选项

• A. 若输出为偶数，则输入的 $d[i]$ 中最多有两个偶数
• B. 若输出为奇数，则输入的 $d[i]$ 中至少有两个奇数
• C. 若输出为偶数，则输入的 $d[i]$ 中至少有两个偶数
• D. 若输出为奇数，则输入的 $d[i]$ 中最多有两个奇数

答案

C

题解

答案是 C。

关键是看懂这个表达式： \[ d[i]+d[j]-(d[i]\&d[j])=d[i]\mid d[j] \] 其中 & 是按位与，| 是按位或。因为两个数相加，等于它们的“按位或”加上“按位与”。

所以，程序求的是：从数组中选取两个值不同的数，求它们按位或的最大值。输出大于 \(0\)，说明至少有一对数满足条件。

再看二进制的最低位：

• 偶数的最低位是 0，奇数的最低位是 1。
• 按位或的结果为偶数，最低位必须是 0，因此参与运算的两个数都必须是偶数。
• 按位或的结果为奇数，只需其中至少一个数为奇数。

因此，若输出为偶数，取得这个最大值的两个数一定都是偶数，输入中至少有两个偶数，C 正确。

其余选项可以用反例排除：