首页 > 代码库 > HDU 4737 A Bit Fun

HDU 4737 A Bit Fun

2024-07-13 17:55:40   225人阅读

题意：定义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;}
View Code


联系
我们