首页 > 代码库 > 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]; } else Num[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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。