Andrew Stankevich’s Contest #10
ZOJ2704 Brackets 12.52% (513/4095)
ZOJ2705 Dividing a Chocolate 20.60% (102/495)
ZOJ2706 Thermal Death of the Universe 16.01% (205/1280)
ZOJ2707 Equations System 12.18% (24/197)
ZOJ2708 Fool’s Game 38.46% (25/65)
ZOJ2709 Lottery 32.21% (48/149)
ZOJ2710 Two Pipelines 21.00% (71/338)
ZOJ2711 Regular Words 28.44% (357/1255)

所有题目都附上了我AC的代码,不过AC不等于没问题,如果代码显示或下载有问题,或者我的程序有错,请在comment中说明,我会尽快fix。这套题中的ZOJ 2705, 2707, 2708强烈推荐!

ZOJ2704 Brackets

downloadsource code (ZOJ2704.c) [bracket, greedy]

给定一个只含()[]的字符串,问其中最长的合法字串是什么。

要判断一个串是否合法,只要维护一个栈进行O(n)的扫描就可以了。但是枚举字串+扫描就O(n^3),肯定不靠谱了。事实上注意到,如果从左往右扫描到第i个,出现不合法的情况,那么前面无论保留什么,都是非法的,所以把栈清空,继续从位置i+1开始新的扫描,复杂度O(n)。代码是入门的时候c语言写的……

ZOJ2705 Dividing a Chocolate

downloadsource code (ZOJ2705.cpp) [Fibonacci, greedy, 逆推]

给定一个m*n(m和n均可以很大)的矩形,初始可以沿任意的整数位置分成两个矩形。然后始终让大矩形减小矩形,直到两个矩形相等,目标是最后的矩形面积最小。题目最后的说明要求:中间不能出现一个矩形大面积大于另一个的两倍的情况。可以说这道题的sample说明才是本体啊。

从描述中可以知道,完成第一刀之后后面的发展是确定的,但由于规模很大,我们不可能去枚举第一刀的情况。可以反过来思考,事实上,知道了最后的结果,比如最后是两个a*b的矩形,那么我们也可以反过来推出之前较大的那个矩形依次是2a*b, 3a*b, 5a*b, 8a*b …,这不正是著名的Fibonacci数列么。目标是a*b尽量小,也就是要找最大的Fibonacci数f,使得m%f==0||n%f==0,10^9内的Fibonacci数不过几十个,枚举就可以了,答案就是m*n-m*n/f。注意要用long long。

ZOJ2706 Thermal Death of the Universe

downloadsource code (ZOJ2706.cpp) [SegmentTree, floor/ceil, off-by-1]

给定一个长度为n<30000的整数序列,进行m<=30000次区间操作,每次操作就是使得区间内的数等于它们的平均数取整,取整根据当前总和与初始总和的关系,可能是floor或ceil。

用支持delete/replace和sum的线段树就能轻松完成要求,复杂度为O(m*lg(n))。线段树的删除通过懒标记实现,相关资料很多地方都能找到。如果你WA了,那么注意,数字可能是负数,确信你的负数的取整没有off by 1。

ZOJ2707 Equations System

downloadsource code (ZOJ2707.cpp) [math, number theory, if-else, polynomial]

给你一个系数在为F2={0,1},也就是模2运算下的多项式构成的二元一次线性方程组,试求解。

事实上这个多项式方程组的求解与整数方程组的求解并无实质性区别。对于求解

{ a1(t)x(t)+b1(t)y(t) = c1(t)
a2(t)x(t)+b2(t)y(t) = c2(t)

记D=a1b2-a2b1, X=a1b2-a2b1, Y=a1b2-a2b1

  1. D不是零(多项式),这种情况最简单,答案就是x(t)=X/D, y(t)=Y/D,如果不整除,那么无解,而这题的难点在于其余的退化情况;
  2. 如果D为零,但X和Y不全为零,这时候也无解;
  3. 如果有0+0=!0的情况显然也是无解的;
  4. 如果都是0+0=0,那么任意x(t), y(t)都是解;
  5. 最后,也是最关键的情况,就是方程组是冗余的,问题转为一个方程a(t)x(t)+b(t)y(t)=c(t)的情况。和解ax+bt=c(mod m)一样,我们用扩展欧几里德算法(extGcd)来求解。利用extGcd可以得到x’(t)a(t)+y’(t)b(t)=gcd(x(t), y(t))=g(t):
    • c(t)不整除g(t),那么无解;
    • 令c’(t)=c(t)/g(t),则x(t)=x’(t)*c’(t), y(t)=y’(t)*c’(t)。

此题中的多项式可以用一个vector<bool>来表示,而加减运算都等价于bool的亦或(xor, ^)运算。

ZOJ2708 Fool’s Game

downloadsource code (ZOJ2708.cpp) [bigraph, enumeration, 逆推]

题目介绍了一种简单的扑克游戏:开始A打出数字一样的一些牌,然后B总要大过这些牌。牌x比牌y的大,当且仅当它们花色相同且x大,或者x是给定的主(trump),而y不是。此后A继续出牌,但有一个限制,A大出的牌的数字必须已经被打出过。问谁必胜。

这题看似一个博弈问题,但往博弈方向却很难寻找到出路。由于A最初打出的牌是已知的,接下来的主动权应该在B上。类似与ZOJ2705中所说,我们再次从结果出发进行推倒推导。现在已知假设胜负已分,那么B胜的情况就是打出的牌中B都大过A了(存在一个满的二分图匹配),而B却无牌可打了(没有和打出的牌数字相同的牌)。那么如果牌局能不可能发展到这样一个状态,那么B必败无疑,否则B可能胜,事实上B必胜,接下来我们就来求这个必胜策略。首先B确定好最后打出牌的数字的集合,一共有2^(9-1)=256种,以A,B牌该数字的子集为二分图的点,cover关系为边,调用hungary算法,如果A都被cover了,那么B必胜。必胜的打法就是每当A打出一张牌,B就打出与之匹配的那张牌。

ZOJ2709 Lottery

downloadsource code (ZOJ2709.cpp) [Fraction, greedy]

给定一个数字n和一个字符串S,要求够造一个包含n个字符的集合,使得从中选出S的概率最大/小。概率不能为0,字符都要来自S,无序。

假设字符集大小为m,S里有xi个字符ci,集合里有yi个字符i,那么xi<=yi,Σyi=n,概率p=ΠCyixi/Cn|S|。要求pmax和pmin,不妨显令所有的yi=xi,然后one by one的加到Σyi=n。每次给yk加1,就等于对p乘p’=yk/(yk+1-xk),分析其性质知道,1) yk=xk时值为xk+1;2) yk越大值越小;3) xk越大,值随yk减小得越慢。

所以要求pmin,只要对最小的xk对应的yk一直++就好了。对于求pmax则要麻烦一点,可以维护一个最大堆,保存p’和xk的pair,每次pop出最大值,对yk++,再更新减小后的p’,push回堆中。

ZOJ2710 Two Pipelines

downloadsource code (ZOJ2710.cpp) [DP, geometry]

每个城市可以连到一个pipeline,费用的dis(p,l)*d。要求连接两个pipeline的城市数差距不超过c的前提下,总花费最小,需要输出方案。

利用计算集合求点到直线的距离,可以预先求出每个点到每个pipeline的cost。然后就是一个传统的二维动态规划,记dp[i][j]表示前i个城市有j个连到了第一个pipeline,则dp[i][j]=min(dp[i-1][j-1]+cost1[i],dp[i-1][j]+cost2[i])。最后取dp[n][(n-c+1)/2..(n+c)/2]中的最小值。

ZOJ2711 Regular Words

downloadsource code (ZOJ2711.cpp) [DP]

略。

类似的DP似乎出现得很多了。dp[i][j][k]=if i<=j<=k then dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1] else 0。这题需要大数。


后记

上回写大妈题的解体报告已经是去年这个时候的事了,当时做了Andrew Stankevich’s Contest #1 ~ #5。感觉收获很大,对自己再World Final上取得成绩也很有帮助,但此后就懒了,加上彩票哥说他打算写#6 ~ #10的解体报告,我就一直没了动静。写在校赛省赛将近,发现手也生了,于是开始补欠下的债……

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

    请问10套都有在ZOJ收录吗。我记得我在SPOJ做过几题。

  2.  
Leave a Reply