Tag Archives: 解题报告

天津赛区网络赛非正式题解

首先声明:因为大部分题目是请神牛来出的,有几个题目我只写了暴力的验证程序而没有实现可以AC的程序。我这里写的解法有的只是看标程猜出来的,难免有不准确之处。如果有不对的地方,也是因为我对标程的理解有误。题目本身的正确性是可以保证的,这个请放心。

A. 首先离散化,然后用一条扫描线从左向右扫描事件,要求一个数据结构可以动态增加和删除线段,并且可以查询恰好被覆盖了K次的区间长度。标程的做法是分块处理,把整个Y轴分成长度约为SQRT(N)的小块,这样一条线段的中间部分会覆盖若干整个小块,两端的部分逐元素处理。对每个小块,用一个hash表H维护被覆盖了i次的长度H[i],以及该小块作为整体被覆盖的次数q。查询时对每个小块查询H[K-q]即可。期望的时间复杂是O(N*sqrt(N))

B. 二分答案,用2-SAT验证。把每轮游戏看作一个布尔变量,有两种取值。假设所有圆的最小半径为r,如果不同轮的某两个圆心的距离小于2r,说明这两个不能同时选择。由此得到一系列限制条件,恰好组成一个每个子式都包含两个变量的合取范式,再判断这个2-SAT问题是否有解即可。

C. 很赞的题目。我们考虑用一个矩形框住所有点,如果要求矩形边平行于坐标轴,则容易发现结果就是简单的把x,y坐标求最值,得到矩形(minx, miny) – (maxx, maxy)。如果我们要求矩形的倾角为a,则可以把所有点都旋转a角度得到新的坐标,然后用同样的方法来做。一个重要的观察是,f(a) = (maxx – minx) – (maxy – miny)是随着a的变化而单调变化的。当a从0度增加到90度,f(a)的符号必然变化(当然,也有一直是0的特殊情况……),把f(a)=0的那个时刻用二分法计算出来就可以了。

当然,此题也有其他方法来做,不过这种方法我觉得是最简捷优美的。

D. 有点麻烦的表达式处理题,基本上大家都要WA几次才能过。注意负号是可以作为单目运算符的,而正号不行,比赛的时候很多人问这个地方。还有就是范围越界的情况可能要尤其注意一下。

E. 如果不考虑那个VIP,N个房间可以被最多K把钥匙打开的情况,实际上就是1..N的置换组成最多K个环的情况,这个就是第一类strling数之和S1[n][1]+S1[n][2]+…+S1[n][k]。在这些情况里面,如果钥匙1恰好锁在房间1里也是不行的,所以还要减去N-1个房间被最多K-1把钥匙打开的情况数。

F. 水题,O(n^2)直接写就可以。

G. 我还没看懂标程是怎么做的,貌似是很神奇的解法。此题题解待补充。

H. 数学题,求曲线积分以后可以得到耗能关于时间t的函数e(t) = X * sqrt(w^2*r^2+v^2) * (t*v*sqrt(r^2+t^2*v^2) + r^2*log(2*v*(t*v+sqrt(r^2+t^2*v^2)))) / (2*v),此函数关于t单调增,二分求解e(t)=E即可。注意特殊处理r=0的情况。

I. 如果四个点不能组成凸四边形,则必然是其中三个点组成一个三角形,另一个点在该三角形内部。于是我们可以O(n)枚举一个点作为内部中心,试图从其他的点里选出三个来,组成三角形把它包围住,看看有多少种可能的选择。继续观察发现,如果三个点不能圈住中心点,则必然是存在一条通过中心点的直线,使得这三点都在直线的同侧。于是我们可以把所有点(除了中心点)按极角排序,然后线性转圈扫描一下就可以统计出来了。总的复杂度是O(n^2*logn)

J. 最后的矩形一定是在四个方向都遇到了-1或者边界才停止扩张。预处理出每个点(i,j)向左能扩张到的点L[i][j],向右能扩张到的点R[i][j]。对每个查询,外层以y递增,内层以x递增的顺序枚举(x,y),假设此点是矩形的底部,并且矩形是向上扩张直到某个(k,y)为-1或边界(这里k<x)。则此时矩形的上边界为k+1,下边界为x,左边界为max{L[k+1][y], L[k+2][y], … L[x][y]},右边界为min{R[k+1][y], R[k+2][y], … R[x][y]}。因为x是从上到下扫描过来的,左右边界可以顺便更新。Special Area的选择就是在这个区域内选择一个最大值,这个可以用二维RMQ在O(1)时间内完成。总的复杂度就是O(N*M*Q)

K. 每当一个点x被mark的时候,对所有点对(i,j),更新cost[i][j] = min(cost[i][j], cost[i][x] + cost[x][j]),复杂度为O(N^2)。这种操作最多有N次,故总复杂度是O(N^3)

XTU市赛解题报告

http://acm.xtu.edu.cn/OnlineJudge/index.php/contest/problems/contest_id/71

A. Allocation of Memory

简单的用一个大小为M的数组标记一下每个位置属于哪个进程即可,用0表示未被占用。新申请一块内存时从左到右寻找到连续的一段大小为K的区域,找不到就碎片清理,然后找第二次,还是找不到就返回-1。进程退出时扫描一遍数组,把本属于它的位置都标记为0。每次操作的复杂度是O(M),总复杂度是O(N*M)。

B. Beautiful Tree

树型DP容易想到,问题的难点在于“平均值”那个地方。此类问题常见的解法就是二分答案验证(和“最优比率生成树”、“最大密度子图”之类是一样的思路)。假设答案是t,把每个点i的权值变成v[i]-t*w[i],在新的权值下找不少于K个点的权值和最大的子树。如果这个最大权值和大于0,说明我们的t定得小了,反之说明t定大了,然后在相应的一半范围里继续二分即可。

现在的问题就是如何找出一个权值和最大的子树,这一步可以用树型dp来解决。用dp[i][j]表示在以i点为根的子树里选出j个点(且选择了i点)的最优解。状态转移是一个类似背包的过程,每次把一棵子树合并上来。DP的复杂度是O(n^3),总的复杂度是O(logC*n^3)。

C. Civil War

比较简单的数据结构题。用大顶堆维护当前各势力的状态,每次弹出堆顶的两个元素,如果没有同归于尽,再把获胜的一方重新压回堆里。注意处理好当战斗力相同时的字典序比较即可。总复杂度O(nlogn)

D. Dating

中等难度的dp问题。从后往前计算即可,用dp[i]表示自第i天以后能得到的最大期望幸福值。每次你有两种选择,搞破坏或不搞破坏。若搞破坏,则幸福值就是下一天的dp[i+1]。若不搞破坏,那么小R有p*q的概率成功,得到v[i],有p*(1-q)的概率单恋难过K天,故得到dp[i+K+1],有(1-p)的概率不喜欢女孩,得到下一天的dp[i+1]。总结得转移方程

dp[i] = max(dp[i+1], p*q*v[i] + p*(1-q)*dp[i+K+1] + (1-p) * dp[i+1])

复杂度O(N)

E. Enumerating the Squres

简单计数。结果就是M*N+(M-1)*(N-1)+…+(M-min(M,N)+1)*(N-min(M,N)+1)

F. Fat Man

这个题目乍看上去是非常复杂的计算几何问题,实际上有一个巧妙的转化:我们把胖子看成一个点,把树看成半径为R的圆,另外两侧墙壁也要向里推进距离R,这样得到的问题是等价的,因为这时可以看作是只考虑胖子圆心的轨迹。

然后我们建立一个图,把每棵树看作一个图中的点,如果两棵树所对应的圆相交,就在两点之间连边。把两侧墙壁也分别看作两个点S,T,如果墙壁和树所对应的圆相交,也连边。这样,胖子能不砍倒任何树通过峡谷,当且仅当S和T在图里不连通。

现在点上带了权值,问题变成:删掉权值和最小的点使得S,T不连通,这就得到了一个显然的网络最小割问题。把每个点拆成两个点,中间加上容量为该点权值的边,原来的边容量为正无穷,求S, T的最大流也就是最小割即可。

G. Generating Random Numbers

简单题。直接按照题意生成序列,生成过程中用一个大小为M的数组标记一下哪个数已经出现过即可。复杂度O(M) 。出的数据比较多是为了卡住O(M^2)的纯暴力。

H. House

我觉得这是最难的一题。首先有经验的ACMer可以发现这个可以用所谓“插头DP”来解,但现在这个数据范围会爆内存。实际上针对此题的特殊要求,可以将其转化为一个费用流问题来解。下面详细说转化方法:

首先考虑一个简化版的问题:判断能否不用任何“开路”就走遍所有格子。把格子黑白交替染色,黑点做X集白点做Y集,得到一个二分图,若两点相邻则连边。因为要求最终的路径中,每个点被进出各一次,也就是每个点“匹配”上两条边。于是我们可以添加源S和汇T,源到X集中每个点的边容量为2,Y集每个点到汇的边容量为2,中间的点容量为1。求最大流,若最大流能使所有S发出的边都充满,则原问题有解。

下面引入“开路”,此时的难点在于,每个点不一定连到另一条点上,而是可以连到“外界”,并且有多余的花费。在上面得到的图中再添加两个虚拟点u’,v’,表示“外界”。下面假设X集不小于Y集(否则可以交换X,Y集,问题不变)。X集中所有在边界上的点都有一条通向u’的边,容量为1,费用为1,表示此点可能通向外界,v’到所有在边界上的Y集点都有边,容量为1,费用为1,表示此点可能通向外界。u’到v’之间有边,容量为无穷,费用为0。最后,u’到T直接有边,容量为(|X|-|Y|)*2,费用为0,这是为了处理X集里多出来的点,这些点允许直接流向汇。求最小费用最大流,若最大流能使所有S发出的边都充满,则原问题有解,费用除以2即为最小“开路”数。

题目中的第一个例子建成图如下所示,其中点中的(x,y)表示第x行第y列的格子:

clip_image002

I. I, Robot

很容易看出是BFS,稍微加了一点难度是涉及到机器人的方向,实际上只需要把状态加一维即可,每个状态包括机器人的横坐标、纵坐标、当前方向。总的复杂度是O(N*M*4)。注意有不能到达的情况。

J. Just a Triangle

方法很多,数据量也不大,基本上怎么写都可以过。本来想卡一下O(n^3)的暴力,结果发现要想那样的话木棍长度就只能出到高精度了(汗)。我认为比较好的方法是先排序,如果能组成三角形,那么一定存在连续的三个值能组成三角形,所以只需判断O(n)次相邻的三个值即可。

后记废话:

题目总的来说是很水的,如果以Regional的难度来看除了H题都可以看作是中等以下。其实我是很想让大家挖掘一下各题的背景资料,包括每道题一开始的一句话都不是随便乱写的(虽然因为水平有限,大部分套得比较生硬,嘿嘿)。不过明显是没有很多人在比赛中顾得上关心这个,所以只好自己选几个说一下 :D

A题Bill Gates那句话是网上流传的众多“IT界最愚蠢的预言”之一,感兴趣的同学可以去搜一下其他,现在看上去都很有喜感,我印象比较深的另外一个是更早的忘了谁说的了:“未来的计算机可能只有一吨重”。B题是我很喜欢的一句话,Dijkstra这个人不止是很牛的计算机科学家,还很喜欢说一些格言式的话出来。C题背景是来自著名的政治讽刺小说《1984》,样例里的几个名字也是出自此(多嘴一句,我觉得每一个身在天朝的人都应该看看这小说)。D题那句诗是已经被用滥了,不过背景描述我觉得很有意思,哈哈。F题用来怀念已经为这个时代所不容的鲁迅老人家。G题冯诺依曼那句话在TAOCP里也有提到,随机数的生成确实是一个很复杂的问题。H题用来感叹一下当前的房事(市)吧,杜甫老人家真是深谋远虑啊……(随便说一句,这题其实不是我原创,貌似在NOI冬令营上有讨论,但是没看到有比较完整的题解,而且我也找不到题目原始出处,汗)I题题目来自著名科幻小说家阿西莫夫的短篇小说集《我,机器人》,题记是他提出的著名的“机器人三定律”之一。J的题记是纯粹硬凑的,来自泰戈尔的《飞鸟集》。我本来想写一句跟三角形有关的话,结果无论如何想不出。