Andrew Stankevich’s Contest #4
ZOJ2559 The Smart Bomb 53.76% (321/597)
ZOJ2560 I Just Called … 21.05% (76/361)
ZOJ2561 Order-Preserving Codes 18.28% (126/689)
ZOJ2562 More Divisors 30.14% (322/1068)
ZOJ2563 Long Dominoes 37.94% (148/390)
ZOJ2564 The Magic Wheel 17.11% (83/485)
ZOJ2565 Cracking SSH 50.25% (98/195)
ZOJ2566 Periodic Tilings 33.81% (47/139)
ZOJ2567 Trade 16.66% (97/582)
ZOJ2568 Counting Triangulations 16.31% (101/619)
ZOJ2569 Unfair Contest 28.57% (64/224)

这套题居然有11道,还是有不少好题的,尤其是ZOJ2566 Periodic Tilings,非常好的一道题,利用数学结论,可以转换为美丽的图论。还有ZOJ 2568是非常不错的计算几何模型动态规划;ZOJ 2561也是动态规划,用到了四边形不等式优化;ZOJ 2567,上下界最小流。

ZOJ2559 The Smart Bomb

downloadsource code (ZOJ2559.cpp) [math]

给定三个圆的圆心,要求圆不能相交,但可以相切,要使三个圆的半径和最大,问三个圆的半径各应该是多少。

显然要使三个圆两两相切,设三角形三边为a, b, c,三个圆半径为x, y, z就有
\left\{\begin{array}{l}x+y=c\\y+z=a\\z+x=b\end{array}\right.
有唯一解。

ZOJ2560 I Just Called …

downloadsource code (ZOJ2560.java) [trie, if-else]

告诉我们一坨电话号码和电话费计费规则,要求一堆电话呼叫的总费用。

可以用Trie树来记录和查找电话和Region,然后就是按规则计费了。

ZOJ2561 Order-Preserving Codes

downloadsource code (ZOJ2561.java) [DP]

题目要求一种01编码方案,要求满足三点,1. prefix free; 2. order preserving(保序); 3. minimum weighted path length。

如果没有第二条要求,那么就是著名的Huffman coding(霍夫曼编码)了。有了这个限制之后,可以通过动态规划来做,dp[i][j]表示把[i, j)内的字符编码后的MWPL(minimum weighted path length),f[i][j]表示[i, j)内的权重和,那么dp[i][i + 1] = 0,dp[i][j] = min{dp[i][k] + dp[k][j] + f[i][j]},方案就是对[i, k)的原有方案加上前缀0,对[k, j)的加上1。这样O(n^2)的状态,O(n)的转移,会TLE,不过问题满足四边形不等式,于是可以优化到O(n^2)。不了解四边形不等式的可以Baidu或参考黑书。

ZOJ2562 More Divisors

downloadsource code (ZOJ2562.cpp) [math, number theory]

输入n,问不大于n的数里,哪个数的因子数最多。

对于质因数分解为p1^r1*p2^r2*…*pm^rm的数,有(r1+1)(r2+1)…(rm+1)个因子,为了让这个数尽量小,自然取p1=2,p2=3,p3=5…的质数,且有r1>=r2>=r3…。在10^16范围内,这种数不多,于是可以预处理出所有这种数和它对应的因数个数。

ZOJ2563 Long Dominoes

downloadsource code (ZOJ2563.cpp) [DP]

问一个m*n的grid被长度为3的多米诺牌铺盖的方案数。

状态压缩DP,转移只在三行之间,状态有三种(0, 1, 2)。我没怎么优化,跑了1s+才得到结果,于是交表……

ZOJ2564 The Magic Wheel

downloadsource code (ZOJ2564.cpp) [math, enumeration]

圆柱体的两个地面和中间各有n个点,要用n条线穿过上底面,中间和下底面的点,要求最短连接方案。

首先从上底面连到中间和从中间连到下底面是两个独立且一样的问题,于是我们考虑其中一个。我们记上面的点按逆时针顺序以此为ABCD…,下面的为abcd…,首先最优的连线显然不会走超过π,其次,最优方案里也不应该有两条交叉的连线,假设Ab和Ba交叉,那么互换以后Aa和Bb一定是更优解。所以我们可以先枚举A和谁连,随后就可以依次牵线,比如有Ac搭配,那么必有Bd, Ce…这样问题可以在O(n^2)内解决。不知道能不能利用二分在O(nlog(n))解决,没试过。
注意输入数据范围是[-2π, 2π],不是[0, 2π)!开始我WA在这里了。

ZOJ2565 Cracking SSH

downloadsource code (ZOJ2565.cpp) [DP]

动态规划,没发现什么很特别的地方。

ZOJ2566 Periodic Tilings

downloadsource code (ZOJ2566.cpp) [math, graph]

铺砖问题:给你一种地砖,问你是否能够铺满整个平面。

* World Finals – 2004/2005
* Shanghai (China)
* G. Tiling the Plane
You might find the following information useful: It is known that there are only two fundamentally different tilings of the plane, the regular tiling by squares (chessboard tiling) and the tiling by regular hexagons (honeycomb tiling). A polygon can therefore tile the plane if and only if it satisfies one of the following two conditions:
1. There are points A, B, C, D in order on the polygon boundary (the points are not necessarily vertices of the polygon) such that the polygon boundaries from A to B and from D to C are congruent and the boundaries from B to C and from A to D are congruent. This leads to a tiling equivalent to the square tiling.
2. There are points A, B, C, D, E, F in order on the polygon boundary, such that the boundary pairs AB and ED, BC and FE, CD and AF are congruent. This leads to a tiling equivalent to the hexagon tiling.

利用上面这些信息,问题就变简单多了。首先我们把图形的边界扣出来,比如对sample1得到SSEENWNW这样的表示,设其长度为n,记m=n/2,然后如果substr(i,j)=reverse(substr(i+m,j+m)),那么w[i][j]=1,否则w[i][j]=inf,然后对w进行一次floyd,如果有w[i][i+m]<=3输出YES,否则NO。注意,对case

***
*.*
***

是NO,一开始找边界的时候应该判断是否有洞,WA在这里了。
据说有牛人搜索+剪枝过了,无比佩服。

ZOJ2567 Trade

downloadsource code (ZOJ2567.cpp) [FlowNetwork]

略。

上下界最小流。源到欧洲城市连边[2, inf],阿拉伯城市到汇连边[2, inf],可选的线路则对应一条[0, 1]的边。

ZOJ2568 Counting Triangulations

downloadsource code (ZOJ2568.java) [DP]

给定平面内的n<=50个点,问有多少种不同的consecutive triangulation。给定的点不会有三点共线的情况。

首先考虑minimal pretriangulation是个三角形的情况,那么consecutive triangulation的个数有:

  • count(A,B,C)=sum{count(P,B,C)*count(A,P,C)*count(A,B,P)},\forall P 在三角形ABC内
  • count(A,B,C)=1,三角形ABC内无点

这可以O(n^4)dp解得。

一般情况minimal pretriangulation是把n个点组成的凸包分成n-2个三角形,我们先把凸包上的点按顺序记为0,1,…,n-1
,用count2(a,b)表示由a,a+1,…,b-1,b这些点组成的凸多边形,那么有:

  • count2(a,b)=sum{count2(a,i)*count(a,b,i)*count(i,b)}, i = a+1,….,b-1

这可以O(n^3)dp解得。

答案就是count2(1,0),要大数。

ZOJ2569 Unfair Contest

downloadsource code (ZOJ2569.cpp) []

dead do

6 Responses to “Andrew Stankevich’s Contest #4解题报告”
  1. shllhs says:

    能问一下平面覆盖那题判断条件为什么是w[i][i+m]<=3?

  2. 复活也有 says:

    有木有qq啊!!可不可以加q啊!

  3. haha says:

    大牛 能发份ZOJ 2567的数据吗 用了一个模板 看了半天找不出哪里错了

  4.  
Leave a Reply