P9496 「RiOI-2」hacker 题解

hfjqwq · 2023-08-05 19:07:47 · 题解

感谢 @lianchanghua 帮忙修改 Markdown 和 \LaTeX。

题目大意：

给出两个数 n 和 m，n 可以通过按位或或者按位与操作变成 m，问最少多少次操作可以实现？

解题思路：

• 我们可以知道，通过一次按位与上一个 0 可以使任意一位变成 0；按位或上一个 1 可以使任意一位变成 1。因此转化思维：我们一次可以将二进制下的 n 任意几位变成 1 或者变成 0，问有最少有多少次操作可以变成二进制下的 m？ 显而易见答案不是 1 次就是 2 次。分三种情况讨论。

1. 如果存在 n 的某些位上是 0，而 m 对应的那一位是 1；且不存在 n 的某些位上是 1，而 m 对应的那一位是 0。就可以通过把这些 0 改成 1 变成 m，输出 1。

2. 如果存在 n 的某些位上是 1，而 m 对应的那一位是 0；且不存在 n 的某些位上是 0，而 m 对应的那一位是 1。就可以通过把这些 1 改成 0 变成 m，输出 1。

3. 如果同时存在 n 的某些位上是 0，而 m 对应的那一位是 1，且 n 的某些位上是 1，而 m 对应的那一位是 0。可以通过两次操作将相应的 0 变成 1，相应的 1 变成 0，输出 2。

解题细节：

注意到数据范围：n,m \leq 10^{18}，所以 n 和 m 要开 long long。

CODE:

#include<bits/stdc++.h>
using namespace std;
int T;
long long n,m;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&n,&m);
        if(n==m){
            printf("0\n");
            continue;
        }
        if((n|m)==n||(n|m)==m){
            printf("1\n");
        }else{
            printf("2\n");
        }
    }
    return 0;
}