B4261 [GESP202503 三级] 2025

chen_zhe · 2025-05-09 21:44:00 · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

本题考察枚举、位运算。

首先先介绍一种笨办法——枚举法。题目中的 x 是给出的，而且要求 y 是正整数，这样我们可以使用一重循环去枚举 y，对每一个 y，计算题目中的算式是否成立。注意，\operatorname{and} 在 C++ 中是 &，而 \operatorname{or} 在 C++ 中是 |。参考代码：

for (int i = 1; i <= 2025; i++){
    if ((x & i) + (x | i) == 2025) {
        cout << i << endl;
        return 0;
    }
}

这种做法足够通过本题。但是我们再介绍一种巧妙方法。题目中的 (x \ \operatorname{and} \ y) + (x \ \operatorname{or} \ y) 这个式子，实则与 x+y 是一致的！

这是为什么呢？我们把 x,y 拆成二进制数，对每一个数位（假设分别是 a 和 b）分别研究，可以得到下列情况：

• 情况 1：a 是 0，b 也是 0，此时 a \operatorname{and} b=0，a \operatorname{or} b=0，a + b = 0；
• 情况 2：a 是 0，b 是 1，此时 a \operatorname{and} b=0，a \operatorname{or} b=1，即 (a \operatorname{and} b) + (a \operatorname{or} b) = 1，而 a + b = 1，两者相等；
• 情况 3：a 是 1，b 是 0，此时与情况 2 完全一致；
• 情况 4：a 是 1，b 也是 1，此时 a \operatorname{and} b=1，a \operatorname{or} b=1，即 (a \operatorname{and} b) + (a \operatorname{or} b) = 2，而 a + b = 2，两者相等；

在每一个位置上，(a \ \operatorname{and} \ b) + (a \ \operatorname{or} \ b) = a + b，因此对于整体来看计算结果也是一样的。

因此题目就变为了：已知 x+y=2025 和 x，求出 y 是多少。那么这个问题就非常简单了，直接输出 2025-x 即可。代码略。