序列【模拟】

题目大意：

---

思路：

首先，我们知道$a or b$肯定是不小于a和b，也就是说，进行或运算的数字越多，结果肯定不会变小。所以，第一问的答案就是全部数字或起来。
那么就考虑第二问。
由于进行与运算的两个数$a,b$肯定有$a and bleq min(a,b)$，所以进行与运算的数字越多，结果肯定不会变大。所以最好就选择$k$个数。
可以把选择的数看成一个滑动窗口，那么就用$num[i]$表示现在窗口的数字中有多少个是二进制下第$i$位为$1$的。
例如窗口里有$3$个数$11,8,2$，那么将这三个数分别转成二进制后就是

$11$	$8$	$2$
$1011$	$1000$	$0010$

所以

• $num[0]=1+0+0=1$
• $num[1]=1+0+1=2$
• $num[2]=0+0+0=0$
• $num[3]=1+1+0=2$

那么如果$num[x]==m$，说明窗口里的数字这一位全部是$1$，所以$and$起来就是$1$，否则不是。
那么就求出窗口在最左边的情况的答案，然后往右移即可。
时间复杂度：（常数为$30$的）$O(n)$，时限$5s$，不怂。

---

代码：

#include <cstdio>
#include <iostream>
#define N 1000100
#define MAXN 40
using namespace std;

int n,m,a[N],ans,num[MAXN];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		ans|=a[i];
	}
	printf("%d ",ans);  //第一问
	for (int i=1;i<=m;i++)
	 for (int j=0;j<=30;j++)
	  if ((a[i]&(1<<j))==(1<<j)) num[j]++;  //窗口
	ans=0;
	for (int i=m+1;i<=n;i++)
	{ 
		int k=0;
		for (int j=0;j<=30;j++)
		{
			num[j]-=((a[i-m]&(1<<j))==(1<<j));
			num[j]+=((a[i]&(1<<j))==(1<<j));  //右移
			if (num[j]==m) k+=(1<<j);  //求答案
		} 
		if (ans<k) ans=k;
	}
	printf("%d
",ans);
	return 0;
}