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$。

其中：

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

题目分析

解题思路

本题的解题思路如下：

1. 问题分析：

   • 给定一个整数 $x$，需要找到最小的正整数 $y$
   • 满足条件：$(x \ \operatorname{and} \ y) + (x \ \operatorname{or} \ y) = 2025$
   • $x$ 的范围是 $[0, 2025)$

2. 核心逻辑：

   • 从最小的正整数开始尝试，直到找到满足条件的 $y$
   • 使用位运算计算 $\operatorname{and}$ 和 $\operatorname{or}$ 的结果
   • 判断两个运算结果之和是否等于 $2025$
   • 如果找到满足条件的 $y$ 则立即返回
   • 如果遍历到 $2025$ 仍未找到，则返回 $-1$

3. 实现要点：

   • 使用位运算符 $\&$ 计算 $\operatorname{and}$
   • 使用位运算符 $|$ 计算 $\operatorname{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 custom/custom-post-content-inner.html %}

示例代码

#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;
}

{% include custom/custom-post-content-footer.md %}

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

“luogu-”系列题目可在 洛谷题库 在线评测。

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

GESP/CSP 认证学习微信公众号