ACM

51nod 1109 01组成的N的倍数(BFS+剪枝)

51nod 1109 01组成的N的倍数(BFS+剪枝)
题目:给定一个自然数N,找出一个M,使得M > 0且M是N的倍数,并且M的10进制表示只包含0或1。求最小的M。例如:N = 4,M = 100。题解:因为答案必须为十进制只包含01的数,所以我们只需要不断把当前数*10,和当前数*10+1放入队列即可。因为最终得到的结果可能会超出long long型,所以我们可以用字符串来存储,然后按照大数取模来计算余数即可。为什么要计算余数呢?... 继续阅读 »
ACM

51nod 1105 第K大的数(二分答案+二分查找)

51nod 1105 第K大的数(二分答案+二分查找)
题目:数组A和数组B,里面都有n个整数。数组C共有n^2个整数,分别是A[0] * B[0],A[0] * B[1] ......A[1] * B[0],A[1] * B[1]......A[n - 1] * B[n - 1](数组A同数组B的组合)。求数组C中第K大的数。例如:A:1 2 3,B:2 3 4。A与B组合成的C包括2 3 4 4 6 8 6 9 12共9个数。题解:二分好题,最重要... 继续阅读 »
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的位减一(... 继续阅读 »