Posts Tagged “ZOJ”

接着上次4道比较简单的题的解题报告写。这次是Detect the Virus IIAn Unusual Problem的解题报告,主要涉及如何在C, C++, Java, Perl, Python中使用正则表达式与及无损压缩算法

ZOJ3440. Detect the Virus II

[regex, topSort]

题目简单来讲就是通过上下文无关语法(context-free grammar, CFG)描述了virus。问一个字符串是否存在virus形式的子串。题目保证描述不会有环/递归。

这题用正则表达式(Regular expressions, regex)来做是再自然不过了,比如sample就等价于下面这段perl代码:

# subparta:=fg|g
$subparta = qr(fg|g);
# parta:=a|b|c
$parta = qr{a|b|c};
# partb:=d|e[subparta]h
$partb = qr{d|e($subparta)h};
# virus:=[parta][partb][partb]
$virus = qr{($parta)($partb)($partb)};

printf 'abcdefghijklm' =~ $virus ? "YES\n" : "NO\n";
printf 'nopqrstuvwxyz' =~ $virus ? "YES\n" : "NO\n";

当然,因为代码是顺序执行的,所以我们调整了几个record的顺序。顺插一句,如果是函数式编程语言的话,那顺序就完全无关紧要了。于是问题就是给定的字符串能否匹配题目所描述的正则表达式,不过因为输入的顺序不确定,所以要麻烦一点,不过即然没有环,一个拓扑排序就搞定了(ZOJ3440watashi2.pl)。

Comments 15 Comments »

ZOJ在建站105个月之后迎来了第一百场比赛。

””\\( ̄ー ̄) ( ̄ー ̄)//””

办一场比赛来庆祝一下,这个想法最先是姐姐在邮件中提出的:

所谓求人不如求己,我自己的记录里是有序号的,所以知道我们目前有98场原创比赛和10场Practice了!喂,要不要庆祝一下第100场呀??!^_^

而我们在ZOJ2.1提供了几个脚本语言的支持后,也一直想办一场“非主流”的比赛。所以便有了今天的 Let’s Celebrate the 100th Contest on ZOJ! — An Unusual Contest powered by ZOJ Staff 这场9道非同寻常的题组成的9小时9分9秒的比赛。题目的准备还是比较匆忙的,事实上除了hhanger的一道题以外,所有题都是最近几天出的。感谢参与出题和验题的navi, hhanger, quark, hsys猛犸也钻地等童鞋,也感谢大家的捧场和支持。


Let’s Celebrate the 100th Contest on ZOJ!
100A ZOJ3437 Very Hard Problem 6.89% (28/406)
100B ZOJ3438 Tripartite Graph 62.28% (71/114)
100C ZOJ3439 Substitution Cipher 7.86% (36/458)
100D ZOJ3440 Detect the Virus II 0.00% (0/26)
100E ZOJ3441 Crack Me II 2.06% (2/97)
100F ZOJ3442 Complex Calculator 0.00% (0/1)
100G ZOJ3443 Bessel Function II 0.00% (0/0)
100H ZOJ3444 An Unusual Problem 5.12% (2/39)
100I ZOJ3445 1KB 9.09% (4/44)

下面是解题报告:


剧透的分割线,看题解之前建议您自己先思考一下


Comments 11 Comments »


ZOJ Monthly, November 2010
A ZOJ3427 Array Slicing 21.05% (56/266)
B ZOJ3428 Bug Races 25.00% (2/8)
C ZOJ3429 Cube Simulation 22.94% (131/571)
D ZOJ3430 Detect the Virus 8.23% (40/486)
E ZOJ3431 Escape! 9.90% (21/212)
F ZOJ3432 Find the Lost Sock 18.38% (257/1398)
G ZOJ3433 Gu Jian Qi Tan 17.41% (39/224)
H ZOJ3434 Hiiragi’s Sticks 23.68% (9/38)
I ZOJ3435 Ideal Puzzle Bobble 4.87% (2/41)
J ZOJ3436 July Number 13.15% (15/114)

因为这一段时间考试、作业、Project实在忙不过来。所以原定的三题比较难的题目都没有挂出来,所以平凡的题目好像多了一点。最近事情好多好烦,希望快点应付过去……

ZOJ3427. Array Slicing

downloadsource code (ZOJ3427.cpp) [regex, simulation, slice, splice]

其实就是要实现一个list的__getslice__和__setslice__操作(pretty solution in python),或者说splice(more pretty solution in perl)操作。题目关于slice只贴了wiki上一段话,没有详细解释,不过sample给得很强,我以为slice是common sense,可是我错了。

输入有点小麻烦,其实scanf可以轻松搞定的啦,规模非常小,所以暴力什么的就好了。STL里的vector::insert和list::splice都可以直接做题目中的操作。题目说数字都是100,不过list的长度可是可以长到很长的哦,xe一点倒是可以让用数组的TLE,不过这是签名题,没有那么坏啦,sample应该是非常强的了 :-)

ZOJ3428. Bug Races

downloadsource code (ZOJ3428.cpp) [Number theory, Pythagorean triple, Euclid's formula, counting]

Comments 19 Comments »


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 »