博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU4737:A Bit Fun(二分)
阅读量:6123 次
发布时间:2019-06-21

本文共 1703 字,大约阅读时间需要 5 分钟。

A Bit Fun

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3079    Accepted Submission(s): 1535


Problem Description
There are n numbers in a array, as a
0, a
1 ... , a
n-1, and another number m. We define a function f(i, j) = a
i|a
i+1|a
i+2| ... | a
j . Where "|" is the bit-OR operation. (i <= j)
The problem is really simple: please count the number of different pairs of (i, j) where f(i, j) < m.
 

Input
The first line has a number T (T <= 50) , indicating the number of test cases.
For each test case, first line contains two numbers n and m.(1 <= n <= 100000, 1 <= m <= 2
30) Then n numbers come in the second line which is the array a, where 1 <= a
i <= 2
30.
 

Output
For every case, you should output "Case #t: " at first, without quotes. The 
t is the case number starting from 1.
Then follows the answer.
 

Sample Input
 
2 3 6 1 3 5 2 4 5 4
 

Sample Output
 
Case #1: 4 Case #2: 0
 

Source

题意:求有多少个子区间满足区间内的数按位或结果小于m。

思路:a[i][j]表示前i个数二进制第j位有多少个1,然后二分即可。

# include 
# include
# define MAXN 100000int a[MAXN+1][36];int judge(int i, int mid){ int sum = 0; for(int j=0; j<36; ++j) if(a[mid][j]-a[i-1][j]) sum |= (1<
>= 1; } } for(int i=1; i<=n; ++i) { int l = i; int r = n; while(l <= r) { int mid = (l+r)>>1; if(judge(i, mid) < m) l = mid + 1; else r = mid - 1; } ans += r - i + 1; } printf("Case #%d: %lld\n",cas++,ans); } return 0;}

转载于:https://www.cnblogs.com/junior19/p/6729995.html

你可能感兴趣的文章
微信支付签名配置正确,但返回-1,调不出支付界面(有的手机能调起,有的不能)...
查看>>
第二周例行报告
查看>>
vue实现点击展开,点击收起
查看>>
如何使frame能居中显示
查看>>
第k小数
查看>>
构建之法阅读笔记三
查看>>
写给对前途迷茫的朋友:五句话定会改变你的人生
查看>>
并行程序设计学习心得1——并行计算机存储
查看>>
JAVA入门到精通-第86讲-半双工/全双工
查看>>
bulk
查看>>
js document.activeElement 获得焦点的元素
查看>>
C++ 迭代器运算
查看>>
【支持iOS11】UITableView左滑删除自定义 - 实现多选项并使用自定义图片
查看>>
day6-if,while,for的快速掌握
查看>>
JavaWeb学习笔记(十四)--JSP语法
查看>>
【算法笔记】多线程斐波那契数列
查看>>
java8函数式编程实例
查看>>
jqgrid滚动条宽度/列显示不全问题
查看>>
在mac OS10.10下安装 cocoapods遇到的一些问题
查看>>
angularjs表达式中的HTML内容,如何不转义,直接表现为html元素
查看>>