Posts Tagged “solution”


ZOJ Monthly, October 2010
A ZOJ3406 Another Very Easy Task 34.45% (317/920)
B ZOJ3407 Doraemon’s Cake Machine 9.41% (55/584)
C ZOJ3408 Gao 8.38% (29/346)
D ZOJ3409 KKV 53.33% (8/15)
E ZOJ3410 Layton’s Escape 9.90% (99/999)
F ZOJ3411 Special Special Judge 18.87% (127/673)
G ZOJ3412 Special Special Judge II 30.23% (13/43)
H ZOJ3413 Special Special Judge III 4.79% (13/271)
I ZOJ3414 Trail Walk 34.31% (257/749)
J ZOJ3415 Zhou Yu 12.08% (11/91)

发现十月份已经被Regional占满了,所以只好把Monthly安排在了国庆节的最后一天,星期四……最近事情比较多,所以Monthly的准备也比较仓促,题型和难度的控制可能不是很好,最后原计划的压轴题也没有整理出来,于是临时换上了一道水题(就是A题)。赛前moondy看了这套题就说要有无数队提前圆满了,还好最后这种事没有发生。

ZOJ3406. Another Very Easy Task

downloadsource code (ZOJ3406.pl) [regex]

题目虽然没有描述,但摘自wiki的sample input本身就是题目描述,再一看sample output应该马上就知道要做什么了:只要把超过2个字符的单词都转成由首字母加上省略字母个数加上尾字母组成的缩写就好了。

临时换上这题的想法原先是希望有人能快速用perl/python/php这些新加的脚本语言,通过正则秒杀掉。不过事实上只有一个人用了python写这道题。标程是用perl写的,非常短,顺带一提,这题的测试数据就是rfc2616

ZOJ3407. Doraemon’s Cake Machine

downloadsource code (ZOJ3407.py) [math, enumeration]
cake-3-5

这题问的就是n个小朋友分一个蛋糕,切m刀,在保证公平的前提小,最少要砍死几个小朋友克隆几个蛋糕。

Comments 24 Comments »


ZOJ Monthly, September 2010
A ZOJ3396 Conference Call 10.73% (208/1937)
B ZOJ3397 Change the Major 11.20% (13/116)
C ZOJ3398 Warden 1.50% (2/133)
D ZOJ3399 Classes Division 6.87% (9/131)
E ZOJ3400 Treasure Hunting 3.67% (16/435)
F ZOJ3401 Guitar 34.04% (96/282)
G ZOJ3402 Marble 10.00% (2/20)
H ZOJ3403 Strange Calendar III 8.78% (194/2208)
I ZOJ3404 Sticker 22.22% (2/9)
J ZOJ3405 Counting Factor Trees 11.62% (137/1179)

因为国内Regional网络赛时间安排的关系,把月赛挪到了九月初,也正好作为一次热身赛吧。希望大家都在接下来两周的网络预赛顺利,然后得继续看时间表安排接下来月赛的时间了。最近这段时间ZOJ各种抽风,好在Monthly的时候还是比较正常,最近ZOJ的dev工作总算看到的重新开始的可能,希望刚成立的ZOJ dev team能够搞好ZOJ 2.1的bug/feature的维护更新,还有传说中的ZOJ 2.7的开发。

Comments 32 Comments »


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 »