ZOJ Monthly, July 2010
[A]ZOJ3352 Boring Board Game 10.97% (27/246)
[B]ZOJ3353 Chess Board 11.94% (8/67)
[C]ZOJ3354 DoIt is Being Flooded 3.22% (1/31)
[D]ZOJ3355 Football Gambling I 37.61% (612/1627)
[E]ZOJ3356 Football Gambling II 4.65% (115/2472)
[F]ZOJ3357 Football Gambling III 11.11% (1/9)
[G]ZOJ3358 Green Dam Girl 11.15% (28/251)
[H]ZOJ3359 Penalties Kick 13.23% (376/2841)
[I]ZOJ3360 Stranger Calendar II 5.26% (1/19)
[J]ZOJ3361 Yellow Card and Red Card 4.51% (16/354)

啊啊啊,我太圡了,这次Monthly选题没有控制好,选了太多的简单但容易WA的题目(都是足球题太多害的);然后从最后结果来看,应该只放9道题就够了,B/C只放一道就好了,I没有人做真的很意外,J也是;E和H骗了无数的提交,结果导致ZOJ一段时间极卡。下回Monthly选题要注意了。

继续广告:8月22日的ZOJ Monthly, August 2010是我yy了一年准备的东方专场ZOJ Monthly。欢迎捧场,选题控制应该会比这场好吧(多分^。^)

然后,解题报告:

warning: —以下文字各种剧透—


ZOJ3352 Boring Board Game

downloadsource code (ZOJ3352.cpp) [game theory, 记忆化搜索]

在有向无环图上的博弈游戏,每次可以把白旗或黑旗沿着边移动到另一个点上,如果不能移,那么要付给对方一定的钱。初始这个钱为1,如果移动白旗到标号为x的点上,那么这个钱加x,如果是移动黑旗,那么减x。

记录dp[i][j][k]表示白旗在i,黑旗在j,当前赌注为k的最大收益,因为是有向无环图,所以状态不会有环。于是直接记忆化搜索就好了,每次枚举白旗的移动或黑旗的移动取最大值,如果不能移动,那么就是-k。时间复杂度O(n^4),空间复杂度O(n^3)。

ZOJ3353 Chess Board

downloadsource code (ZOJ3353-2.cpp) [enumeration, greedy, bitwise]

这题不过是光灯问题的一个加强版,所以可以参考ZOJ1354 Extended Lights OutZOJ2977 Strange Billboard枚举第一行,然后贪心的做法。这题需要用位运算优化,否则可能会TLE。注意这题中第2个pattern不满足枚举第一行然后贪心的条件,不过类似的可以枚举最后一列然后贪心。第3和第4个pattern类似,也可以通过旋转board和pattern来转成枚举第一行的情况。

downloadsource code (ZOJ3353.cpp) [gaussian elimination]

关灯问题的另一个做法是用亦或方程组的高斯消元法,由于要求最优解,最后需要枚举所有自由变量的组合,求得最优解。解的个数显然不超过2^15种,实际跑得比上面的方法快。

ZOJ3354 DoIt is Being Flooded

downloadsource code (ZOJ3354.cpp) [DAG, sp(dijkstra), DisjointSet]

海平面不断上涨,最后将会把DoIt淹没,DoIt每年的经济收入又一个数字a和这年各个岛屿的大小通过公式计算求出。给出许多查询的年份和对应的数字a,问该年的收入。

首先注意题目里说的,海水只会流到相邻的格子里,所以一个各自未必在海平面高于自己的时候就被淹了,比如sample中间的格子,只有在第4年才会被淹。首先处理这一问题,方法就是类似最短路的先对所有的点重新标号,得到每个点真正被淹没的时间。

之后就是对查询排序,然后从高到低,看那些格子升出了水面,这些格子可能会和周围的格子练成岛屿,这个部分通过并查集来做就好了。然后我是用map<int, int>来记录大小为first的岛屿有second个,以回答查询。事实上这部分可以自己通过一个list来做到O(1)的处理,不过O(lgn)也足够了。

ZOJ3355 Football Gambling I

downloadsource code (ZOJ3355.cpp) [math]

赌球押胜平负的赔率风别是a, b, c,押n元中了可获得floor(odds * n)。问是否有可能稳赚不赔。

假设在胜平负上风别压注x, y, z,那么有

\left\{\begin{array}{rcl}ax&>&x+y+z\\by&>&x+y+z\\cz&>&x+y+z\end{array}\right.

于是可以推出
\frac{1}{a}+\frac{1}{b}+\frac{1}{c}<1

这一必要条件。同时如果上式成立,那么按b*c, c*a, a*b的比率去押注,就可以做到稳赚不赔,所以也是充分条件。

题目说了都是两位小数,所以最好还是整数运算。不过就像xgy说过的“与double斗,其乐无穷”,选择合适的eps还是能AC的。

ZOJ3356 Football Gambling II

downloadsource code (ZOJ3356.cpp) [greedy, enumeration]

假设现在有s的钱,问在最悲剧的情况下,赌球后能拥有的最多的钱。

从0到s枚举并模拟下注总金额,每一次都应该把这一元钱押到当前三种情况中收益最小的一个。一个优化就是先把大部分的钱都按b*c, c*a, a*b的比率下注,然后one by one的枚举。集训的时候我暴力枚举TLE了,而范叔只枚举-3到+3瞬秒,不过放Monthly的时候我把实现加到暴力枚举全部也能AC了。

ZOJ3357 Football Gambling III

downloadsource code (ZOJ3357.cpp) [geometry]

题目相当于告诉你许多aix+biy>c和aix+biy<c这样的不等式,然后问ax+by的最大值和最小值。

每个约数条件对应一条直线(一个半平面),问题就是二维平面的线性规划,单纯形或半平面交是比较不靠谱的。有O(n)的随机增量法,也有O(nlgn)的求凸包的算法,不过这题只要用很简单的O(n^2)算法求出凸包上的关键点就好了。枚举每条直线,然后再枚举其余直线,用这些直线去且所枚举的直线,最后可能切没了,那么说明这条直线最后最后不属于凸包的一部分;否则切成一个线段,那么这个线段的两个端点就是凸包的顶点,也就可能取得最大最小值的关键点;根据题目描述,不会出现切成射线的情况。

ZOJ3358 Green Dam Girl

downloadsource code (ZOJ3358.cpp) [sp(floyd), DP]

绿坝娘包养计划。绿坝娘为第i名队员花季护航一天,可分别在第一天,第二天,以后每天分别获得ai, bi, ci的收入。而从第i名队员处搬到第j名队员处需要对应的花费。如果钱不够就不能搬,但一天可以搬多次,而且如果搬到了同一队员处,仍然从第一天开始算。

首先用floyd处理搬运费用,求出在从任意一名队员处帮到另一队员处的最小花费。然后就是一个DP,dp[i][j][k]表示第i天,绿坝娘为第j名队员花季护航,是连续第k天,其中k为0, 1, 2,的最大收益,每次可以选择搬,转移到dp[i][j'][0],或不搬,转移到dp[i][j][min(k + 1, 2)]。

ZOJ3359 Penalties Kick

downloadsource code (ZOJ3359.cpp) [simulation, if-else]

给你11*3次射点球的预测,要求按点球大战模拟规则输出结果和比分。

总之小心,别漏了某些情况或把某些情况写错。WA的话生成点数据和AC的程序对拍一下吧。

ZOJ3360 Stranger Calendar II

downloadsource code (ZOJ3360.cpp) [search(dfs/bfs)]

题目就是要求n1, n2 …使得1/n1-1/n1n2+1/n1n2n3-…等于给定的A/B

有两种闰年,这里只考虑A/B<1/2的,另一种情况的解和1-A/B是一样的。然后假设n1=C,那么应该有A/B-1/C=(AC-B)/BC,后面的分数,分母都有一个C,乘上去,取相反数,得到(B-AC)/B,这个就是1/n2-1/n2n3+…需要满足的条件,递归的做下去。

实现的时候就是一个dfs或者bfs,从上面推倒知道ni都是不超过B的,而且搜索的状态不超过B的所有因数的欧拉函数值的和。

ZOJ3361 Yellow Card and Red Card

downloadsource code (ZOJ3361.cpp) [simulation, if-else]

给你个相比Penalties Kick更复杂的世界杯红黄牌规则和冠军的7场比赛的红黄牌记录,问哪些队员缺席了哪些比赛。

与点球大战一样,注意处理各种情况。数据说了,裁判不靠谱,所以可能会给明明不在场上或已经红牌罚下的队员继续发卡,这些卡应该被54的。和H一样,都是简单没什么算法,但又容易WA的题。

41 Responses to “ZOJ Monthly, July 2010解题报告”
  1. Yuan says:

    请问下,3353这题
    “解的个数显然不超过2^15种”
    那个灯的总数是n*m, 应该怎么确定自由变元不超过15?

  2. 求 zoj2731源代码

  3. Yuan says:

    请问3356 的那个优化怎么写呢?
    我写了后还是时间差不多~~应该是我写的有问题了

  4. 刘奚睿 says:

    谢谢你的解答 贪心的方法我搞懂了 希望你能解决我高斯消元的问题

  5.  
Leave a Reply