Posts Tagged “bitwise”

ZOJ八周年庆,8道题,比赛时间188min,很有爱。其实是因为勉勉强强才凑到了8道题,如果正正经经比5个小时的话,大家都圆满了。


ID Title Ratio (AC/All)
A(ZOJ3305) Get Sauce 16.56% (142/857)
B(ZOJ3306) Kill the Monsters 17.36% (25/144)
C(ZOJ3307) Magic Machine 18.03% (11/61)
D(ZOJ3308) Move the Knights 37.23% (35/94)
E(ZOJ3309) Search New Posts 20.20% (80/396)
F(ZOJ3310) Unrequited Love 23.47% (307/1308)
G(ZOJ3311) ZOJ Special AC String 24.59% (338/1374)
H(ZOJ3312) 8*8 7.14% (2/28)


除了G和H外都是summer2009暑期集训里的题。不说废话了,正文开始:

ZOJ3305: Get Sauce

一个n<=16个元素的集合,给定m<=种备选子集,问最多可划分出多少个不相交的备选子集。

source code [bitwise, search]

这题有复杂度O(3^n),而且常数很小的算法。这基于下面这个简单又漂亮的位运算枚举子集的循环

for (int sub = mask; sub != 0; sub = (sub - 1) & mask)

sub将依次表示mask所有可能的子集,总的枚举复杂度则是n^3。

当然,搜索加有效地剪枝总是能过的。不过我表示剪枝苦手,当时也不知道这样一个O(3^n)枚举子集的算法,所以我是训练前18名中唯一一个没过这道题的,惭愧啊~

ZOJ3306: Kill the Monsters

在一个20×20的grid中,选择共n行与列,使得最多的’#'同时被所选行和列覆盖。

source code [bitwise]

Comments 15 Comments »