这是队友的代码,只是转载一下。
A Bit Fun
Problem Description
There are n numbers in a array, as a0, a1 ...
, an-1, and another number m. We define a function f(i, j) = ai|ai+1|ai+2|
... | aj . Where "|" is the bit-OR operation. (i <= j) The
problem is really simple: please count the number of different pairs of (i, j) where f(i, j) < m.
Input
The first line has a number T (T <= 50) , indicating the number of test cases.
For each test case, first line contains two numbers n and m.(1 <= n <= 100000, 1 <= m <= 230)
Then n numbers come in the second line which is the array a, where 1 <= ai <= 230.
Output
For every case, you should output "Case #t: " at first, without quotes. The t is the case number starting from
1.
Then follows the answer.
Sample Input
2
3 6
1 3 5
2 4
5 4
Sample Output
Case #1: 4
Case #2: 0
今年ACM成都赛区网赛的题最后一题,自己花了不少时间做的。题目数据较大,本题用追逐法解决。表示一次AC,有点开心。令l[i]表示a[i]之前到a[i]的异或和小于m的最左边的下标值,则最后答案为ans+=i-l[i]+1 (1<=i<=n) 代码如下
#include <iostream> #include <string> #include <cstdio> #include <algorithm> #include <cstring> #define maxn 100010 using namespace std; int a[maxn]; int l[maxn]; int f(int x,int y) { int temp=a[x]; for(int i=x+1;i<=y;i++) { temp|=a[i]; } return temp; } int main() { int T; scanf("%d",&T); getchar(); for(int kase=1;kase<=T;kase++) { int n,m; scanf("%d%d",&n,&m); memset(l,0,sizeof(l)); long long ans=0; for(int i=1;i<=n;i++) scanf("%d",a+i); int L,R; for(R=1;R<=n;R++) { L=R; while(L>=1&&f(L,R)<m) L--;//找最左边的下标值 l[R]=++L; } for(int i=1;i<=n;i++) { //printf("l[%d]=%d\n",i,l[i]); if(l[i]) ans+=i-l[i]+1; } printf("Case #%d: %lld\n",kase,ans); } return 0; }