思维+位运算，CF 1934D1 - XOR Break --- Solo Version

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1934D1 - XOR Break --- Solo Version

二、解题报告

1、思路分析

合法操作会让 n 越变越小

假如最高位1为 b1, 次高位1 为b2

那么我们去掉b1 的 1最大能够得到的数为 （1 << b2） - 1

假如n 和 m 最高位1都是b1，那么有n ^ m < n，我们此时可以一步操作

否则，我们必须去掉b1，我们看（1 << b2） - 1 和 m 的关系，如果m > （1 << b2） - 1，说明无法得到，输出-1

否则，我们可以两步得到：

第一步：去掉b1，得到（1 << b2） - 1

第二步：异或 x = (（1 << b2） - 1) ^ m，x 显然x < （1 << b2） - 1

于是我们可以发现，如果存在合法解，那么最多两步就能得到

2、复杂度

时间复杂度： O(1)空间复杂度：O(1)

3、代码详解

 ​

import sys  input = lambda: sys.stdin.readline().strip() MII = lambda: map(int, input().split()) LMI = lambda: list(map(int, input().split())) LI = lambda: list(input()) II = lambda: int(input()) I = lambda: input() fmax = lambda x, y: x if x > y else y fmin = lambda x, y: x if x < y else y P = 1_000_000_007  def solve():     n, m = MII()     if n ^ m < n:         print(1)         print(n, m)         return     hi = 1 << (n.bit_length() - 1)     ma = (1 << (n ^ hi).bit_length()) - 1     if ma < m:         print(-1)     else:         print(2)         print(n, ma, m)  if __name__ == "__main__":     T = 1     T = II()     for _ in range(T):         solve()