题目链接

变幻莫测

题目描述

给定两个整数 、，你可以任意顺序多次执行以下两种操作之一：

  1. 交换：
  2. 变换：

求使 成立所需的最少操作次数；如果无法实现，输出 -1。

输入:

  • 一行，包含两个整数 ()。

输出:

  • 一个整数，表示所需的最少操作次数；如果无法实现，则输出 -1。

解题思路

本题看似是一个复杂的搜索问题，但其核心可以通过分析变换的代数性质，转化为一个简单的条件判断问题，从而得到一个 的解法。

  1. 矩阵视角: 我们可以将状态 视为一个列向量 ，并将两种操作视为矩阵乘法：

    • 交换操作: 对应矩阵 。
    • 变换操作: 对应矩阵 。

  2. 核心洞察: 计算“变换”矩阵的平方，我们发现一个关键性质： 其中 是单位矩阵。这意味着连续进行两次“变换”操作，等价于将原状态的 和 都乘以 2。这个性质 () 极大地限制了状态的可能性，说明如果存在解，其操作序列必然很短。

  3. 推导最短路径: 我们可以逐一检查最短需要几步操作可以达成 的目标：

    • 0 步: 初始状态即为目标，条件是 。
    • 1 步: 对 进行一次变换，得到 。要使两分量相等，则 。
    • 2 步: 如果1步无法解决，我们尝试两步。最短的新路径是“交换”后“变换”：。要使两分量相等，则 。
    • 3 步: 如果2步仍无法解决，我们尝试三步。最短的新路径是“变换”->“交换”->“变换”：。要使两分量相等，则 。

  4. 最终结论: 由于任何更长的操作序列都可以通过 和 进行化简，不会产生新的基础求解条件。因此，如果初始状态 不满足以上四个条件（、 、 、 ）中的任何一个，就无法达成目标。问题从而简化为一系列条件判断。

代码

#include <iostream>

using namespace std;

int main() {
    long long x, y;
    cin >> x >> y;
    if (x == y) {
        cout << 0 << endl;
    } else if (y == 0) {
        cout << 1 << endl;
    } else if (x == 0) {
        cout << 2 << endl;
    } else if (x + y == 0) {
        cout << 3 << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}

import java.util.Scanner;

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

        if (x == y) {
            System.out.println(0);
        } else if (y == 0) {
            System.out.println(1);
        } else if (x == 0) {
            System.out.println(2);
        } else if (x + y == 0) {
            System.out.println(3);
        } else {
            System.out.println(-1);
        }
    }
}

x, y = map(int, input().split())

if x == y:
    print(0)
elif y == 0:
    print(1)
elif x == 0:
    print(2)
elif x + y == 0:
    print(3)
else:
    print(-1)

算法及复杂度

  • 算法：数学推导、条件判断
  • 时间复杂度：。代码只包含若干次条件判断。
  • 空间复杂度：。只需要常数空间存储变量。