位运算相关

1.与运算
点我
这个题的大概意思给$2$个数$n$和$x$其中满足$n\&(n+1)\&(n+2)\&(n+3)...\&m=x$,求最小的$m$只要满足$m>=x$即可
这个题在二进制的角度来看就是假设$n$的位是

100101

那么$x$一定是从某一位开始与$n$不同并且不同的这一位记为$q$位一定是$x$为$0$$n$为$1$并且从这一位往右$x$的位都是$0$.只有这样才是满足条件的假设不是这样。

• 情况一$x$的$q$位是为$1$$n$的为$0$一定不可能。与运算不可能弄出来一个$1$
• 情况2$x$从$q$位往右还有$1$一定不可能。既然$x$是累积与运算的结果那么与到$q$位一定是用一个   \space   $q+1$位(向左数1位)为$1$后面都是$0$的数   \space   与出来的。

综上所述$x$的位可以是

100100

在这里有一个$trick$$n$的$q+1$位为$1$.这个 $q+1$位(向左数1位)为$1$后面都是$0$的数 应该与$n$中$q+1$位含相加造出$m$,但是如果$n$的$q+1$位为$1$那么$q+1$位就会被消掉了。比如说$n=3$和$x=2$最后求出来$m$是$4$结果是错的。证明略去。
代码

#include<iostream>
#include<cstdio>
#include<bitset>
typedef long long ll;
using namespace std;
typedef long long ll;
int main(void)
{
	int t;
	scanf_s("%d", &t);
	for (int i = 0; i < t; i++)
	{
		ll n, x;
		scanf_s("%lld%lld", &n, &x);
		bitset<100> n2;
		bitset<100> x2;
		n2 = n;
		x2 = x;
		int flag = 1;
		for (int i = 99; i >= 0; i--)
		{
			 
			if (x2[i] != n2[i]&&x2[i]==1&&n2[i]==0)
			{
				flag = 0;
				break;
			}
			else if (x2[i] != n2[i])
			{
				if (x2[i + 1] == 1)
				{
					flag = 0;
					break;
				}
				for (int j = i - 1; j >= 0; j--)
				{
					if (x2[j] != 0)
					{
						flag = 0;
						break;
					}
				}
				if (flag == 0)
					break;
				x2[i + 1] = 1;
				break;
			}
		}
		if (flag == 0)
			printf("-1\n");
		else
		{
			ll sum = 0;
			for (int i = 99; i >= 0; i--)
			{
				sum = sum * 2 + x2[i];
			}
			printf("%lld\n", sum);
		}
	     	
	}
}

2.或运算
集合?点我
这个题的大概意思是给$n$个数然后每个数是以位的形式给出的比如说第$i$个数有$3$位$235$$235$位上是$1$那么第$i$行的样例就会给出

3 2 3 5

现在要找出两个子序列让他们的或运算的结果相等。
我一开始想到集合上去了就是把每个数的位加入到集合里面然后看集合大小有没有变化这个和加入顺序有很大关系并且在某种程度是错误的
比如说

3 1 3 4
3 2 3 1
3 3 5 2

这个样例其实是正确的但是每次加入集合都有新元素所以算法不对。实际上只要记录下来所有数的位的出现次数然后再看是否存在一个数的所有位出现次数$>1$即可。
数据结构我之前交了个代码超时了不是很理解 (用的$vector$所以统计次数的那个位置使用了$map$

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
//const int length = 2e5 + 5;
int main(void)
{
	int t;
	scanf_s("%d", &t);
	for (int i = 0; i < t; i++)
	{
		int n;
		scanf_s("%d", &n);
		vector<vector<int>> edge(n);
	//	vector<int> c(length, 0);
		map<int, int> c;
		for (int i = 0; i < n; i++)
		{
			int k;
			scanf_s("%d", &k);
			for (int j = 0; j< k; j++)
			{
				int a;
				scanf_s("%d", &a);
				edge[i].push_back(a);
				c[a]++;
			}
		}
		int flag = 0;
		for (int i = 0; i < n; i++)
		{
			int yh = 1;
			//for (int j = 0; j < edge[i].size(); j++)
			for(int j:edge[i])
			{
				if (c[j] == 1)
				{
					yh = 0;
					break;
				}
			}
			if (yh == 1)
			{
				flag = 1;
				break;
			}
		}
		if (flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
}

比较
$1840ms$是使用局部数组在循环里用$memset$
$1855ms$那个用的全局数组然后在循环里用$memset$
超时的是把二维数组移到全局然后在循环里声明一个$vector$
$93ms$是在循环里用$map$
可能是开一个$vector$比较花时间本来就是险过但是用$map$就很快…