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

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;

}

巴特西

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