首页 > 代码库 > HDU 4737 A Bit Fun
HDU 4737 A Bit Fun
题意:定义F(i,j)为数组a中从ai到aj的或运算,求使F(i,j)<m的对数。
思路:或运算具有单调性,也就是只增不减,如果某个时刻结果大于等于m了,那么再往后一定也大于等于m。所以可以用两个指针i,j来维护一段区间,同时开一个数组记录二进制每位上的1的个数(类似于前缀和),利用该数组可以得到区间或的值。一旦大于m则i前移。
#include<iostream>#include<algorithm>#include<cstdio>#include<set>#include<cmath>#include<cstring>#include<vector>#define ll long long#define len 31using namespace std;int num[32];int arr[100005];int n,m;void add(int val){ for(int i=0; i<len; ++i) if(val&(1<<i)) num[i]++;}void sub(int val){ for(int i=0; i<len; ++i) if(val&(1<<i)) num[i]--;}int convers(){ int res=0; for(int i=len-1; i>=0; --i) res=res*2+(bool)num[i]; return res;}int main(){ int T,kase=0; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(num,0,sizeof(num)); for(int i=0; i<n; ++i) scanf("%d",&arr[i]); ll ans=0; int fst=0,lst=0,res=0; while(lst<n) { if(arr[lst]>=m) { fst=++lst; memset(num,0,sizeof*(num)); continue; } add(arr[lst]); ans+=(lst-fst+1); if((((lst+1<n)&&(convers()|arr[lst+1])>=m))) { while(fst<=lst&&(convers()|arr[lst+1])>=m) sub(arr[fst++]); } lst++; } printf("Case #%d: %I64d\n",++kase,ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。