京东 · 贪心 · 算法编程题
京东 贪心 时限 1 秒 / 256 MB

题目描述

小红拿到了一个正整数 x ，她希望你将该数变成 y 。小红可以进行如下操作：
选择一个正整数 p=2^k ，在满足 x \& p=p 的前提下，使得 x 加上 p 或者 x 减去 p （ \& 操作为二进制下按位与）。
请你帮小红给出一个修改方案。

输入输出

输入描述
两个正整数 x,y ，用空格隔开。
1≤ x,y ≤ 10^18
输出描述
如果无解，请直接输出 -1。
否则第一行输入一个整数 t ，代表操作次数。
接下来的 t 行，每行输入一个字符和一个正整数 p ，代表每次操作。
如果是使得 x 加上 p ，则输出"+ p"；如果是 x 减去 p ，则输出"- p"
你需要保证 p 满足题目中限制的条件，且操作的次数不超过 10^3 次
有多解时输出任意即可。

样例共 2 组

样例 1 · 输出以下也是可以的： - 1 + 2 + 4
输入
3 8
输出
2
+ 1
+ 4
样例 2 · 4 的二进制为"100"，显然无法再加上 1 得到 5。
输入
4 5
输出
-1

算法解析依据充分

考点：贪心 · 构造

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 元素值域：x ≤ 1e18，y ≤ 1e18（注意整数类型选择，避免溢出）
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

  1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
  2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
  3. 按策略一次扫描（通常要先排序）得到答案。
  4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

  • 策略不成立却当成贪心做（典型错因）。
  • 排序关键字选错，或相同关键字时的次级规则没考虑。

对照本题

  • 元素值域最大到 1e18 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 8 → 输出 2 / + 1 / + 4

输出以下也是可以的：

  • 1

+ 2

+ 4

样例 2：输入 4 5 → 输出 -1

4 的二进制为"100"，显然无法再加上 1 得到 5。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第六批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解