Posts Tagged “solution”


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 »


ZOJ Monthly, July 2010
[A]ZOJ3352 Boring Board Game 10.97% (27/246)
[B]ZOJ3353 Chess Board 11.94% (8/67)
[C]ZOJ3354 DoIt is Being Flooded 3.22% (1/31)
[D]ZOJ3355 Football Gambling I 37.61% (612/1627)
[E]ZOJ3356 Football Gambling II 4.65% (115/2472)
[F]ZOJ3357 Football Gambling III 11.11% (1/9)
[G]ZOJ3358 Green Dam Girl 11.15% (28/251)
[H]ZOJ3359 Penalties Kick 13.23% (376/2841)
[I]ZOJ3360 Stranger Calendar II 5.26% (1/19)
[J]ZOJ3361 Yellow Card and Red Card 4.51% (16/354)

啊啊啊,我太圡了,这次Monthly选题没有控制好,选了太多的简单但容易WA的题目(都是足球题太多害的);然后从最后结果来看,应该只放9道题就够了,B/C只放一道就好了,I没有人做真的很意外,J也是;E和H骗了无数的提交,结果导致ZOJ一段时间极卡。下回Monthly选题要注意了。

继续广告:8月22日的ZOJ Monthly, August 2010是我yy了一年准备的东方专场ZOJ Monthly。欢迎捧场,选题控制应该会比这场好吧(多分^。^)

然后,解题报告:

warning: —以下文字各种剧透—


ZOJ3352 Boring Board Game

downloadsource code (ZOJ3352.cpp) [game theory, 记忆化搜索]

Comments 41 Comments »

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 »


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 »