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 的进化的被认为是温和的。它希望计算出温和的进化的对数。
第一行包含两个整数n,m。 接下来一行包含A0,A1…An-1 这n 个正整数，描述这n 个基因。
Output
第一行包含一个整数，表示温和的进化的对数。
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;
}
