3518. 【NOIP2013模拟11.6A组】进化序列(evolve)

(File IO): input:evolve.in output:evolve.out

Time Limits: 1000 ms Memory Limits: 262144 KB

Description

Abathur采集了一系列Primal Zerg 的基因样本,这些基因构成了一个完整的进化链。为了方便,我们用A0,A1…An-1 这n 个正整数描述它们。

一个基因Ax 可以进化为序列中在它之后的基因Ay。这个进化的复杂度,等于Ax | Ax+1…| Ay的值,其中| 是二进制或运算。

Abathur 认为复杂度小于M 的进化的被认为是温和的。它希望计算出温和的进化的对数。

Input

第一行包含两个整数n,m。

接下来一行包含A0,A1…An-1 这n 个正整数,描述这n 个基因。

Output

第一行包含一个整数,表示温和的进化的对数。

Sample Input

4 6

1 3 5 1

Sample Output

2

Data Constraint

对于30% 的数据,1 <= n <=1000。

对于100% 的数据,1 <= n<= 100000,0 <= m <= 2^30,1<= Ai<= 2^30。

题解

两种解法:

一种是类似RMQ的倍增算法

另一种是……(我也不知道,有点像单调队列……反正是队列)

我用的是第二种,虽然不知道叫什么算法,但是也讲讲

用队列que表示当前选择

a [ i ] 表示第i位的1的个数

num表示当前进化复杂度

如果当前值x,x|num>m就把队首丢掉

代码

#include<cstdio>
#include<queue>
#include<cmath>
#define lowbit(a) ((a)&-(a))
#define qu(q) ((long)log2(lowbit(q)))
#define N 32
using namespace std;
queue<long>que;
long a[N];
int main()
{ long n,m,i,q,num,x,ans=0;
freopen("evolve.in","r",stdin);
freopen("evolve.out","w",stdout);
scanf("%ld%ld",&n,&m);
num=0;
for(i=1;i<=n;i++){
scanf("%ld",&x);
while((num|x)>m){
for(q=que.front();q;q^=lowbit(q)){
a[qu(q)]--;
if(!a[qu(q)])
num^=lowbit(q);
}
que.pop();
}
num|=x;
que.push(x);
for(q=x;q;q^=lowbit(q))
a[qu(q)]++;
ans+=que.size()-1;
}
printf("%ld\n",ans);
return 0;
}
05-11 22:35