【贪心 位运算】JZOJ_3518 进化序列(evolve)

本文主要是介绍【贪心 位运算】JZOJ_3518 进化序列(evolve)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给一个数列$A$，其中$A_x$可以进化到$A_y$的条件：
$1)x<y$
$2)A_x|A_{x+1}|A_{x+2}|...|A_y<M$

思路

我们维护一个队列，可以知道它是一直往右的。
每次往队尾加入一个数，然后一直踢掉队头直到满足当前队列中的或值$<M$(因为当前如果不满足或值$<M$的话那么队头的数就不能进化到后面的数)
答案累加$tail-head$，代表前面的每个数都能进化到当前队尾的数。

代码

#include<cstdio>
#include<algorithm>int N, M;
long long ans;
int a[100001], v[100001];//v记录每一位上1的个数void insert(int x) {for (int i = 0; i <= 30; i++)v[i] += (x >> i) & 1;
}void del(int x) {for (int i = 0; i <= 30; i++)v[i] -= (x >> i) & 1;
}int getK() {int r = 0;for (int i = 0; i <= 30; i++)r += (std::min(v[i], 1) << i);return r;
}int main() {scanf("%d %d", &N, &M);for (int i = 1; i <= N; i++)scanf("%d", &a[i]);int head = 1;for (int i = 1; i <= N; i++) {insert(a[i]);while (getK() >= M && head < i)del(a[head++]);ans += i - head;}printf("%lld", ans);
}

这篇关于【贪心 位运算】JZOJ_3518 进化序列(evolve)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---