※ 引述《Anisno (Anisno)》之铭言： : 我遇到一个问题，题目如下:给一个正整数，你必须找出遮罩M，满足L<M<U且N or M : 运算後数字最大。 : 假如 : N=30951344 : L=201310 : U=3567891 : 求M=___ 要解的话最简单就是 NM, M = max((i|N, i) for i in range(L+1,U)) 出来 NM 就是 N or M 值，M 即所求 不过这样复杂度是 O(U-L) 我想到一个 O(log(U)) 的解法 以范例来说 U-L = 3366581 log(U) = 21.8 效率差距差不多就差这麽多 我想到的解法是 找出所有 "介於 U L 间，尽量多 1 或是尽量越大的数字" 称为 candidates 再从这些 candidates 中取出跟 N 做 or 最大者 实作出的 code 有点长，我直接加注解传到贴 code 网站 http://ideone.com/p0YzSV 建意看以下的演算法可以搭配 code 会比较清楚 :) class Entry 栏位解释： (等等演算法中 queue 里的元素都是 Entry) M: 现在的 M 值，是 binary string 型式，是从高位元填下来的 uf: upperbound flag: 有 set 表示现在的 M 值已保证小於 U lf: lowerbound flag: 有 set 表示现在的 M 值已保证大於 L idx: 现在跑到第几 bit (最高位元是 idx=0) 在开始前，先把 U L 转成 binary string 而且长度对齐，L 短的部份就前面补 0 以下的 length = len(U) = len(L) # code 中 ub lb 是指 binary string 版的 U L 演算法 ====== 主要的概念就是从最高位元(idx=0)开始填 0/1，然後再往下走 idx=1 填 0/1 如此一来会展开一颗二元树，叶子会有 2**length 个 然後我们用 BFS 去走访他，搭配剪枝可以砍掉大部份的状况 # DFS 应该也可以，不过我 code 是用 BFS 实做的，效能应该差不多 刚刚提到的 class Entry 可以想成是在每个节点的 状态 在每次 main while 跑时会从 queue 中取一个状态来走，然後把新的状态加到 queue 中 若取出的状态，发现 lf uf 都已 set 了，表示已符合 L<M<U 那麽後面乱填也不会影响到 L<M<U，跟据题意当然全填 1 这样 or 起来会最大 class Entry 的 get() 就是在後面补 1 用的，然後结果就会是一个 candidate 若取出的状态，发现 idx >= length，表示 M 的长度已经填满了 表示 寻找 L<M<U 失败，那这条路就不理他 (continue) 再来就是演算法的重点，要怎麽作状态转移 跟据 U[idx] L[idx] 的值会有 4 种状况：00 01 10 11 我跟据等等解释需要做一点顺序的调整 U L 1. 1 0 2. 0 1 3. 0 0 4. 1 1 U L 1. 1 0 在这个状况下 M 若填 1 就 "一定保证比 L 大" -> set lf M 若填 0 就 "一定保证比 U 小" -> set uf 因此会产生两个新状态："填 1 并 set lf" "填 0 并 set uf" 这里，我们不能知道 填1比较好 还是 填0比较好 因为 set 的 flag 不同(set flag 可以想成是得到的保证) 後面可能会有不同结果 U L 2. 0 1 这个状况比较神奇，因为 U > L 若在前面的 bit 全部都 U==L，那到这位发现 U[idx]==0 L[idx]==1 就不合前题 (因为我们是从高位走下来的) 因此会遇到这个状态只有可能是前面出现过 1 0 (状况1) 既然出现过 状况1，那 lf 或 uf 一定有其中一个被 set 所以分状况 if lf is set: (已经保证比L大了) 为了满足 M<U，这里一定要填 0 if uf is set: (已经保证比U小了) 为了满足 M>L，这里一定要填 1 if lf ul are not set: 不可能出现 在这个状况下，由於要满足 L<M<U，只会产生一个新状态，而不会动到 flag U L 3. 0 0 这个状态必需要考虑到 uf，因为 M<U，随便填 1 的话可能会因此 M>U if uf is not set: 为了不能让 M 超过 U，只能填 0 if uf is set: M 已经保证小於 U 了，这位可以高兴的直接填 1 顺便 set lf -> uf lf 皆 set，结束这条路 (後面也可以高兴的全填 1) U L 4. 1 1 这个状态与上个类似，因为 M>L，所以必需看 lf 行事 if lf is not set: 为了不能让 M 小於 L，只能填 1 if lf is set: M 已经保证大於 L 了，这位...填 0 填 1 都可以 填 0 --> set ul 结束这条路 填 1 --> 什麽 flag 都不会动，继续做 为什麽不能像 状况3 直接结束这条路呢？ 因为 N[idx] 有可能在这位是 0，那麽这位填 1 可能会得到 N or M 比较大 当然可以判断 N 值多砍一点，不过现在效能已经改善很多，先不弄这麽复杂 如此去走访这颗树，走完後会一堆 candidates 再一个个去测谁和 N or 起来最大就结束了 # 当然可以在一产生 candidate 时就做 N or M 然後记录最大 # 这样可以再省掉存 candidates 花的时间和空间，不过这跟演算法没什麽关系 # 为了方便我就先没这样写了XD ----------------------------------------------------------------- 效能的部份 这个方法最坏就是整颗树走完 O(U)，不过这是不可能的事 由於剪枝的关系，每往下一层大约只有 2 条路能走到 (没剪枝是 2**层数 条) 虽然没精算，不过我觉得效能差不多是 O(2*log(U)) = O(log(U)) 而实测也差不多是如此 范例的 U=3567891 L=201310 爆搜要 3567891 - 201310 跑 3366581 次 但用这个演算法 main while 只跑了 37 次，产生的 candidates 只有 12 个 2*log(3567891) = 43.5 差不多再少一点这样 程式是用 python2 写的，从 stdin 依序读入 U L N 要改 python3 只有 print 和 raw_input 需要动 这个实作是把数字转成 0/1 组成的 string 做的 真的要加速的话可以直接用 bitwise，但这部分与演算法无关就不提了 有问题或 bug 欢迎提出 :) -- 光明 的背後 是 黑暗 黑暗 的背後 还是 黑暗 由此可知 黑暗 > 光明 Q.E.D. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.113.235.135 ※ 编辑: darkgerm 来自: 140.113.235.135 (11/05 22:47) ※ 编辑: darkgerm 来自: 140.113.235.135 (11/05 22:52)