Andrew Stankevich’s Contest #7
ZOJ2604 Little Brackets 25.07% (250/997)
ZOJ2605 Under Control 28.44% (93/327)
ZOJ2606 Holidays 8.54% (27/316)
ZOJ2607 Laboratory 25.00% (104/416)
ZOJ2608 Maps 27.02% (20/74)
ZOJ2609 Crazy Painter 23.23% (89/383)
ZOJ2610 Puzzle 28.92% (105/363)
ZOJ2611 Quest 21.27% (30/141)
ZOJ2612 Stable Sets 29.43% (88/299)

Codeforces也开始挂ASC了,这我才想起,ZOJ上11套ASC的解题报告我还差一份作业没交呢,于是在此补上。目前把ZOJ上的ASC打完了,期待Codeforces放出更多的ASC。代码除了通过解题报告中的链接访问外,也可以在github上watashi/AlgoSolution(README)找到。


—-剧透的分割线—-

ZOJ2604 Little Brackets

downloadsource code (ZOJ2604.py) [Bignum, DP]

问最深嵌套恰好位k层且长度为2n的匹配括号的序列个数。

这种题一看就想到了DP,我们用dp[n][k]表示长度为2n深度不超过k的括号序列个数,那么答案就是dp[n][k]-dp[n][k-1]。

  • 边界条件:dp[0][j] = 1
  • 递推公式:dp[i][j] = sum{dp[i-k][j] * dp[k-1][j-1] | 0<k≤i}

ZOJ2605 Under Control

downloadsource code (ZOJ2605.cpp) [bfs]

一个在(x,y)文明程度为d的城市所控制的区域是满足|i-x|≤d+1 && |j-y|≤d+1 && |i-x|+|j-y|≤d+2的点组成的区域。一个文明所控制的区域是最小的包含其n个城市所控制区域的并,且补集中不含悬挂点的区域。所谓悬挂点就是不包含于任何2×2区域的点。

本题的规模非常小,所以可以直接求出文明所控制的区域中的所有点。首先根据输入,将每座城市所控制的点加入一个集合中。接下来就是要找出悬挂点并加入集合中。很显然,悬挂点只会出现在一个集合中的点的八邻居中。于是,每往集合内加入一个新的点,我们就将它不在集合中的八邻居加入待检查队列中。每次从队首取出一个点,根据定义检查它是否是悬挂点,直到队列为空。

ZOJ2606 Holidays

downloadsource code (ZOJ2606.cpp) [Date, DP]

题目按发生顺序给定Ys到Yf这几年间的n条假期新增和取消记录,但记录发生的年份并没给出。问这段时间最多有几天的假期,并要求输出对应方案。

从题目很容易想到用dp[k][y]表示第k条记录发生在第y年的最优解,这个dp本身是很简单的。麻烦之处在于对日期的处理,虽然不算难,但有许多容易出错的地方。由于本题的数据范围不大,可以用暴力一些的O(n*m^2)的算法,要改写成O(nm)的算法也不难。

ZOJ2607 Laboratory

downloadsource code (ZOJ2607.cpp) [Math]

将一个长方形用一条水平线和一条垂直线分成四块区域,要求所得的面积分别大于等于A、B、C、D,问原长方形的最小面积。
问题也可以描述为


\begin{array}{ll} min & (p_1+p_2)(q_1+q_2) \\ s.t. & p_1q_1 \geq a \\ & p_1q_2 \geq b \\ & p_2q_1 \geq c \\ & p_2q_2 \geq d \end{array}.

「ギリギリを考えよ」(“考虑极限情况”)。对于任意一个满足所给条件的方案,如果水平相邻的两个格子都没有取到等号,那么我们总可以保持q不变,减小p得到更优的解。



同理,如果垂直相邻的两个格子都没有取到等号,那么我们总可以保持p不变,减小q得到更优的解。


于是,最优解必然在下面两种情况取到:

  1. 有三个格子取到等号。


    如上图中Sample#1的情况。此时有q1=c/p2, q2=d/p2, p1=b/q2=b/d*p2, s=(1+b/d)*(c+d)。显然p2具体的值并不重要,不妨取1,此时只要有cd/b≥a,就可以取到解bc/d+b+c+d。
  2. 对角线上的两个格子取到等号。


    如上图中Sample#2的情况。此时有q1=a/p1, q2=d/p2。由条件p1/p2*d≥b, p2/p1*a≥c可以推出k=p1/p2的取值范围为[b/d, a/c]。而目标函数s=(k+1)(a/k+d)是凸的,且在k’=sqrt(a/d)时取得最小值,于是我们只要检查区间的两个端点和k’就好了。

ZOJ2608 Maps

downloadsource code (ZOJ2608.cpp) [geometry]

给定不同比例尺的三张相同区域的地图,小地图在大地图的内部,现在要求给出一种中地图的摆放方案,使得中地图在大地图内,小地图在中地图内,且存在小地图内一个点,三张地图在该点地理坐标是相同的。

这三张地图可以看作经过不同平移,旋转,缩放后得到的结果。缩放的系数已经由输入给出。而从已知的小地图和大地图的关系,通过求解一个简单的二元一次方程组,就能够求得坐标变换后不动点的位置。于是平移关系也可以唯一地确定。剩下的就是要找一个合适的旋转,使得中地图在大地图内,小地图在中地图内。

首先,对于这题规模如此小的情况,以AC为目标的话,直接上“枚举角度法“即可。

不过我们还能够做得更好。还是「ギリギリを考えよ」(“考虑极限情况”)。假设找到了一个合法的中地图,它和小地图和大地图都没有公共点,那么我们就可以继续沿着任意方向旋转,直到它和小地图或大地图有公共点(或者极角等于0)。于是我们只要求出这些关键的角度并检查它们就足够了,而求关键角度的问题又可以转为求圆和线段的交点的问题。


ZOJ2609 Crazy Painter

downloadsource code (ZOJ2609.cpp) [bipartite, FlowNetwork]

要给m×n的格子上色,给连续一段水平格子上色的花费为h,一段竖直格子上色的花费为v,一个单独格子上色的花费为s。不能给同一个格子先后上两种不同颜色,要求输出一个花费最小的上色策略。

如果h=v=1,那么这是一个非常经典的二分图最小点集覆盖问题。把连续相同颜色的水平带或垂直带作为顶点,而由他们相交唯一确定的格子作为连接两点的边。有了h和v后,问题就变成了带权问题。不过也可以转为如下最小割模型:对水平带i和垂直带j确定的格子(i,j),加三条边(S, i, h), (i, j, ∞), (j, T, v)。割集中的边就对应了所选的水平带和垂直带。最后有了给单个格子上色的s后,只要把原来的边(i, j, ∞)改成(i, j, s)就好了,最小割就对应最优方案。

ZOJ2610 Puzzle

downloadsource code (ZOJ2610.cpp) [misc]

n^2个小正三角形组成了一个边长为n的大正三角形的两个部分。现在问是否能够通过平移将两部分分离。

如果能分离,那么就一定可以沿着某条边的方向分离。于是只要枚举三个方向,分别判断是否每行都满足/0*1*|1*0*/的形式就好了。

ZOJ2611 Quest

downloadsource code (ZOJ2611.cpp) [implementation, topsort]

为一个老套的拯救公主游戏写攻略。

题目给了一大堆限制条件,一言以蔽之就是道具什么的能用就用准没错。问题本身可以通过依赖关系建图转为类似拓扑排序的问题。不过在复杂的输入下和坑爹的输出方案要求下,这其实是一道彻头彻尾的蘑菇题。

ZOJ2612 Stable Sets

downloadsource code (ZOJ2612.cpp) [DisjointSet, Ring]

考虑Zr上的整数和多项式,问有多少{0, 1, …, r-1}的子集A,对多项式函数p和q,其值域也为A。

首先我们分析只有一个多项式p的情形。假设x是A中的一个元素,那么显然p(x)也是A中的一个元素,如果对所有的0, 1, …, r-1我们都连一条i到p(x)的边,就得到了一个有向图,图中每个点的出度都恰好为1。为了保持封闭性,我们知道,如果x属于A,那么p(x)也属于A。为了保证值域等于定义域,而不是它的真子集,对于A中的任何元素x,其入度必须大于0。于是我们知道,每个稳定的A和若干个不相交的简单圈的并是一一对应的。求出这样圈的个数k,那么最终答案就是2^k。

多项式增加到两个甚至更多之后,问题并没有本质区别,同理可解。

6 Responses to “[填坑]Andrew Stankevich’s Contest #7解题报告”
  1. yefeng1627 says:

    您好~ 问下 ZOJ2604 Little Brackets 为什么可以这样转移,不太明白。

  2. wuzhengkai says:

    那啥,这是ASC06吧

  3.  
Leave a Reply