G - WiFi Password Gym - 101608G (异或思维题+曲尺) - Windows

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：https://cn.vjudge.net/contest/285962#problem/G

题目大意：给你n和m，n代表有n个数，然后让你找出一个最长的区间，使得这个区间内的所有的数的‘’或‘’都小于等于m。

具体思路：曲尺，两个指针来回弄就行，具体的细节在代码里面，（以前做过的题现在竟然做不出来了，，我）

AC代码：

 #include<iostream>

 #include<stack>

 #include<stdio.h>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 # define ll long long

 const int maxn = 3e6+;

 ll a[maxn];

 int main(){

 freopen("wifi.in","r",stdin);

 int T;

 scanf("%d",&T);

 while(T--){

 ll n,m,tmp=,tot=,flag=,ans=,l,r;

 scanf("%lld %lld",&n,&m);

 for(ll i=;i<=n;i++){

 scanf("%lld",&a[i]);

 ans=max(ans,tot);

 if(a[i]<=m&&!flag){

 l=i;

 r=i;

 tot=;

 tmp=a[i];

 ans=max(ans,tot);

 flag=;

 }

 else if(flag){

 ans=max(ans,tot);

 if((tmp|a[i])<=m){

 r++;

 tmp|=a[i];

 tot++;//计数的时候是按照合法的来记的，不能通过r-l+1来判断

 ans=max(ans,tot);

 continue;

 }

 ans=max(ans,tot);

 if(a[i]>m){

 tot=;

 flag=;

 tmp=;

 continue;

 }

 ans=max(ans,tot);

 tmp=;//注意这里的tmp直接归零就可以了。

 ll pos=l;

 r++;//注意先r++.

 for(ll j=r;j>=pos;j--){

 if((tmp|a[j])<=m){

 tmp|=a[j];

 l=j;

 }

 else break;

 }

 tot=r-l+;// 合法块的大小重新赋值。

 ans=max(ans,tot);

 }

 }

 printf("%lld\n",ans);

 }

 return ;

 }