HDU4737A Bit Fun

本文主要是介绍HDU4737A Bit Fun，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：HDU4737A Bit Fun

题目大意:给出N个数，然后问里面有多少个子串，对于每个子串做或运算的结果小于m。

解题思路：这题测试数据比较水，暴力就可以过。正解：把每个数都用二进制存起来，然后一开始head和tail都指向1.每次tail都++，对于每个tail求出离他最远的head。然后求和一下每个tail满足条件的子串。注意当head到tail的和超过m的时候，就要将head往后移动，这个时候就要将head的数字对应有1的位置--。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;const int maxn = 1e5 + 5;
int n;
int num[maxn], m;
int Num[maxn][35], cnt[35];
int t[35];void init () {t[0] = 1;for (int i = 1; i <= 30; i++)t[i] = t[i - 1] * 2;
}bool judge () {ll Sum = 0;for (int i = 0; i <= 30; i++) if (cnt[i])Sum += t[i];if (Sum < m)return true;return false;
}ll solve () {ll ans = 0;for (int k = 1; k <= n; k++) {for (int i = 30; i >= 0; i--) {if (num[k] >= t[i]) {Num[k][i] = 1;num[k] -= t[i];} elseNum[k][i] = 0;}}int head, tail;head = tail = 1;for (int i = 0; i <= 30; i++)cnt[i] = 0;ll tmp; while (tail <= n) {for (int i = 0; i <= 30; i++)if (Num[tail][i])cnt[i]++;if (!judge()) {	while (head <= tail && !judge()) {//注意head移动的边界for (int i = 0; i <= 30; i++)if (Num[head][i])cnt[i]--;head++;}}ans += tail - head  + 1;tail++;}return ans;
}int main () {int T;scanf ("%d", &T);init();for (int cas = 1; cas <= T; cas++) {printf ("Case #%d: ", cas);scanf ("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf ("%d", &num[i]);printf ("%I64d\n", solve());}return 0;
}

这篇关于HDU4737A Bit Fun的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---