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刀,在保证公平的前提小,最少要砍死几个小朋友克隆几个蛋糕。

不妨假设竖着切了x刀,横着切了y刀,克隆了z次。首先考虑x=0的情况,这时显然要求n=m+1,而y=m, z=0就是最优解。
否则有
\left\{\begin{array}{rcl}x + y + z &=& m \\ 2x(y+1)+z &=& n\end{array}\right.
原本这题的规模是比较小的,只要从大到小枚举z,再解二元一次方程组(甚至再枚举x)就能过。出月赛的时候按我的方法加强了数据:注意到上面的两个方程可推出2x(y+1)-(x+y)=n-m=d,所以有x*y≤n,所以有x≤sqrt(n)或y≤sqrt(n)。于是可以从1到sqrt(n)枚举x,求出y,进而求出z;再从0到sqrt(n)枚举y,求出x,进而求出z;取所有合法解z的最小值。这个算法的复杂度是O(sqrt(n))的。事实上注意到x和y有一定的对称性,只要枚举x和y中的一个就足够了。

ZOJ3408. Gao

downloadsource code (ZOJ3408.cpp) [SP, DP, Booth]

前面cpcs和gao什么的其实和问题关系不大,题目就是要求一个10000个点,50000条边的图里,在所有最短路里,每个点各出现了几次,输出答案的最后10位数。

首先以0出发,利用SPFA或者Dijkstra求出由所有单源最短路组成的有向无环图G。然后在G上通过动态规划,可以分别求出0到节点v的最短路数和从节点v出发的最短路数,而经过包含v的最短路数就是这二者的乘积。动态规划应该按G的拓扑排序做,求G的拓扑排序最简单的方法就是按最短路求得的距离对节点排序。注意输出10位数是超int的,乘积也有可能超long long,由于只有最后一步有乘法,所以用大数也不会慢。但是更简单的办法是用布斯(Booth)乘法:

inline long long mul(long long lhs, long long rhs) {
	long long lhs2 = lhs % 100000;
	long long rhs2 = rhs % 100000;
	return ((lhs / 100000 * rhs2 + rhs / 100000 * lhs2) * 100000 + lhs2 * rhs2) % MOD;
}

ZOJ3409. KKV

downloadsource code (ZOJ3409.cpp) [geometry, physics]

一个基本的空间解析几何模拟题,没什么复杂的算法,只要简单的模拟就好了。关键在于如何根据当前速度矢量v0,新的速度矢量v的方向w和这两个矢量的差w=v-v0的模求出新的矢量v。两个矢量的差的模可以通过动量守恒定律来求得,知道了w=v-v0的大小,关键是求它的方向。考虑v0关于v的切向分量v0p和法相分量v0n,还有w关于v的切向分量wp和法相分量wn,那么显然要有v0n=-wn才能保证新的速度矢量的方向满足题意要求,而知道了|w|和wp,wn只有方向正好相反的两种取值,显然取与v同向的才能使所需时间最小,而最后v=v0p+wp。中学时代做了这么多的物理题,应该很熟悉这种切向法向的分解了吧。至于如何求切向向量,就是个简单的点积;求法向向量,就是一个叉积或减法。

downloadsource code (ZOJ3409p.py)

ZOJ3410. Layton’s Escape

downloadsource code (ZOJ3410.cpp) [greedy]

Layton逃脱需要通过N个陷阱,对于i号陷阱,可以选择花Ti时间移除,或者不移除而损失1点血,并且必须在时间Di内通过。题目要求通过所有陷阱最少要损失多少血,如果不可能,输出-1。

注意没有要求按顺序通过所有陷阱,这个顺序是可以自由决定的。于是可以贪心,贪心方法如下:按照Di从小到大对所有陷阱排序,然后扫描处理,如果累计用时T≤Di,那么什么也不需要损失血就可以移除所有陷阱,继续处理下一个陷阱;否则,必然要损失血,通过损失血来换取时间,所以必然选择放弃移除花费时间最多的陷阱j,T-=Tj,HP–,直到有T≤Di。

ZOJ3411. Special Special Judge

downloadsource code (ZOJ3411.py) [DP, BigInt]

概率无非是Accepted的output数除以总的output数,总的output数就是(b-a+1)^n,而Accepted的output数可以通过动态规划求解。记dp[i][j]表示前i个数,总的误差为j,那么就有dp[i][j] = sum{dp[i - 1][j - abs(x[i] – k)] | a ≤ k ≤ b},初始dp[0][0] = 1,Accepted的output数为sum{dp[n][j] | 0 ≤ j ≤ m}。大数需要。

ZOJ3412. Special Special Judge II

downloadsource code (ZOJ3412.cpp) [DP, NumberTheory, Inclusion-exclusion principle]

动态归划,状态依然是dp[i][j]表示前i个数,总和为j。转移的关键是求得[x, y]区间内的数b[i]和a[i]的最大公约数g可能的取值和对应的b[i]的个数。显然gcd一定是a[i]的约数,所以可以通过枚举a[i]的约数来枚举g,然后要求[x, y]区间内有多少b[i]满足gcd(a[i], b[i]) = g。这个只要转为求得[0, y]区间内有多少不同的数b满足gcd(a[i], b) = 1就可以了。如果y = a[i] – 1,那么这就是欧拉函数,而对于一般情况,这个问题可以通过容斥原理得到求解。

ZOJ3413. Special Special Judge III

downloadsource code (ZOJ3413.cpp) [if-else, geometry, Inclusion–exclusion principle]

关键要注意特殊情况的处理:

      如果a=b=0,就有p=q=0,那么这时的答案就是0或1,当x+y≤=k时为1,但是判断的时候要用x+y≤=k+EPS,否则很可能会WA,比如”1.1 2.2 0 0 3.3″这个case;
      a和b中有一个等于零,这个就是线段上的概率,为对应长度比,很简单;
      a和b均不为零,那么就是平面上的概率,为对应面积比。

求面积比的方法有几种:首先因为问题比较简单,所以可以if-else分情况求面积,这个不推荐;二是直接利用半平面交,贴模块倒是很挺轻松的,我的cpp程序也这么做了,但同样不推荐;最好的办法应该是用容斥原理来求,非常好写,而且不会遇到计算几何可能有的诡异问题,而且即使问题进一步复杂,比如扩展到3维的体积比或更高维的时候,这个方法依然有效,下面是这个方法的python版本。

downloadsource code (ZOJ3413p.py)

ZOJ3414. Trail Walk

downloadsource code (ZOJ3414.cpp) [math, geometry]

以飘渺水云间(88, 浙江大学最大的BBS)FatMouse(FM也是浙大集训队的指导教师)发起的毅行活动为背景的签名题。我参加过两次毅行,包括历史上最简单的一次和历史上最大规模的一次,也是最后一次。算法很简单,先求出路线总长度,然后求出两个CP间的距离,最后沿着线段走并模拟就好了。

ZOJ3415. Zhou Yu

downloadsource code (ZOJ3415.cpp) [math]

这题最初的规模是只要用和ZOJ3329 One Person Game类似的算法(hhanger的解题报告),就可以在O(n)复杂度AC,或者直接用解三对角方程的追赶法就能AC的,也有人“找递推规律”AC了。之所以会加大复杂度,是因为赛后asmn推出了O(1)的公式,当然即使不知道有这么一个O(1)的公式,利用中间对角方程的系数相同是可以得到O(log(n))复杂度的算法的;因为近似解在规模大的时候精度非常高,也可以规模小的时候O(n)求解,规模大的时候输出近似解。

by asmn

此题的公式如下,具体推导过程参见证明

clip_image002

24 Responses to “ZOJ Monthly, October 2010解题报告”
  1. zxz says:

    shi哥 小弟最近在学习perl 就在zoj上进行了一些尝试
    但是发现perl的输入的处理很麻烦 如果用split很耗时间
    希望能提供一些好的输入方法 或者在oj上提供一些perl的simple program 最好能测试一下perl性能并适当放宽时限

    • watashi says:

      这个问题很多语言都有的,没有办法,OJ上就是很多题连Java都不可能AC,更不要说python和perl了
      最近加的题TL稍微宽点,规模小的题应该还是可以过的
      关于最后一个feature我们也考虑过,但是近期应该不会在现在这个版本的ZOJ上改动,如果可能,会在未来开发的版本加入

  2. yygy says:

    不是2的问题,像1000000 999999这种数据就精度不行

  3. yygy says:

    那样做的话,会有误差,我WA掉了。你有没有AC啊?

  4. yygy says:

    是不是还用追赶法啊?然后系数的话不是用O(n)求的,而是利用对角系数一样可以用矩阵乘法来求

    • watashi says:

      差不多,就是把O(n)的算法写出来就会发现实际上是做了n次完全一样的迭代,于是可以用矩阵乘法优化到O(lg(n))

  5. yygy says:

    ZOJ3415. Zhou Yu
    可不可以不用公式啊?

    • watashi says:

      可以啊,矩阵乘法复杂度是lg(n)的,前面有人问过了

      • yygy says:

        怎么个矩阵乘法啊?我用矩阵乘法,精度不够高,WA掉了。
        我是把g(0)表示成g(n)的线性组合的,g(0)=a*g(n)+b;
        g(0)=0;
        g(n)=-b/a;

  6. yygy says:

    ZOJ3415. Zhou Yu
    用O(n)的算法会TLE吗?

  7. Yuan says:

    请问
    ZOJ3413. Special Special Judge III
    这题那个容斥的做法是什么意思呢?
    我看得不太懂那个代码…
    能解释下吗?
    多谢了

  8. lijunle says:

    ZOJ3410. Layton’s Escape 数据有点弱。
    遍历的时候,对于一个被吃掉的情况,应该用while不断选出最大耗费时间的陷阱。
    而我之前由于忘了,所以使用了if,结果AC。
    估计是数据有点弱,通知一下watashi大牛加强一下。

  9. mark1989 says:

    3451 zhouyu 这题在得到三对角方程后怎么利用中间系数相同得到 lg(n) 的算法?
    麻烦具体说一下。

    • watashi says:

      那个for循环里面的操作始终是一样的,其实不就是一个矩阵乘法么,所以换成O(lgn)的矩阵乘法就好了

  10. WJMZBMR says:

    。。就我们队圆满了囧。。。。

  11. lalala says:

    Python的时限能不能放宽一些

    • watashi says:

      @,@ 这个问题我们考虑过,出于一下两个原因没有做:
      1. 我们觉得选择语言的时候应该知道获得便利的同时也有风险,所以选python就有可能超时,应该自己权衡;
      2. 目前要实现这一点需要改ZOJ代码,ZOJ 2.0设计的时候没有考虑到这一点,但我们非常不愿意在已经准备淘汰ZOJ 2.0做这件事,而且ZOJ 2.0太buggy,风险很大。所以有可能的话,这个feature会出现在预想中的ZOJ 2.7里。

      不过目前ZOJ上python速度确实过慢,我们准备在近期换一个速度好不少的python解释器

  12.  
Leave a Reply