CSP-S 提高级 · CSP 2020 提高级第一轮 第 16 题

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 $1.5$ 分，选择题 $3$ 分，共计 $40$ 分）

1.

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

• 判断题

1. $n$ 必须小于 $1000$,否则程序可能会发生运行错误。（ ）

2. 输出一定大于等于 $0$。（ ）

3. 若将第 13 行的 j=0 改为 j = i + 1 程序输出可能会改变。 （ ）

4. 将第 14 行的 d[i] < d[j] 改为 d[i] != d[j]，程序输出不会改变。（ ）

• 单选题

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

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

这题核心是把 d[i]+d[j]-(d[i]&d[j]) 认出是 d[i]|d[j]，程序就在求数组里任意两个不同数按位或的最大值。审题先抓数组定义和循环条件，再结合二进制特征判断输出范围，就能快速排除错误选项。

很多学生容易把 a+b-(a&b) 硬算成普通加法，忽略位运算恒等式；或者死记数组大小是 1000 就以为 n 必须小于 1000，没注意题目给的输入范围是 10000；还有人会误以为输出一定是非负的，忘了 ans 初始化为 -1 且当所有元素相等时确实会输出 -1。

考点与概念

本题主要考查位运算（按位与、按位或）以及程序逻辑分析。关键恒等式是： $$a+b-(a\&b)=a|b$$

简单理解：两个数相加时，二进制位上如果都是 1，会产生进位（和为 2），而按位与只保留这一位的 1（和为 1），差值正好是进位贡献的 1；如果一位是 1 一位是 0，和与按位与都是 1，差为 0。所以把“和”减去“按位与”，剩下的就是“按位或”的结果。

程序功能推导

原代码逻辑：

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]));

1. 外层循环枚举所有 $i$，内层循环枚举所有 $j$，构成了 $n^2$ 次比较。 2. 条件 $d[i] < d[j]$ 保证了只处理“不同且有序”的数对。 3. 计算 $d[i]+d[j]-(d[i]\&d[j])$ 根据恒等式等价于 $d[i]|d[j]$。 4. ans 初始化为 -1，不断取最大值。

结论：程序输出的是数组中任意两个不同元素按位或的最大值。如果所有元素都相等，没有任何 $d[i]<d[j]$ 成立，ans 保持 -1。