【GESP】C++三级真题 luogu-B4261 [GESP202503 三级] 2025

GESP三级真题，位运算相关问题，难度★★☆☆☆。

luogu-B4261 [GESP202503 三级] 2025

题目要求

题目描述

小 A 有一个整数 $x$，他想找到最小的正整数 $y$ 使得下式成立：

\[(x \ \operatorname{and} \ y) + (x \ \operatorname{or} \ y) = 2025\]

其中 $\operatorname{and}$ 表示二进制按位与运算，$\operatorname{or}$ 表示二进制按位或运算。如果不存在满足条件的 $y$，则输出 $-1$。

输入格式

一行，一个整数 $x$。

输出格式

一行，一个整数，若满足条件的 $y$ 存在则输出 $y$，否则输出 $-1$。

输入输出样例 #1

输入 #1

1025

输出 #1

1000

说明/提示

对于所有测试点，保证 $0 \leq x < 2025$。

\[(x \ \operatorname{and} \ y) + (x \ \operatorname{or} \ y) = 2025\]

其中：

• $\operatorname{and}$ 表示按位与运算，运算符为 $\&$。

• $\operatorname{or}$ 表示按位或运算，运算符为 $

  $。

---

题目分析

解题思路

本题的解题思路如下：

1. 问题分析：
   • 给定一个整数x，需要找到最小的正整数y
   • 满足条件：(x AND y) + (x OR y) = 2025
   • x的范围是[0, 2025)
2. 核心逻辑：
   • 从最小的正整数开始尝试，直到找到满足条件的y
   • 使用位运算计算AND和OR的结果
   • 判断两个运算结果之和是否等于2025
   • 如果找到满足条件的y则立即返回
   • 如果遍历到2025仍未找到，则返回-1
3. 实现要点：
   • 使用位运算符&计算AND

   • 使用位运算符

     计算OR

   • y的取值范围需要考虑以下几点：
     • y必须是正整数
     • y的上限不需要超过2025，因为题目要求和为2025
     • 考虑到位运算的特性，y的值不可能大于2025。因为：
       1. 对于任意两个数的按位与运算结果一定小于等于这两个数中的较小值
       2. 对于任意两个数的按位或运算结果一定大于等于这两个数中的较大值

       3. 已知x < 2025，如果y > 2025，则x & y < 2025且x

          y > 2025

       4. 这样(x & y) + (x

          y)必然大于2025，与题目要求不符

   • 注意及时退出循环以提高效率

复杂度分析：

• 时间复杂度：$O(N)$，其中N为2025，最坏情况下需要遍历到2025
• 空间复杂度：$O(1)$，只需要常数级别的变量存储空间

---

示例代码

#include <iostream>

int main() {
    // 声明变量x用于存储输入值
    int x;
    // 从标准输入读取x的值
    std::cin >> x;
    // 标记是否找到满足条件的y
    bool flag = false;
    // y从0开始尝试
    int y = 0;
    // 循环尝试所有可能的y值，直到2025（根据题目条件）
    while (y <= 2025) {
        // 检查是否满足 (x AND y) + (x OR y) = 2025
        if ((x & y) + (x | y) == 2025) {
            // 找到满足条件的y，设置标记为true
            flag = true;
            break;
        }
        y++;
    }
    // 根据是否找到满足条件的y输出结果
    if (flag) {
        // 找到则输出y的值
        std::cout << y;
    } else {
        // 未找到则输出-1
        std::cout << "-1";
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。