欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

nssl1230-序列【位运算】

程序员文章站 2024-03-19 08:29:16
...

正题


题目大意

长度为n的序列,求两个长度大于等于kk的连续序列,一个位运算“和”后最大的答案,和“或”后最大的答案。


解题思路

首先oror
b=a or xb=a\ or\ x的话,bab\geqslant a
所以答案就是所有的或起来

然后andand
b=a and xb=a\ and\ x的话,bab\leqslant a
所以就找长度为k的就好了,维护一个滑动窗口。


code

#include<cstdio>
#include<algorithm>
#define N 1000010
#define W 32
using namespace std;
int n,k,a[N],v[W],max1,max2;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
	    scanf("%d",&a[i]);
	    max1|=a[i];//或的答案
	    for(int j=0;j<W;j++)
	    	v[j]+=(a[i]>>j)&1;//加上新的
	    if(i>=k)
	    {
	    	for(int j=0;j<W;j++)
	    		v[j]-=(a[i-k]>>j)&1;//去掉头 
	    	int ands=0;
	    	for(int j=0;j<W;j++)
	    	  ands+=(v[j]==k)*(1<<j);//计算答案
	    	max2=max(max2,ands);//取最大值
	    }
	}
	printf("%d %d",max1,max2);
}
相关标签: 位运算 nssl