• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

A|B

互联网 diligentman 2周前 (01-12) 8次浏览


链接:https://ac.nowcoder.com/acm/contest/10746/A
来源:牛客网

题目描述 

给定两个正整数a,x,统计满足以下条件的bb的个数:

1 le ble x1≤b≤x
a|b=a+ba∣b=a+b
输入描述:
第一行给出一个 t, 1le t le 10^5t,1≤t≤10 
5
 

接下来 t 行每行一对正整数 a,x,1le 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.wangt.cc/2021/01/a%ef%bd%9cb/
喜欢 (0)