P9496 「RiOI-2」hacker 题解

zhang_Jimmy · 2023-08-07 18:16:04 · 题解

2023.8.9更新：感谢 @Anomynous 大佬的提醒，情况2有错误，现已更改。

这题我们可以分三种情况来讨论。

情况一： n = m。

如果 n = m 那么就不用进行操作，直接输出 0。

情况二：n \operatorname{and} m = n 或 n \operatorname{and} m = m。

假设 n = 22_{(10)},m = 6_{(10)}，那么将 n 和 m 转换为二进制就是 n = 10110_{(2)},m = 110_{(2)}，进行与运算就是 n \operatorname{and} m =6_{(10)}。这时我们可以发现一个数的二进制是另一个数的二进制的后缀。

如果 n 是 m 的后缀，那么 n \gets (n \operatorname{or} m)，此时 n = m，只需执行一次。

如果 m 是 n 的后缀，那么 n \gets (n \operatorname{and} m)，此时 n = m，只需执行一次。

如果不是这种情况，怎么办呢？

假设 n = 4_{(10)},m = 6_{(10)}，那么将 n 和 m 转换为二进制就是 n = 100_{(2)},m = 110_{(2)}，进行与运算就是 n \operatorname{and} m =4_{(10)}。

对于这种情况，我们可以 n \gets n \operatorname{or} m，就可以将 n 变成 m 了。

情况三：其它情况

对于其它情况，我们可以先将 n 变为 0，即 n \gets (n \operatorname{and} 0)，此时 n = 0，对于这种情况，只需要再执行一次 n \gets (n \operatorname{or} m)，就可以让 n = m 了，总共需要两次操作。

每次回答的时间复杂度为 O(1)，总时间复杂度为 O(t)。

记得开 long long。

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n==m) cout<<"0\n";
        else if((n&m)==n||(n&m)==m) cout<<"1\n";
        else cout<<"2\n";
    }
    return 0;
}