HDU 4737 A Bit Fun 2013成都网络赛 1010

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4737

题目大意：给定一系列数，F(i,j)表示对从ai到aj连续求或运算，(i<=j)求F(i,j)<=m的总数。

解题思路：或运算只会让值变大或保持不变。不断通过右移j来更新F(i,j)，当aj>=m时所有的i<=j F(i,j)都大于等于m，因此从j后面继续扫数组；当aj<m而F(i,j)>=m时通过右移i来使F(i,j)<m。扫完整个数组即可。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<cmath>
  5 #include<algorithm>
  6 using namespace std;
  7 int tmp[32],last;
  8 long long A[100005];
  9 long long m,now;
 10 int n;
 11 void getin(long long x)
 12 {
 13     int i=0;
 14     while(x)
 15     {
 16         if(x&1)
 17             tmp[i]++;
 18         x/=2;
 19         i++;
 20     }
 21     if(last<i-1)
 22         last=i-1;
 23     return;
 24 }
 25 void Minus(int i)
 26 {
 27     int k=0;
 28     long long x=A[i];
 29     while(x){
 30         if(x%2)
 31             tmp[k]-=1;
 32         x/=2;
 33         k++;
 34     }
 35     return;
 36 }
 37 long long getnow()
 38 {
 39     int i;
 40     long long x=1;
 41     long long s=0;
 42     for(i=0;i<=30;i++)
 43     {
 44         if(tmp[i]>0)
 45             s+=x;
 46         x*=2;
 47     }
 48     return s;
 49 }
 50 int geti(int i,long long Now)
 51 {
 52     while(Now>=m){
 53         Minus(i);
 54         i++;
 55         Now=getnow();
 56     }
 57     now=Now;
 58     return i;
 59 }
 60 void pls(int j)
 61 {
 62     int k;
 63     long long x=A[j];
 64     for(k=0;k<=30;k++)
 65     {
 66         if(x%2)
 67             tmp[k]+=1;
 68         x/=2;
 69     }
 70     return;
 71 }
 72 int main()
 73 {    
 74     int Case=1;
 75     int t,i,j,sum;
 76     scanf("%d",&t);
 77     while(t--)
 78     {
 79         sum=0;
 80         scanf("%d%I64d",&n,&m);
 81         for(i=0;i<n;i++)scanf("%I64d",&A[i]);
 82         i=j=0;
 83         while(j<n)
 84         {
 85             while(j<n&&A[j]>=m)
 86                 j++;
 87             if(j>=n)
 88                 break;
 89             i=j;
 90             sum++;
 91             memset(tmp,0,sizeof(tmp));
 92             last=1;
 93             now=A[i];
 94             getin(A[i]);
 95             if(j+1>=n)
 96             {
 97                 j++;
 98             }
 99             while(j<n){
100                 if(A[++j]>=m||j>=n){
101                     break;
102                 }
103                 else 
104                 {
105                     if((A[j]|now)>=m)
106                     {
107                         pls(j);
108                         i=geti(i,now|A[j]);
109                         sum+=j-i+1;
110                     }
111                     else
112                     {
113                         sum+=j-i+1;
114                         pls(j);
115                         now=A[j]|now;
116                     }
117                 }
118             }
119         }
120         printf("Case #%d: ",Case++);
121         printf("%d
",sum);
122     }
123     return 0;
124 }

View Code

想思路的时候想复杂了，需要右移i时，其实可以直接从j开始向前找到最小的i使F(i,j)<m。不需要像我一样开数组记录

HDU 4737 A Bit Fun 2013成都 网络赛 1010

HDU 4737 A Bit Fun 2013成都网络赛 1010