首页 > 代码库 > HDU 4737 A Bit Fun
HDU 4737 A Bit Fun
题目链接
由于位运算|在区间上是单调的,所以只需要算出每个从i开始的能到哪个j结束,使得(i,j)这个区间里面所有子区间都是满足条件的,即可。
<style>pre { font-family: monospace; color: #ffffff; background-color: #000000 } body { font-family: monospace; color: #ffffff; background-color: #000000 } .lnr { color: #ffff00 } .Special { color: #ffd7d7 } .Statement { color: #ffff00 } .Type { color: #87ffaf } .Constant { color: #ff40ff } .PreProc { color: #5fd7ff }</style>1 #include <stdio.h> 2 #include <string.h> 3 typedef long long ll; 4 const int maxn = 1e5 + 5; 5 int n, m, a[maxn], b[31]; 6 inline int modify(int x, int v) { 7 int ret = 0; 8 for (int i = 0; i <= 30; ++i, x >>= 1) { 9 if (x & 1) 10 b[i] += v; 11 if (b[i]) 12 ret |= 1 << i; 13 } 14 return ret; 15 } 16 int main() { 17 int T; 18 scanf("%d", &T); 19 for (int Tc = 1; Tc <= T; ++Tc) { 20 scanf("%d%d", &n, &m); 21 for (int i = 0; i < n; ++i) 22 scanf("%d", &a[i]); 23 memset(b, 0, sizeof(b)); 24 int j = 0, tmp = 0; 25 ll ans = 0; 26 for (int i = 0; i < n; ++i) { 27 if (i) 28 tmp = modify(a[i - 1], -1); 29 while (j <= i || (j < n && (tmp | a[j]) < m)) 30 tmp = modify(a[j++], 1); 31 if (tmp < m) 32 ans += j - i; 33 } 34 printf("Case #%d: %lld\n", Tc, ans); 35 } 36 return 0; 37 }
HDU 4737 A Bit Fun
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。