Monthly Archives: September 2010

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

首先声明:因为大部分题目是请神牛来出的,有几个题目我只写了暴力的验证程序而没有实现可以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)