Posts Tagged “容斥原理”


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中的H题Special Special Judge III怎么用容斥原理做。确实我只在解题报告中提了一句可以这么做,然后就丢下了一段python代码跑了。现在来详细解释一下如何运用容斥原理求一个Hyperrectangle被Hyperplane切割后剩余部分的体积。这里假定n维空间内的Hyperrectangle为

\{(x_1,x_2,\cdots,x_n)|0\le x_1\le X_1, 0\le x_2\le X_2, \cdots, 0\le x_n\le X_n\}

而对应的Hyperplane为
a_1x_1+a_2x_2+\cdots+a_nx_n=b

那么我们实际要求的就是Convex
\{\mathbf{x}|0\le x_i\le X_i,\mathbf{a}^T\mathbf{x}\le b\}

的体积。

不妨先考虑两个二维平面上的例子:

mp-case-1

\{(x,y)|0\le x\le 4,0\le y\le 3,x+y\le 5\}

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