牛客练习赛130-A题题解
牛客练习赛130-A题题解
题目描述如下:
给定两个整数 x,y，jackle 希望把 x 变成 y。
他每次可以进行如下两种操作之一：
- 选择任意一个整数 z，令 x=x&z。
- 选择任意一个整数z，令x=x|z。
请问最少操作几次可以把 x 变成 y。
输入描述:
本题有多组测试数据。
第一行输入 1个正整数 T(1≤T≤10^5) ，表示数据组数。
接下来 T 行，每行 2 个整数 x,y(0≤x,y≤10^18)。
输出描述:
对于每组测试数据，输出最少操作次数。
示例
输入
2
0 0
0 1
输出
0
1
解题思路:
我们阅读题面可以发现，看到”最少操作次数“这样的描述，我们就可以看出来这是一道贪心的思维题。
那我们先思考一下，我们先看x和y的范围是0到10^18,因此我们要给x，y开long long，这里的输入输出并没有很多，所以用不着快读。
接下来，我们想想，题目给我们限制了两种操作方式，一个是位与"&"操作，一个是位或"|"操作，那么当x==y的时候，我们直接输出0就可以。
若x!=y,我们如果想把x变成y，是不是只需要先让x=x&0,在让x=x|y,就可以了。比如: 2=0010,5=0101,我们首先将2=2&0，2就变成了0，0=0|5，0就变成了5，所以最多只需要2步即可。
到这就完了?还没有，我们还需要考虑1的情况，比如说2=0010，3=0011，他们只有一位不同,那么2=3，是不是只需要让2=2|3就可以了，也就是只需要1步。那我们如何思考这个判断条件呢？
第一个例子，p=x&y,x=2,y=3,
p=2&3,0010&0011=0010,所以p=2=x。
第二个例子，p=x&y,x=11,y=10,
p=11&10,1011&1010=1010,.p=10=y
你发现了什么？是不是只要判断x&y等于x或者x&y等于y，就能知道是不是只需要1步了?
AC代码如下:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int t;
int main()
{
cin>>t;
while(t--){
ll x,y;
cin>>x>>y;
ll p;
p=x&y;
if(x==y){
cout<<0<<endl;
}else if(p==x||p==y){
cout<<1<<endl;
}else{
cout<<2<<endl;
}
}
}