CSP-S 2020 第一轮 第20题：若输入n为100，且输出为 127，则输入的 d[i]中不可能有（）

题目

#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$ 的正整数，完成下面的判断题和单选题：

若输入 $n$ 为 $100$，且输出为 $127$，则输入的 $d[i]$ 中不可能有（  ）。

选项

• A. 127
• B. 126
• C. 128
• D. 125

答案

C

题解

答案是 C. 128。

关键是看懂这句： ``cpp d[i] + d[j] - (d[i] & d[j]) `` 利用位运算恒等式 \[ a+b=(a\mid b)+(a\&b), \] 原式等于 \(a\mid b\)，即 按位或。

因此，程序求的是：所有数值不同的两个输入数，按位或的最大值。条件 d[i] < d[j] 保证两数不同。

为什么不能有 \(128\)？

• \(128\) 的二进制是 10000000，它与任意正整数按位或，结果都至少是 \(128\)。
• 如果输入中有 \(128\)，且还有不同于它的数，这两个数就会参与计算，使输出至少为 \(128\)，不可能是 \(127\)。
• 如果所有数都是 \(128\)，条件始终不成立，输出为初始值 \(-1\)，也不是 \(127\)。

其他三个选项则可以同时出现： ``text 127 = 01111111 126 = 01111110 125 = 01111101 `` 它们中任意两个不同的数按位或，结果都是 \(127\)。输入这三个数，再重复其中的数补足 \(100\) 个，输出就是 \(127\)。