Andrew Stankevich’s Contest #3
ZOJ2361 SGU209 Areas 18.12% (62/342)
ZOJ2362 SGU210 Beloved Sons 45.40% (173/381)
ZOJ2363 SGU211 Strange Counter 28.12% (63/224)
ZOJ2364 SGU212 Data Transmission 11.95% (104/870)
ZOJ2365 SGU213 Strong Defence 36.40% (83/228)
ZOJ2366 SGU214 Weird Dissimilarity 13.31% (84/631)
ZOJ2367 SGU215 PL/Cool 22.91% (33/144)
ZOJ2368 SGU216 Royal Federation 24.80% (64/258)
ZOJ2369 SGU217 Two Cylinders 15.71% (94/598)

还是先推荐两道构造题2363 Strange Counter2368 Royal Federation2361 Areas是一道coding量很大的计算几何题,而2367 PL/Cool是一道考验基本功的蘑菇题。2363 Data Transmission是一个值得再研究的分层图的阻塞流问题。

ZOJ2361/SGU209 Areas

downloadsource code (ZOJ2361.cpp) [geometry, 计算几何, dfs]

题目描述很简单,问给定的n条线把平面分出了几个有限的区域。

规模为80,不得不ym那些用优化的半平面交轻松AC这道题的牛人们,但我觉得这不能算a right approach。

我的算法是O(n^2lg(n))的。首先处理出所有交点,并给所有点标号,注意合并相同的点。然后给直接相连的两点之间连两条有向边,处理成邻接表。显然至多有O(n^2)个点和O(n^2)条边。最后算法的核心就是枚举所有边作为起始边,“走”出所有的区域。“走”的算法是这样的,每走到一个顶点,就找从这个点出发相对当前边的方向最“左”的边。如果最后回到了最初枚举的起点就找到了一个有限区域。如果这条边不在当前边的方向的“左”边说明这不是一个有限区域。否则更新当前边继续找。对于“走”过的边标上标记,则以后遇到可以不再继续搜下去。而在找从一个点出发相对当前边的方向最“左”的边的时候可以先对所有边按极角排序再二分查找。其实这个找的过程在纸上模拟还是非常简单的,不过变成代码就可能有各种bug了……

ZOJ2362/SGU210 Beloved Sons

downloadsource code (ZOJ2362.java) [augment, bigraph]

国王要给王子们安排婚事,每个王子都有一个权重Ai,目标是使所有与心爱女孩结婚的王子们的权重的2范数最大。当然是一夫一妻……

那个平方和开根号的公式只是一个烟雾弹而已。不知道有没有直接秒杀此题的二分图最优匹配模块。实际上由于题中的权值有由二分图X部分的顶点唯一确定这一特殊性质,所以只要从按这个权值从大到小的顶点出发找增广路,求一个二分图最大匹配就可以了。由增广路的算法知道,如果从x开始找到一条增光路并增广,那么X中原先匹配的顶点依然匹配,此外x也匹配了;如果从x开始找不到增广路,那么说明要么不存在包含x的匹配,要么要使x匹配,必使一个X中原先匹配的顶点不匹配。于是可以证明,按权值降序找增广路所求得的匹配一定是最优解。

ZOJ2363/SGU211 Strange Counter

downloadsource code (ZOJ2363.cpp) [构造]

一种神奇的计算机内的二进制数字,每一位可以是0/1/2,于是表示不唯一。这种计算机的神奇之处在于,从0开始,不断地加上一些2的幂次的数,可以保证每次只有不超过四位数字发生改变。题目就是让你模拟出这种机器。

一般的思路就是保持格式总能保持某种不变性,总之构造题就是很用力很用力的想啊想。我的算法是始终保持数字具有/(21*0[01]*)*/的形式,当+2^p的时候,记t>p是第一个2出现的位置,而z<t是随后的第一个0的位置,那么

if (p >= z) then
	changeDigit(p, +1)
	changeDigit(t, -2)
	changeDigit(t + 1, +1)
elif (getDigit(p) > 0) then
	changeDigit(p, -1)
	changeDigit(p + 1, +1)
else
	changeDigit(p, +1)
endif

这样经过不超过三次(比题目要求的四次还优 :D )变化后,依然保证数字是/(21*0[01]*)*/形式的。

算法显然还有很多,求更多的算法

ZOJ2364/SGU212 Data Transmission

downloadsource code (ZOJ2364.cpp) [blocking flow(阻塞流), FlowNetwork, Dinic, HLPP, MPM]

求一个分层图的阻塞流(blocking flow)。(n = 1.5k; m = 0.3M)

看到分层图和阻塞流,首先想到的就是Dinic算法。Dinic算法就是通过距离标号构造分层图,再在分层图上求阻塞流,每次复杂度O(n*m),最多求n次,当然这里虽然只要求1次,还是TLE了。网上搜了一下,发现很多人先贪心预流(greedy preflow),再用Dinic算法求阻塞流就AC了。而在楼教主的解体报告中则提到,HLPP(highest-label preflow-push, 最高标号预流推进),虽然理论复杂度是O(n^3),但能轻松搞定这种图。于是我写了一个HLPP,最终AC了此题。此题SGU的spj应该有bug,因为我原先在代码中加入了gap优化,导致虽然求出的最大流流量是对的,但边上的流量是错了,在SGU却AC了。

前一段时间看Algorithms Design Techniques and Analysis里介绍的MPM算法(这是三个人的名字:Malhotra, Pramodh-Kumar and Maheshwari)。这个算法也是在分层图上求阻塞流,最多求n次,与Dinic不同的是,求阻塞流是按每点的吞吐量(throughput)增序去推拉流量,每次的复杂度为O(n^2),于是理论复杂度在题目时限以内。可能是我实现的比较搓,实际运行不比HLPP版本快多少。

不过这些算法都没有很好的题目中分层图的性质,求更好的算法

ZOJ2365/SGU213 Strong Defence

downloadsource code (ZOJ2365.java) [bfs, greedy, SP(shortest path)]

一个有向图,要给一些边染色,使得所用的颜色最多,且S到T的任意路径的都包含所有颜色。

颜色种数就是最短路的长度d,给距离标号为i<d的边染上第i种颜色,给所有距离标号≥d的边染上第d种颜色。因为任意路径都包括距离标号为1到d的边至少一条,所以S到T的任意路径的都包含所有颜色。另一反面,考虑最短路只有d条边,所以这已经是最优解。

ZOJ2366/SGU214 Weird Dissimilarity

downloadsource code (ZOJ2366.cpp) [DP]

字符c1和c2的距离为d(c1, c2),已知两个字符串s和t,现在要找长度相等的两个字符串a和b,使得s是a的子序列,t是b的子序列,且a和b的距离最小。

做法类似O(n^2)的LCS。记dp[i][j]为匹配了s的前i个字符和t的前j个字符,每次转移有两类情况。要么让a和s匹配一个字符,那么对b,贪心一个字符使得它与a的距离最小,更新dp[i+1][j];更新dp[i][j+1]的情况类似。要么同时让a和s匹配,b和t匹配,这时dp[i+1][j+1] <?= dp[i][j] + d(s[i], t[j])。

ZOJ2367/SGU215 PL/Cool

downloadsource code (ZOJ2367.cpp) [Trie, DisjointSet, calculator, parser, simulation]

为PL/Cool写一个解释器,它有两种操作:define op1 op2把以后所有的op1都用op2替换,替换是可以一直迭代的,但重复define和产生环的define应该被无视;print expr,其中expr是个四则运算表达式,输出先根据define替换再表达求值的结果。

一句话:DEAD DO。我用Trie树维护变量表,我想用map<string, int>应该能省不少事。通过带路径优化的有根的并查集来维护define。最后print利用堆栈解析表达式,不知道递归下降会不会TLE。

ZOJ2368/SGU216 Royal Federation

downloadsource code (ZOJ2368.cpp) [构造]

将一个树形的国家分成一些省,每个省要有[B, 3B]的城市,且满足存在一个省会城市(不一定要再省内),使得所有该省的城市都可以不出省到达改省会。

递归地来做,并再构造的时候保持某种不变量。我的算法是这样的:假设某个节点数大于3B的子树又有大小为s1≤s2≤…≤sk的子树。对于其中si≤B部分如下扫描处理,把si加到集合中,如果总大小超过3B,则可以把一个大小在[B,2B)的子集删掉。考虑处理后的集合,如果它加上根后的大小小于B,那么把它们作为sk的子树,并递归;否则直接删掉。最后对于si≤3B直接删掉,对于si>3B递归处理。

算法应该不唯一,求更简洁的算法

ZOJ2369/SGU217 Two Cylinders

downloadsource code (ZOJ2369.cpp) [integral, math, numeric]

求轴垂直相交的两个圆柱的相交区域体积。

圆柱是个直纹面,假设r1以x轴为轴,r2以y轴为轴,则从z方向看过去,没个平行与xOy的平面所做的切面都是一个矩形,x方向长2*sqrt(r1*r1-z*z),y方向长2*sqrt(r2*r2-z*z),假设r1≤r2,那么答案就是

8\int_{0}^{r_1}{\sqrt{(r_1^2-z^2)(r_2^2-z^2)}}\,\mathrm{d}z

个人觉得,ACM题里做数值积分还是复合Simpson公式的性价比比较高
\frac{h}{6}\left(f(x_0)+4\sum_{i=0}^{n-1}{f(x_{i+1/2})}+2\sum_{i=1}^{n-1}{f(x_i)}+f(x_n)\right)

这是用Romberg和Gauss-Legendre n点公式做vbvan大神的某道题的教训……

10 Responses to “Andrew Stankevich’s Contest #3解题报告”
  1. Prime21 says:

    大神你好,能不能提供一份MPM算法的Data Transmission。很想学习一下。

  2. mrdotmoon says:

    我想问下2362的会不会不在最大匹配上取得最优值啊,比如9^2+8^2>1^2+2^2+10^2等等

    • watashi says:

      上面的解题报告已经给出了算法正确性的严格证明了
      最优值一定可以在按算法求得的最大匹配上取到

  3. Starvae says:

    你好,对于ZOJ2364/SGU212 Data Transmission这题,你说:“此题SGU的spj应该有bug,因为我原先在代码中加入了gap优化,导致虽然求出的最大流流量是对的,但边上的流量是错了,在SGU却AC了。 ”,题目要求的最大流流量是没有限制的吧,只要最后没有增广路就行了,比如这组数据:
    6 7 4
    1 2 2 3 3 4
    1 2 5
    1 3 3
    2 4 3
    3 4 3
    3 5 2
    4 6 3
    5 6 2

    如果我的答案是:
    0
    3
    0
    3
    0
    3
    0
    也是应该满足题意的吧,尽管会有比这更大的可行流存在~
    ~~?

  4. [...] [ZJU][2364][Data Transmission] Helanic Abyss Andrew Stankevich’s Contest #3解题报告 by watashi [...]

  5. RainFlying says:

    yyyyyyyyyyyyyyyyyyyyyyyyyyyym 大牛shi

  6. 死肥羊 says:

    顶shi哥!
    最近完全不知道自己在干什么~还是继续ZOJ最有爱!用力!

  7.  
Leave a Reply