BISHI11　变幻莫测¶

简单通过率 47.66%python3样例通过牛客 AC

讲解章节：模拟

一句话

交换 (X,Y)->(Y,X) 与变换 (X,Y)->(X+Y,X-Y)，最少几步使 X=Y。

解题思路¶

这题考什么¶

「操作序列看似无穷，可达状态其实有限」的识别。两种操作都是线性变换，可以写成矩阵左乘：交换是 S = [[0,1],[1,0]]，变换是 T = [[1,1],[1,-1]]。关键性质是 S^2 = I、T^2 = 2I：连着做两次同样的操作，要么白做（S），要么只是把整个向量放大 2 倍（T）。而「X = Y」这个目标对整体缩放（包括同乘负数）完全不敏感，于是放大倍数可以直接丢掉。

结论：任何操作序列都能化简成 S 与 T 交替出现的形式，而交替词只有有限种本质不同的判定条件：

步数 0   I           -> X = Y
步数 1   T           -> Y = 0
步数 2   T·S         -> X = 0
步数 3   T·S·T       -> X + Y = 0
步数 4 起条件开始循环（再往下又回到 X = Y 和 X + Y = 0）

所以判定条件总共只有 4 个，按步数从小到大逐个检查，全不满足就是 -1，整题 O(1)，连循环都不需要。

数据规模与复杂度¶

只有一组数据、|X|, |Y| <= 100，几次比较即可，O(1)。值域这么小其实也能对全部 201*201 个状态跑一遍 BFS 验证上面的结论，但既然条件已经推出来，直接判断更短也更快。

坑在哪¶

四个条件可能同时成立，必须按 0 -> 1 -> 2 -> 3 的顺序判断，求的是最少步数。(0, 0) 同时满足全部四条，只有先判 X = Y 才会输出 0；把分支顺序打乱就会给出偏大的答案；
连做两次变换等于把 (X, Y) 同时乘 2，不会产生新的可行解，所以「多操作几步说不定就成了」是不成立的，步数超过 3 就不必再试；
X、Y 可以是负数（-100 <= X, Y <= 100），x == -y 这一条正是靠负数才有意义，样例 2 的 (5, -5) 走的就是这条分支。

样例复核¶

(5, 8)：X != Y、Y != 0、X != 0、X + Y = 13 != 0，输出 -1； (5, -5)：前三条都不满足，X + Y = 0 成立，输出 3—— 对应变换得 (0, 10)、交换得 (10, 0)、再变换得 (10, 10)，与样例一致。

参考实现¶

solutions/BISHI11.py
x, y = map(int, input().split())

if x == y:
    print(0)                          # 已经相等，一步都不用走
elif y == 0:          # 一次变换：(X,Y) -> (X+Y, X-Y)，Y=0 时两边都是 X
    print(1)
elif x == 0:          # 先交换成 (Y,0)，再变换得 (Y,Y)
    print(2)
elif x == -y:         # 变换得 (0,2X)，交换得 (2X,0)，再变换得 (2X,2X)
    print(3)
else:
    print(-1)                         # 四个条件都不满足，再多步也无解

BISHI11 变幻莫测¶