RT
大致题意 : 给定两个数字a,b, 能对a,b进行三种操作: 1. a = a + 1; 2. b = b + 1; 3. a = a | b;
问至少多少次操作, 使得两数相等;
分析 : 这是一道位运算的题目, 操作1,2很好理解, 而对于操作3, 要知道按位或的性质, 是
a | b = a >= max{a, b} , 所以进行操作3后会使 原本a<b 到 a>=b, 再用一次二者差异会更大, 所以操作三只会用一次, 对于用一次操作3的情况下, 枚举3种情况
1. 若是 a | b == b , 则直接输出1, 如样例1
2. 若是 a<b 的情况下, a++直到 a | b == b, 则从1枚举每一次情况 即判断 ((a+i) | b) == b是否成立
3. 若是 a>b的情况下., 是先用了a | b, 使得a>b, 然后让b靠近a, 即 a | b, b++ == a, 即判断
(a | (b+i)) == b+i 是否成立.
每次的答案即为+i的次数 再+1(操作三), 若枚举完还没有使a = b, 则最小操作就直接是 b - a(a一直加到b)
AC代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;const int N = 1e5+10;int main()
{int T;scanf("%d", &T);while(T -- ){int a,b;cin>>a>>b;int res = 0;if((a|b) == b){cout<<1<<endl;continue;}for(int i = 1; i <= b-a-1; i++){if(((a+i)|b) == b || (a|(b+i)) == (b+i)){res = i+1;break;}}if(res) cout<<res<<endl;else cout<<b-a<<endl;}
}