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)

### ZOJ3305: Get Sauce

source code [bitwise, search]

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

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

### ZOJ3306: Kill the Monsters

source code [bitwise]

### ZOJ3307: Magic Machine

source code [DP, 记忆化搜索]

double gao(int l, int r) {
if (l >= r) {
// interval[left, right] is illegal or empty
return 0;
} else if (dp[l][r] >= 0) {
// done
return dp[l][r];
} else {
double &ret = dp[l][r];
ret = 0;
// random choose one position i that left <= i <= right
for (int i = l; i < r; ++i) {
ret += a * ok[i]  + b * gao(l, i) + (1 - a - b) * gao(i + 1, r);
}
ret /= (r - l);
return ret;
}
}

### ZOJ3308: Move the Knights

source code [FlowNetwork, MinCostMaxFlow]

### ZOJ3309: Search New Posts

source code [DS]

void gaoSearch() {
set<string> post;
list<string>::iterator it = lst.begin();
while (post.size() < 100 && it != lst.end()) {
if (post.find(*it) == post.end()) { // new
if (st.find(*it) != st.end()) {
fputs(it->c_str(), stdout);
post.insert(*it);
++it;
} else {
it = lst.erase(it);
}
} else {
it = lst.erase(it); // ++it;
}
}
fputs("###\n", stdout);
}

lst是按发布/回复时间顺序保存着帖子的std::list，st则是保存着未被标记为已读的帖子的std::set。虽然search里有个可能很慢的while循环，但其实对于每个帖子操作，都只会在while循环里被执行一次，所以复杂度是O(nlg(n))的，其中lg(n)来源于std::set，如果用hash，可以优化到O(n)。

### ZOJ3310: Unrequited Love

source code [DP, enumeration]

long long gao(int n, int a[]) {
long long x, y, z;
x = y = 0;
for (int i = 0; i < n; ++i) {
z = x;
x = y;
y = max(y, z + a[i]);
}
return x;
}

### ZOJ3311: ZOJ Special AC String

source code [string, greedy]

OO
ZZ
ZJ
OZJO

### ZOJ3312: 8*8

source code [Fraction, search]

15 Responses to “ZOJ 8th Anniversary Contest解题报告”
1. wzc1989 says:

Search New Posts 看着好像不是nlogn,貌似复杂度有点高?
如果有很多search,一个search是不是就是nlogn?

• watashi says:

复杂度的确是O(nlgn)的，而且用hash_set代替set就能做到O(n)
如果search多了，那么每个search的时候st.size()和lst.size()势必就大不了
每个post只会进st, lst一次，出一次，所以看起来每次search都有个while循环很吓人，但总的循环次数只有n而已

2. inowfordream says:

求教大牛，那个3^n的复杂度如何证明…

• watashi says:

不会证明
我只是道听途说而已……

3. Navi says:

手机一水…原来yq无线可以直接上国际网

• watashi says:

ym 手机
gxgx bgbg

4. VegetableB says:

揭露黑历史啊……

• watashi says:

也没多少黑历史嘛

5. Hang Hang says:

有钱提醒，ZOJ3305: Get Sauce有个3^n写成n^3了，我还是在肥羊zz的时候才发现的，教坏xpy了

• watashi says:

钱在哪里?
我错了,其实本来全部写成n^3了,结果还有一个漏网了,不过简单推导一下就能证明是3^n吧

6. Navi says:

Get Sauce原来我当时过了啊-.- 发现当时好像是各种ws办法终于过了的…
AC String再补两个Case: OJZO和OJZOO-.- 我感觉把所有情况都考虑到了结果还是wa.. 想了好一阵终于想到忘记判b不能为0了… 于是准备比赛结束前一分钟交-.- 结果忘记了……刚才一交果然ac…

• watashi says:

ym 过了的
AC String我也忘记b不能为0了……我WA了4次 = =b

• HangHang says:

姥姥就给了我一个题面，我纯手工捏了22个数据，原来这么强大的啊

• watashi says:

orz

• VegetableB says:

orz

7.