Posts Tagged “ZOJ”


ACM × Touhou (ZOJ Monthly, August 2010)
akyu ZOJ3373 Gensokyo Forbidden Words 19.70% (27/137)
cirno ZOJ3374 ⑨ Adjacent Numbers 11.36% (5/44)
furan ZOJ3375 Imperishable Night 23.12% (68/294)
hatate ZOJ3376 Safest Points 100.00% (3/3)
inaba ZOJ3377 Ancient Duper 23.50% (51/217)
kaguya ZOJ3378 Attack the NEET Princess 9.80% (103/1050)
marisa ZOJ3379 Master Spark 6.64% (20/301)
pache ZOJ3380 Patchouli’s Spell Cards 15.68% (8/51)
reimu ZOJ3381 Osaisen Choudai! 19.51% (193/989)
sakuya ZOJ3382 Luna Dial 28.57% (2/7)
shiki ZOJ3383 Shiro? Kuro? 22.94% (355/1547)
youmu ZOJ3384 Yuyuko and Youmu 50.31% (398/791)
yuyuko ZOJ3385 Hanami Party 0.91% (1/109)

基本上这套题都是红魔馆和白玉楼的天下了,风神录/地灵殿/星莲船都没什么出场机会。然后不多说了,下面是每题简要的解题报告,详细会放在http://watashi.ws/blog/touhou-monthly/touhou-monthly-solutions/

ZOJ3373. Gensokyo Forbidden Words

tag: 通配符(glob), 正则表达式(regex), 字符串(string), if-else
详细解题报告和标程
根据题目描述给定的规则,对”.”, “?”, “*”, “[]“里的第一个”!”变化一下就好了。输入可能有很长很长的一行,getchar推荐。

ZOJ3374. ⑨ Adjacent Numbers

tag: 动态规划(DP), 计数(counting)
详细解题报告和标程
先考虑,从站成一列的n个人里选m个人,不出现9连号的方案数,这个动态规划可解。然后确定一个位置,把环剪开成链,枚举剪开的地方到底是几连号,就可以求出围成一个圈的n个人里选m个人,不出现9连号的方案数。

ZOJ3375. Imperishable Night

Comments 17 Comments »


pic

Comments 13 Comments »

ZOJ Monthly, July 2009

[F]ZOJ3227 Perfect Cherry Blossom 0.00% (0/13)
[H]ZOJ3229 Shoot the Bullet 12.12% (4/33)

ZOJ Monthly, November 2009

[E]ZOJ3263 Immaterial and Missing Power 0.00% (0/8)

标题是照着vls的《我出过的题目》取的,确切的说是我出过的以東方Project为背景的,已经公开的题目。因为今年Summer2010暑期集训新手上路选拔和七月校队选拔中,我又出了11道东方系列的题目,以在这个月办好一场东方专场ZOJ月赛(详情:acm_x_touhou),用把力,把去年暑假的yy变成现实。去年出的这三题当然离办一场Monthly还有无限远,不过今年提前准备,再加上vout和猛犸的强力支持,现在已经有了充足的各种难度,各种类型的东方系列备选题目能够支援ZOJ八月的月赛了。届时希望广大acmer和touhou fans捧场 :D

ZOJ3229 Shoot the Bullet (文花帖)

downloadsource code (ZOJ3229.cpp) [FlowNetwork, 上下界最大流]

在未来的n天中,文文要强拍幻想乡的mm们为《文々。新闻》增加8g素材。但是每天她只能对某些mm拍照,并且所拍照片数不能过多或过少,每天总的照相数也有上限,而n天内她所拍某个mm的相片也有最低要求。在满足所有这些要求的前提下,希望最后拍的照要尽量多,求任意一个最优方案。

很裸的上下界最大流,构图算法都没什么需要多说的了,有模块就直接秒杀了。ZOJ上就这题的AC数到了三位数,不知道有没有人用来测模块。

ZOJ3227 Perfect Cherry Blossom (妖々夢)

downloadsource code (ZOJ3227.cpp) [DP, SegmentTree]

 暖和的季节结束了,边境被银白色的幻想所封闭。
 人们在这不知道什么时候结束的漫长冬天中,也变得安分起来了。
 

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


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 »