Posts Tagged “ZOJ”

ZOJ Monthly, December 2008到February 2009连续三个月的解题报告。当时没有自己的空间,而又觉得BBS上发贴效果太不好,所以做的pdf版的。不过后来被ZOJ 7th Anniversary Contest和The 9th Zhejiang University Programming Contest打断了,也没有坚持下去,于是只有这三个月的。说起来我又手痒写了上个月的ZOJ Monthly, June 2010 解题报告,我觉得我也至少能再坚持三个月吧。特别是ZOJ Monthly, August 2010,嗯……如果顺利的话……现在少女祈祷中……

Comments 3 Comments »

狗狗(WishingBone orz)从ZOJ前6个Volumn精调细选的40题,虽然每年集训都见,但一直没有好好做掉。今年最后一次集训了,最近忙的事情也不多,特别是实习+毕设搞的我手的完全生疏了,于是下定决心重头开始把这40道题完全重做一遍。

说来半年多没怎么水题,SRM也没做,退化得真是厉害,集训新手选拔第一场的时候,我在旁边打酱油,然后我突然问于指导,“诶,C++的注释是怎么样的啊”。我发现我先写了个”–”,又写了个”#” (perl写多了),再改成个”%” (latex……毕业论文害的),vim都没有高亮,好不容易想起来”//”,自己也冷得不行。重写这40题的时候也是,以前轻松搞定的问题也WA个几次,还有些就都不会写了,好在慢慢找回点状态。最后几个大自然还是折腾了比较久,特别是”ZOJ1448 Pattern Matching Using Regular Expression”,数据实在是太不厚道了啊。还有”ZOJ1230 Legendary Pokemon”,蘑菇题什么的最讨厌了。



ID ZOJ ID Title Ratio (AC/All)
1001 1021 The Willy Memorial Program 23.69% (82/346)
1002 1030 Farmland 50.33% (151/300)
1003 1041 Transmitters 49.30% (995/2018)
1004 1043 Split Windows 52.48% (74/141)
1005 1060 Sorting It All Out 29.89% (993/3322)
1006 1063 Space Station Shielding 31.79% (235/739)
1007 1066 Square Ice 37.69% (239/634)
1008 1100 Mondriaan’s Dream 39.23% (840/2141)
1009 1103 Hike on a Graph 46.49% (524/1127)
1010 1116 A Well-Formed Program 29.88% (75/251)
1011 1123 Triangle Encapsulation 35.32% (136/385)
1012 1138 Symbolic Derivation 49.23% (32/65)
1013 1144 Robbery 32.24% (128/397)
1014 1145 Dreisam Equations 27.77% (75/270)
1015 1155 Triangle War 37.20% (109/293)
1016 1185 Metal Cutting 31.03% (63/203)
1017 1193 Reflections 42.77% (77/180)
1018 1197 Sorting Slides 26.03% (257/987)
1019 1230 Legendary Pokemon 43.33% (13/30)
1020 1237 Fans and Gems 37.03% (50/135)
1021 1245 Triangles 31.91% (532/1667)
1022 1298 Domino Effect 26.02% (431/1656)
1023 1299 Pendulum 43.20% (35/81)
1024 1301 The New Villa 31.15% (396/1271)
1025 1321 Parallelepiped Walk 20.00% (32/160)
1026 1387 Decoding Morse Sequences 37.63% (499/1326)
1027 1389 Fill the Cisterns! 42.08% (141/335)
1028 1391 Horizontally Visible Segments 24.36% (115/472)
1029 1413 2D Nim 47.31% (44/93)
1030 1423 (Your)((Term)((Project))) 37.73% (512/1357)
1031 1425 Crossed Matchings 61.69% (641/1039)
1032 1426 Counting Rectangles 63.45% (125/197)
1033 1448 Pattern Matching Using Regular Expression 8.29% (18/217)
1034 1460 The Partition of a Cake 29.37% (94/320)
1035 1462 Team Them Up! 18.29% (75/410)
1036 1463 Brackets Sequence 18.20% (356/1956)
1037 1504 Slots of Fun 64.37% (197/306)
1038 1506 Left Labyrinths 21.70% (28/129)
1039 1509 Family 14.79% (25/169)
1040 1518 This Sentence is False 37.71% (109/289)


Comments 20 Comments »


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 Counter2368 Royal Federation2361 Areas是一道coding量很大的计算几何题,而2367 PL/Cool是一道考验基本功的蘑菇题。2363 Data Transmission是一个值得再研究的分层图的阻塞流问题。

ZOJ2361/SGU209 Areas

downloadsource code (ZOJ2361.cpp) [geometry, 计算几何, dfs]

题目描述很简单,问给定的n条线把平面分出了几个有限的区域。

规模为80,不得不ym那些用优化的半平面交轻松AC这道题的牛人们,但我觉得这不能算a right approach。

我的算法是O(n^2lg(n))的。

Comments 10 Comments »

ZOJ Monthly, June 2010,也是今年ACM-ICPC集训选拔赛的一部分。赛前hhanger放出话:

史上最easy的一次月赛,believe me :mrgreen:

这也是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)

ZOJ3343 Accident Tree

downloadsource code (ZOJ3343.cpp) [bitwise, tree, parser, scanf]

计算中心218原因不明地起火了,据专家Frozen的表示,起火原因可用一棵XML树表示:

  • 非叶子节点有两种:”and”代表的条件成立当且仅当其所有的子条件都成立;而”or”节点只要有一个子条件成立,这个节点就成立;
  • 叶子节点都表示一个元条件,包含名字和概率。注意具有相同名字的叶子节点总是同时成立或不成立的。

要求这棵树(根节点)成立的概率。最多只有10种不同名字的元条件。

由于只有10种不同名字的元条件,很容易想到2^10枚举所有情况,再判断根节点是否成立。最后的答案就是所有成立情况的加权和,复杂度为2^10*200。题目的麻烦之处再于读入XML并parse成树,其实灵活运用scanf的话,还是比较轻松的,具体看代码。

ZOJ3344 Card Game

downloadsource 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].

当然还要求n的阶乘。需要大数。

ZOJ3345 Language

downloadsource code (ZOJ3345.cpp) [string]

Comments 29 Comments »

Screenshot-ZOJ :: Home :: Show User Status


Rank Name Plan Solved Submitted AC Ratio
1 Leave me alone http://blog.sina.com.cn/javamancaopeng 1569 1840 85.27%
2 awpris http://e-olimp.com.ua 1363 2051 66.46%
3 SHiVa 1246 2510 49.64%
4 Dorm4106 555 1112 2898 38.37%
5 hhanger@Zodiac Remember The Name 1086 2131 50.96%
6 11 http://www.netyi.net/in.asp?id=cpcs 1072 15232 7.04%
7 听雨轩士 help someone loose…… 1068 4491 23.78%
8 一定要顶啊 1066 1612 66.13%
9 ant 寄望final 1063 1811 58.7%
10 AndyZhau 快追上Shiva了:) 1062 2083 50.98%
11 Fire! 1050 1679 62.54%
12 watashi@Zodiac http://watashi.ws/blog/ 1024 5422 18.89%

发信人: watashi (watashi), 板面: Algorithm
标 题: ZOJ 1kAC达成,自贺一把
发信站: 飘渺水云间 (Fri Apr 30 20:09:30 2010), 转信

终于在接触ZOJ三年内1kAC达成了,自贺一把,版主给个m吧
菜鸟总有一天会长大的

watashi (watashi@Zodiac) AC Ratio: 1024/5422

Plan:

http://watashi.ws/blog/

Solved Problems:
1001 1002 1003 1004 1005 1006

Comments 61 Comments »