| Andrew Stankevich’s Contest #3 |
| ZOJ2361 |
SGU209 |
Areas |
18.12% (62/342) |
| ZOJ2362 |
SGU210 |
Beloved Sons |
45.40% (173/381) |
| ZOJ2363 |
SGU211 |
Strange Counter |
28.12% (63/224) |
| ZOJ2364 |
SGU212 |
Data Transmission |
11.95% (104/870) |
| ZOJ2365 |
SGU213 |
Strong Defence |
36.40% (83/228) |
| ZOJ2366 |
SGU214 |
Weird Dissimilarity |
13.31% (84/631) |
| ZOJ2367 |
SGU215 |
PL/Cool |
22.91% (33/144) |
| ZOJ2368 |
SGU216 |
Royal Federation |
24.80% (64/258) |
| ZOJ2369 |
SGU217 |
Two Cylinders |
15.71% (94/598) |
还是先推荐两道构造题2363 Strange Counter和2368 Royal Federation。2361 Areas是一道coding量很大的计算几何题，而2367 PL/Cool是一道考验基本功的蘑菇题。2363 Data Transmission是一个值得再研究的分层图的阻塞流问题。
source code (ZOJ2361.cpp) [geometry, 计算几何, dfs]
题目描述很简单，问给定的n条线把平面分出了几个有限的区域。
规模为80，不得不ym那些用优化的半平面交轻松AC这道题的牛人们，但我觉得这不能算a right approach。
我的算法是O(n^2lg(n))的。
5 Comments »
ZOJ Monthly, June 2010，也是今年ACM-ICPC集训选拔赛的一部分。赛前hhanger放出话：
史上最easy的一次月赛，believe me 
这也是atouSk, Bzu, CError和Django奉献的最后一次Monthly了。没题啊，没题啦……
| ZOJ Monthly, June 2010 |
| [A]ZOJ3343 |
Accident Tree |
12.00% (3/25) |
| [B]ZOJ3344 |
Card Game |
36.73% (18/49) |
| [C]ZOJ3345 |
Language |
28.90% (61/211) |
| [D]ZOJ3346 |
Number Game |
12.87% (26/202) |
| [E]ZOJ3347 |
Picture Handling |
26.15% (68/260) |
| [F]ZOJ3348 |
Schedule |
14.21% (30/211) |
| [G]ZOJ3349 |
Special Subsequence |
18.09% (76/420) |
| [H]ZOJ3350 |
Strange Calender |
21.21% (7/33) |
| [I]ZOJ3351 |
Washing Clothes |
18.64% (110/590) |
source code (ZOJ3343.cpp) [bitwise, tree, parser, scanf]
计算中心218原因不明地起火了，据专家Frozen的表示，起火原因可用一棵XML树表示：
- 非叶子节点有两种：”and”代表的条件成立当且仅当其所有的子条件都成立；而”or”节点只要有一个子条件成立，这个节点就成立；
- 叶子节点都表示一个元条件，包含名字和概率。注意具有相同名字的叶子节点总是同时成立或不成立的。
要求这棵树（根节点）成立的概率。最多只有10种不同名字的元条件。
由于只有10种不同名字的元条件，很容易想到2^10枚举所有情况，再判断根节点是否成立。最后的答案就是所有成立情况的加权和，复杂度为2^10*200。题目的麻烦之处再于读入XML并parse成树，其实灵活运用scanf的话，还是比较轻松的，具体看代码。
source code (ZOJ3344.java) [counting, BigInt]
略
其实问题的本质是求将n个数的排列分解为不超过k的奇数个环的方案数。把n个数的排列分解为恰好k个环的方案数就是第一类斯特林数：
![\left[{n\atop k}\right] = (n-1) \left[{n-1\atop k}\right] + \left[{n-1\atop k-1}\right].](http://s.wordpress.com/latex.php?latex=%5Cleft%5B%7Bn%5Catop%20k%7D%5Cright%5D%20%3D%20%28n-1%29%20%5Cleft%5B%7Bn-1%5Catop%20k%7D%5Cright%5D%20%2B%20%5Cleft%5B%7Bn-1%5Catop%20k-1%7D%5Cright%5D.&bg=ffffff&fg=000000&s=0 "\left[{n\atop k}\right] = (n-1) \left[{n-1\atop k}\right] + \left[{n-1\atop k-1}\right].")
当然还要求n的阶乘。需要大数。
source code (ZOJ3345.cpp) [string]
26 Comments »
Entries (RSS)