2019级计科第一次实训Problem E

10175101159 edited 4 年，2 月前

Problem E 计算步数

这题比较有意思，分享一个解法，转载自本人的知乎文章（2019级程序设计能力实训第一次机考）：

题意

$\hspace{1em}\hspace{1em}$从平面直角坐标系的点 $(0,0)$ 出发移动有限步，第 $i$ 步可以沿 $x$ 轴或 $y$ 轴正向或反向移动 $2^{i-1}$ 个单位长度。给定点 $(x_0,y_0)(-{10}^{12}\le x_0,y_0\le {10}^{12})$ ，问是否存在某种移动方法的终点恰为 $(x_0,y_0)$ ，如果存在，输出所有可行方法中的最少步数，否则输出 $-1$ 。

$\hspace{1em}\hspace{1em}$例如，输入 $(3,2)$ ，因为最少移动三步（ $(0,0)\to (-1,0)\to (-1,2)\to (3,2)$ ）到达，所以输出 $3$ ；再如输入 $(3,0)$ ，因为最少移动两步（ $(0,0)\to (1,0)\to (3,0)$ ）到达，所以输出 $2$ ；又如输入 $(-1,-1)$ ，因为不存在可行的方法到达，所以输出 $-1$ 。

思路

$\hspace{1em}\hspace{1em}$观察题给样例，不难猜测可行与否与输入的奇偶性有关，有如下证明：考虑横纵坐标和的奇偶性，初始位于 $(0,0)$ ，横纵坐标和 $0+0=0$ 为偶，之后除了第一步移动 $1$ 会改变其奇偶性，此后移动 $2,4,8,16,\cdots$ 都不改变奇偶性。因此除非输入 $(0,0)$ ，只要输入的横纵坐标和为偶数都无解。此外，输入的正负是没有区别的，对水平或垂直方向全部取反向的走法就能使结果变为相反数。故下面只研究输入非负且一奇一偶的情形。

$\hspace{1em}\hspace{1em}$联想到 $A$ 题的平衡三进制表示，沿 $x,y$ 坐标轴正向走记 $+$ ，负向记 $-$ ，把走法表示为两个平衡二进制数，分别表示水平和垂直方向。为方便起见，我们把数位反过来从低位到高位写（从左到右每一位的权重分别是 $1,2,4,8,\cdots$ ，每个数位可以是 $-1,0,1$ ）。举个例子，前述 $(0,0)\to (3,2)$ 的走法被表示为下面两个平衡二进制数：$x=-1\times 1+0\times 2+1\times 4,y=0\times 1+1\times 2+0\times 4$

$\hspace{1em}\hspace{1em}$不难理解，这两个平衡二进制数 $x,y$ 转为十进制后恰好就是输入的 $x_0,y_0$ 。而且因为每一步要么水平移动，要么垂直移动，所以对于每个数位的数码，这两个平衡二进制数都是一个 $0$ ，另一个 $\pm 1$ （ $\otimes$ ）。（这两个结论侧面反映了输入的 $x_0,y_0$ 是一奇一偶的才有解）

$\hspace{1em}\hspace{1em}$根据结论（ $\otimes$ ）， $x,y$ 最低位的数码一个 $0$ ，另一个 $\pm 1$ ，不妨假设 $x$ 最低位是 $0$ ，那么 $y$ 最低位就是 $\pm 1$ 。现在把最低位置零，$x$ 仍是 $x$ ， $y$ 变成了 $y+1$（最低位是 $-1$ ）或 $y-1$（最低位是 $1$ ），这样 $x,y$ 都是偶数了且只有权重为 $2,4,8,\cdots$ 的数位有效。权重为 $2,4,8,\cdots$ 的数位怎么同原来权重为 $1,2,4,8,\cdots$ 的数位产生联系呢？只要把每个数位的权重都减半就好了，也就相当于把偶数 $x,y\pm 1$ 变为 $\frac{x}{2},\frac{y\pm 1}{2}$ 。再回到结论（ $\otimes$ ），现在新的 $\frac{x}{2},\frac{y\pm 1}{2}$ 也是每一位一个 $0$ ，另一个 $\pm 1$ ，权重也回到了 $1,2,4,\cdots$ ，所以还是一奇一偶的。注意到 $\frac{y+1}{2}$ 和 $\frac{y-1}{2}$ 恰好相差 $1$ ，它们是一奇一偶的，而且 $\frac{x}{2}$ 的奇偶性是随输入确定的。

$\hspace{1em}\hspace{1em}$这样就柳暗花明了，根据 $\frac{x}{2}$ 的奇偶性我们可以确定前面是$\frac{y+1}{2}$ 还是 $\frac{y-1}{2}$ ，也意味着我们能够确定先前把最低位置零时 $y$ 是变成了 $y+1$ 还是 $y-1$ ，即我们能够确定 $y$ 的最低位是 $-1$ 还是 $1$ 。

$\hspace{1em}\hspace{1em}$上面的论证说明了什么？如果我们假设输入的 $x,y$ 是一奇一偶且有解的，我们就能用奇偶性确定两个平衡二进制数的最低位。而因为去掉最低位（变成$\frac{x}{2},\frac{y\pm 1}{2}$）后我们又回到了与初始完全类似的情境，所以我们可能利用循环逐步确定两个平衡二进制数的每一位。“能够从合法输入确定平衡二进制数的每一位”这个事实还暗含了“如果解存在，那么解唯一”这个结论。所以我们只要进行这个循环，如果过程中出现矛盾则说明原输入无解，否则我们能得到唯一解（甚至还能得到解的每一步具体走法），也就是题目要求的最优解。

参考代码

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

ll x,y;

int main()
{
    cin>>x>>y;
    if(x < 0)x = -x;
    if(y < 0)y = -y;

    int ans = 0;
    while(1){
        if(x==0 && y==0)break;
        ++ans;
        if(abs(x+y) == 1)break;
        if(x%2 == y%2){ // 同奇偶则不行
            cout<<-1;
            return 0;
        }
        if(x % 2){ // 交换，不妨假设x偶y奇
            x ^= y,y ^= x,x ^= y;
        }
        x /= 2; // x最低位是0,y最低位是1或-1

        // 但两种可能中，x,y抹掉最低位得到的偶数再/2还得是1奇1偶
        ll t1 = (y-1)/2,t2 = (y+1)/2;
        if(x%2 != t1%2)y = t1;
        else y = t2;
    }
    cout<<ans;
    return 0;
}

Comments