Posts Tagged “andrewzta”


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 »


pic

Comments 13 Comments »


Andrew Stankevich’s Contest #6
ZOJ2595 Ackerman’s Function 14.93% (99/663)
ZOJ2596 The Minimal Angle 11.07% (65/587)
ZOJ2597 Yellow Code 38.21% (146/382)
ZOJ2598 Yet Another Digit 23.79% (138/580)
ZOJ2599 Graduated Lexicographical Ordering 20.99% (80/381)
ZOJ2600 GSM 20.00% (55/275)
ZOJ2601 Warehouse Keeper 14.69% (117/796)
ZOJ2602 Don’t Go Left 24.13% (49/203)
ZOJ2603 Railroad Sort 46.76% (123/263)

稿好久,趁着集训间隙前来填坑。大妈题就是好啊就是好,于是顺便广告一下,8月14日,ZOJ将办一场Andrew Stankevich’s Contest, Warmup的Practice,用的题目是Andrew Stankevich’s Contest #11,年代有点久远,不过对绝大多数人来讲应该应该是一套非常不错的新题,去年我们也拿来组队训练过,欢迎捧场。

ZOJ2595 Ackerman’s Function

downloadsource code (ZOJ2595.cpp) [recursion, number theory, Euler's theorem]

求Ackerman函数A(n, m)模t的值。

n\m 1 2 3 4 5
1 2 4 6 8 10 … (2m) 2 \times m
2 2 4 8 16 32 … (2m) 2 \uparrow m
3 2 4 16 2222 22222 … (m2) 2 \uparrow\uparrow m
4 2 4 65536 \begin{matrix}\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}} \\ 65536 \end{matrix} overflow .. 2 \uparrow\uparrow\uparrow m
5 2 4 overflow .. 2 \uparrow\uparrow\uparrow\uparrow m ..

上表中用到了Knuth’s up-arrow notation。从上面的表中可以看出n=1, n=2, m=1, m=2的时候问题都很简单,而事实上n和m只要稍稍大一点,这个数就大得不得了,而它关于t的余数就是定值。证明就是利用欧拉定理,可以参考在Andrew Stankevich’s Contest #8解题报告中,ZOJ2674 Strange Limit这题的解题报告。对于n=3&&m<32和n==4&&m==3的时候,结果未必收敛到了ZOJ2674中定义的那个极限,所以也要特殊处理,方法类似求那个极限的递归。

ZOJ2596 The Minimal Angle

Comments 6 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 »


Andrew Stankevich’s Contest #9
ZOJ2696 Chip Designing 19.15% (41/214)
ZOJ2697 Electricity 16.55% (76/459)
ZOJ2698 Numbers to Numbers 10.28% (29/282)
ZOJ2699 Police Cities 19.35% (66/341)
ZOJ2700 Quadratic Equation 30.51% (65/213)
ZOJ2701 Restore the Tree 13.99% (76/543)
ZOJ2702 Unrhymable Rhymes 28.86% (153/530)
ZOJ2703 Selling Tickets 21.79% (51/234)

灰灰灰灰灰灰长好的一套题,所有题目都推荐!特别是2696 Chip Designing2701 Restore the Tree2697 Electricity这三道构造题,一道比一道值得一想。然后是ZOJ 2698,DP虽然简单,但英语转数字可是相当考验基本功啊。2703 Selling Tickets虽然不算难,但把握时间复杂度和编程复杂度的trade off是很有趣的一件事。有些题,尤其是构造题,一定存在更有趣,更简洁,或者更高效的算法。抛砖引玉,欢迎分享或者cha。

ZOJ2696 Chip Designing

downloadsource code (ZOJ2696.cpp) [构造, 平面几何]

给你个芯片,要用水平或垂直的线路连接两排输入输出节点,要求线路不相交。

2696-2

构造,方法应该非常多,bfs应该也可以,我的方法不难想,效率也满高的,不过写起来就不那么轻松了。首先直接构造一个input到output的连线,如果这条连线和先前的连线相交了,那么总可以“绕”过这条连线,绕的时候,可以保持这条连线的距离为u。只要每次的u都小于上回的一半(理论上等于也可以,但会有更多情况需要处理),那么就不可能会和之前的连线相交。这样还可以在计算过程中使用整数运算,不需要分数。上图是sample的情况,下图是对n=4的一个case的解,图片太模糊了,若需要高清无码矢量图,请点链接下载eps格式的文件。

DL 2696-2.ps
2696-4
DL 2696-4.ps

ZOJ2697 Electricity

downloadsource code (ZOJ2697.cpp) [构造, 拓扑排序(Topological Sort), acyclic]

给定一个有向无环图,要求每天改变一条边的方向,使得最后一些边的方向恰好与原来相反,要求中间过程始终没有环。

Comments 6 Comments »