ACM

tenka1-2017-IntegerotS(位运算+贪心)

tenka1-2017-IntegerotS(位运算+贪心)
题意:给出n组数据,ai,bi,意味着编号为ai的物品价值为bi,求选择一些ai,他们或运算之后小于或等于k的最大价值。题解:贪心法,因为当前选择的ai或运算之后有可能会大于k,考虑到或运算的性质,假设当前选择的数或运算之后必须小于或者等于k,那么我们必须要选择这样的一个a[i],a[i]&k==a[i]。即k的二进制位上有1的地方,a[i]才能有1。然后,循环将k二进制位上有1的位减一(... 继续阅读 »
ACM

HDU 5969 最大的位或(二进制)

HDU 5969 最大的位或(二进制)
“|”运算是1|1=1,1|0=0,0|1=0,0|0=0。不用想肯定是位运算,但是比赛时想了好久没想通。后来看题解发现是自己想多了。就是从最高位开始往下遍历,如果一个数是2的n次方,那么与他“|”最大的肯定是2^n-1,如果取不到那么肯定是往上取。就是这个往上取,开始想不通,后来看题解才明白。具体看代码吧。题目地址:http://acm.hdu.edu.cn/showproblem.php?pi... 继续阅读 »