鏈接：https://ac.nowcoder.com/acm/contest/10746/A
來源：牛客網
題目描述
給定兩個正整數a,x，統計滿足以下條件的bb的個數：
1 \le b\le x1≤b≤x
a|b=a+ba∣b=a+b
輸入描述:
第一行給出一個 t, 1\le t \le 10^5t,1≤t≤10
5
接下來 t 行每行一對正整數 a,x,1\le a,x \le 10^9a,x,1≤a,x≤10
9
輸出描述:
輸出 t 行，每行一個正整數
示例1
輸入
復制
2
1 2
2 3
輸出
復制
1
1
假設 A=100100010，則滿足 A+B=A|B 條件的B，在 A 中為1的位置必定為0，也就是 B=0xx0xxx0x，其中的 x 可為 0 或 1，因此只要數一下 A 裡面有幾個位元是 0，算出 2 的次方就可以得到答案，
但是題目又規定 B <=X ，所以我們要將 X 分段處理，假設 X=1001000100，先找出最左邊第一個出現的 1 為 1000000000，分出第一段數字 xxxxxxxxx，(不含上面的數)
也就是 0 ~ 111111111 (1000000000-1)，再用這一段去找有幾個位置在 A 中是 0，接下來再找出第二個出現的 1 為 1000000，而第二段數字為 1000xxxxxx，也就是 1000000000 ~ 1000111111 (1001000000-1)，數字的最前面固定是 1000，一樣找出后面的位置有幾個在 A 中是 0，
要注意的是，如果這個位置在 X 和在 A 中同時為 1，則后面就不會再有答案，因為這個做法只能處理到 X-1，所以 X 要另外處理，
最后，因為題目要求要正整數，但這個做***包含 0，所以答案要再減一，
大坑：與運算要加括號
最后要考慮最后一位a與x相等的情況
并且0不是答案
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
int T;
scanf("%d", &T);
while(T --){
int a, x;
scanf("%d%d", &a, &x);
long long ans = 0;
for (int bit = (1 << 30); bit >= 1; bit >>= 1){
if ((bit & x) == 0){
// cout << "_------" << endl;
continue;
}
// cout << "--------" << endl;
int cnt = 0;
for (int bits = bit >> 1; bits >= 1; bits >>= 1){
if ((bits & a) == 0) cnt ++;
}
// cout << bit << "-------" << endl;
ans += pow(2, cnt);
// cout << ans << endl;
if (bit & a) break;
}
if ((a | x) == (a + x)) ans ++;
cout << ans - 1 << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/247743.html
標籤：其他
上一篇：將WebAPI部署在IIS上