Archive for the “solution” Category


Andrew Stankevich’s Contest #7
ZOJ2604 Little Brackets 25.07% (250/997)
ZOJ2605 Under Control 28.44% (93/327)
ZOJ2606 Holidays 8.54% (27/316)
ZOJ2607 Laboratory 25.00% (104/416)
ZOJ2608 Maps 27.02% (20/74)
ZOJ2609 Crazy Painter 23.23% (89/383)
ZOJ2610 Puzzle 28.92% (105/363)
ZOJ2611 Quest 21.27% (30/141)
ZOJ2612 Stable Sets 29.43% (88/299)

Codeforces也开始挂ASC了,这我才想起,ZOJ上11套ASC的解题报告我还差一份作业没交呢,于是在此补上。目前把ZOJ上的ASC打完了,期待Codeforces放出更多的ASC。代码除了通过解题报告中的链接访问外,也可以在github上watashi/AlgoSolution(README)找到。


—-剧透的分割线—-

Comments 6 Comments »

Semi-live已经结束。从ranklist上看,online队伍的表现要比onsite稍稍逊色一筹。


The 2011 ACM-ICPC Asia Dalian Regional Contest
A ZOJ3539 Compress the String 0.00% (0/53)
B ZOJ3540 Adding New Machine 9.03% (16/177)
C ZOJ3541 The Last Puzzle 17.73% (25/141)
D ZOJ3542 Hexadecimal View 31.36% (281/896)
E ZOJ3543 Number String 27.64% (81/293)
F ZOJ3544 Draw a Mess 3.97% (17/428)
G ZOJ3545 Rescue the Rabbit 19.66% (70/356)
H ZOJ3546 Advanture of Xiaoxingxing 16.66% (1/6)
I ZOJ3547 The Boss on Mars 17.17% (136/792)
J ZOJ3548 Chess Board 16.00% (8/50)

简要介绍一下各题的思路吧,不打算写详细的解题报告了,最近也不打算写套题的解题报告。遇到有人问ZOJ Monthly解题报告的事,于是说一下。首先ZOJ Monthly没有官方的解题报告,我过去写的解题报告只是个人兴趣而已,一开始便没有打算一直做下去。不过ZOJ近两个月的解题报告可以在猛犸也钻地Fancy的blog找到。

ZOJ3539. Compress the String

Comments 34 Comments »

现在的版本是去阿里巴巴前写好的,之后基本就没什么进展了。最近被数次问到了月赛解题报告,真不好意思,只好发个半成品了 >_< 哎呀呀,题解说不定要烂尾了~


ZOJ Monthly, July 2011
A ZOJ3510 Boring Assignment Expressions 14.28% (3/21)
B ZOJ3511 Cake Robbery 14.04% (66/470)
C ZOJ3512 Financial Fraud 6.35% (22/346)
D ZOJ3513 Human or Pig 18.78% (127/676)
E ZOJ3514 Palindromic Mighty String 8.33% (1/12)
F ZOJ3515 ToT 1.29% (5/387)
G ZOJ3516 Tree of Three 21.06% (357/1695)
H ZOJ3517 Tower VII 0.00% (0/25)
I ZOJ3518 Unsafe Factor 15.57% (246/1579)
J ZOJ3519 Who is the Smartest Man 29.07% (574/1974)

这个月是浙江大学集训队个人选拔赛的日子,而我作为教练也是每天早出晚归。而除此以外,还有许多集训以外的事情要处理,特别是最近两周非常忙+睡眠不足。这也是为什么这次解题报告没有及时发布的原因。不过拖集训队老人和小朋友们的福,下个月的ZOJ Monthly, Auguest 2011将举办第二回东方专场ZOJ月赛(The 2nd Touhou Only ZOJ Monthly),敬请期待。(第一回东方专场ZOJ月赛的详情在这里。)

ZOJ3510. Boring Assignment Expressions

downloadsource code (ZOJ3510.cpp) [bfs, expr_eval, topsort, sp]

Comments 17 Comments »


ZOJ Monthly, May 2011
A ZOJ3500 Electron Cloud 27.20% (139/511)
B ZOJ3501 Roman Order 30.79% (400/1299)
C ZOJ3502 Contest 15.11% (78/516)
D ZOJ3503 Quadratic Surface 2.28% (4/175)
E ZOJ3504 P-norm 49.43% (262/530)
F ZOJ3505 Yet Another Set of Numbers 28.00% (42/150)
G ZOJ3506 Cut the Tree 17.94% (21/117)
H ZOJ3507 Fractal 13.20% (66/500)
I ZOJ3508 The War 13.53% (226/1670)
J ZOJ3509 Island Communication 4.24% (7/165)

一是准备给包括在去年参加过集训在内的xpies一次新手上路前热身的机会。二是因为神奇的原因,存有summer2009和summer2010数据的ZOJ服务器在省赛后被拔网线了。所以这次的题目来自校赛省赛未用题(ABCD)、summer2007(J)和summer2008(EFGHI)。就算题目总体看来水题很多啦,不过两个小时被圆满什么的>_<,何方神圣啊orz(台大一队?)……不管怎样把五月份混过去了,下次Monthly大概在六月底了吧……

ZOJ3500. Electron Cloud

downloadsource code (ZOJ3500.cpp) [math]

求两个球的并的体积。

判断两个球的位置关系和圆没有区别,在相离、相切和包含的时候很简单,所以主要就是要考虑相交的情况。这时候的体积是两个球冠的体积,球冠的体积可以很简单的积分得到:

\int_{z=-r}^{h}{\pi\sqrt{r^2-z^2}^2}=\pi r^2(h+r)-\frac{1}{3}\pi(h^3+r^3)

而要求h1h2,也只要解:

Comments 46 Comments »


ZOJ Monthly, February 2011
A ZOJ3467 3D Knight Moves 7.14% (5/70)
B ZOJ3468 Dice War 39.82% (92/231)
C ZOJ3469 Food Delivery 13.33% (24/180)
D ZOJ3470 Magic Squares 42.85% (72/168)
E ZOJ3471 Most Powerful 21.23% (86/405)
F ZOJ3472 Play Bridge 66.66% (2/3)
G ZOJ3473 Radio Matrix 20.40% (20/98)
H ZOJ3474 Taekwondo 11.62% (15/129)
I ZOJ3475 The Great Wall I 46.15% (6/13)
J ZOJ3476 The Great Wall II 11.11% (1/9)

summer2010的题用得差不多了,无论简单题还是中等题都有些紧俏了,自己的几个idea又准备留给校赛和省赛,不舍得扔出来,于是从summer2008和summer2009里抠了几道题出来。即使去掉校赛和省赛两个monthly,到7月还要再坚持整理两套monthly呢,果然每场比赛都用10+道题太贅沢了么,难道要求助summer2007了……总觉得一场比赛有太多的圆满不太好,不过有好几道题没人过或没提交也不是太漂亮呢,选题验题好难啊 >______<

ZOJ3467. 3D Knight Moves

downloadsource code (ZOJ3467.cpp) [双向搜索, Bidirectional search]

判断在三维棋盘中,一步能跳(x, y, z)的马能否在6步之内从(x1, y1, z1)跳到(x2, y2, z2)。如果有,输出步数最少的字典序最小的方案。

Comments 55 Comments »