小红的整数操作

[题目链接](https://www.nowcoder.com/practice/f817bcf2052b42e6a1bab1f460ea6042)

思路

给定正整数 $x$ 和 $y$ ，每次操作可以选一个 $p = 2^k$ ，要求当前 $x$ 的第 $k$ 位为 $1$ （即 $x \mathbin{\&} p = p$ ），然后令 $x$ 加上或减去 $p$ 。问能否在 $10^3$ 次操作内把 $x$ 变成 $y$ 。

观察操作的本质

先把每一位上的 $1$ 想象成一枚代币。操作的效果是：

减去 $2^k$ ：直接移除第 $k$ 位上的代币。popcount 减 $1$ 。
加上 $2^k$ ：从第 $k$ 位产生一个进位，第 $k$ 位清零，第 $k{+}1$ 位加 $1$ 。如果第 $k{+}1$ 位也是 $1$ ，进位继续向上传播。本质是把代币从低位「推」到更高位，途中还可能吞掉沿途的其他代币。

关键性质：代币只能向高位移动或被消除，永远不能向低位移动。 因此每次操作后 popcount 只减不增。

判定无解

根据上面的性质，有两个必要条件：

popcount 条件： $\text{popcount}(y) \leq \text{popcount}(x)$ 。代币只减不增， $y$ 的 $1$ 的个数不能超过 $x$ 。
低位条件： $y \bmod \text{lowbit}(x) = 0$ 。设 $\text{lowbit}(x) = x \mathbin{\&} (-x)$ ，即 $x$ 的最低位 $2^L$ 。所有操作都是加减 $2^k$ （ $k \geq L$ ），所以 $x$ 始终是 $2^L$ 的倍数， $y$ 也必须如此。

可以证明，当这两个条件同时满足时一定有解。

构造方案

把 $x$ 的 $1$ -位看作代币， $y$ 的 $1$ -位看作目标槽位。我们需要把若干代币「搬运」到目标位置，多余的代币直接删掉。

第一步：匹配。 对 $y$ 的每个 $1$ -位（从高到低），在 $x$ 的 $1$ -位中找最高的、位置不超过目标的、尚未使用的那个进行配对。如果找不到则无解。

这种「从高到低、就近匹配」的策略可以最小化搬运距离，也保证了匹配后的配对天然地位置单调： $x$ 位置升序时 $y$ 位置也升序。

第二步：删除多余代币。 把没有被匹配的 $x$ -位从高到低逐个减掉。从高位减不影响低位，安全。

第三步：搬运已匹配的代币。 把所有配对按 $x$ 位置从高到低处理，每次通过连续的「加 $2^k$ 」把代币逐位上移到目标位置。

为什么要从高到低搬运？因为低位代币在上移时可能经过高位代币的位置，产生意外的进位合并。先搬高位代币，搬完后它落在更高的目标位上，不会挡住后面低位代币的上移路径。

操作次数分析

删除操作至多 $60$ 次。
搬运操作的总步数等于 $\sum (y_i - x_i)$ ，在 $60$ 位的范围内最大约 $30 \times 30 = 900$ 。
总操作次数不超过 $960$ ，满足 $10^3$ 的限制。

样例演示

$x = 3$ （ $011$ ）， $y = 8$ （ $1000$ ）：

步骤	操作	$x$ （二进制）	说明
匹配	—	—	$y$ 的 bit3 配对 $x$ 的 bit1；bit0 多余
1	$- 1$	$010$	删除多余的 bit0
2	$+ 2$	$100$	搬运 bit1 → bit2
3	$+ 4$	$1000$	搬运 bit2 → bit3

复杂度

时间复杂度： $O(B^2)$ ，其中 $B = \log_2 x \leq 60$ 。匹配 $O(B^2)$ ，每次搬运至多 $B$ 步，总搬运步数 $O(B^2)$ 。
空间复杂度： $O(B^2)$ ，存储操作序列。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long x, y;
    scanf("%lld%lld", &x, &y);

    if(x == y){
        printf("0\n");
        return 0;
    }

    long long lowbit_x = x & (-x);
    if(y % lowbit_x != 0){
        printf("-1\n");
        return 0;
    }

    vector<int> xbits, ybits;
    for(int i = 0; i < 62; i++){
        if((x >> i) & 1) xbits.push_back(i);
        if((y >> i) & 1) ybits.push_back(i);
    }

    if((int)ybits.size() > (int)xbits.size()){
        printf("-1\n");
        return 0;
    }

    // 匹配：y-bit 从高到低，每次取最高可用 x-bit
    vector<pair<int,int>> matched;
    vector<bool> used(xbits.size(), false);

    for(int i = (int)ybits.size() - 1; i >= 0; i--){
        int yi = ybits[i];
        int best = -1;
        for(int j = (int)xbits.size() - 1; j >= 0; j--){
            if(!used[j] && xbits[j] <= yi){
                best = j;
                break;
            }
        }
        if(best == -1){
            printf("-1\n");
            return 0;
        }
        used[best] = true;
        matched.push_back({xbits[best], yi});
    }

    vector<int> extra;
    for(int j = 0; j < (int)xbits.size(); j++)
        if(!used[j]) extra.push_back(xbits[j]);

    vector<pair<char,long long>> ops;

    // 删除多余代币（高→低）
    sort(extra.rbegin(), extra.rend());
    for(int pos : extra){
        ops.push_back({'-', 1LL << pos});
        x -= (1LL << pos);
    }

    // 搬运（按 x 位置高→低）
    sort(matched.begin(), matched.end(), [](auto& a, auto& b){
        return a.first > b.first;
    });

    for(auto& [xp, yp] : matched){
        for(int p = xp; p < yp; p++){
            ops.push_back({'+', 1LL << p});
            x += (1LL << p);
        }
    }

    printf("%d\n", (int)ops.size());
    for(auto& [c, p] : ops)
        printf("%c %lld\n", c, p);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong(), y = sc.nextLong();

        if (x == y) {
            System.out.println(0);
            return;
        }

        long lowbitX = x & (-x);
        if (y % lowbitX != 0) {
            System.out.println(-1);
            return;
        }

        List<Integer> xbits = new ArrayList<>(), ybits = new ArrayList<>();
        for (int i = 0; i < 62; i++) {
            if (((x >> i) & 1) == 1) xbits.add(i);
            if (((y >> i) & 1) == 1) ybits.add(i);
        }

        if (ybits.size() > xbits.size()) {
            System.out.println(-1);
            return;
        }

        boolean[] used = new boolean[xbits.size()];
        List<int[]> matched = new ArrayList<>();

        for (int i = ybits.size() - 1; i >= 0; i--) {
            int yi = ybits.get(i);
            int best = -1;
            for (int j = xbits.size() - 1; j >= 0; j--) {
                if (!used[j] && xbits.get(j) <= yi) {
                    best = j;
                    break;
                }
            }
            if (best == -1) {
                System.out.println(-1);
                return;
            }
            used[best] = true;
            matched.add(new int[]{xbits.get(best), yi});
        }

        List<Integer> extra = new ArrayList<>();
        for (int j = 0; j < xbits.size(); j++)
            if (!used[j]) extra.add(xbits.get(j));

        StringBuilder sb = new StringBuilder();
        int opCount = 0;

        extra.sort(Collections.reverseOrder());
        for (int pos : extra) {
            sb.append("- ").append(1L << pos).append('\n');
            opCount++;
            x -= (1L << pos);
        }

        matched.sort((a, b) -> b[0] - a[0]);
        for (int[] m : matched) {
            for (int p = m[0]; p < m[1]; p++) {
                sb.append("+ ").append(1L << p).append('\n');
                opCount++;
                x += (1L << p);
            }
        }

        System.out.println(opCount);
        System.out.print(sb);
    }
}