浙大ACM简单讲解.ppt

Lecture III 赛题解析,杭航ZJU mailto:Hang.Hang.ZJU QQ:54621399,Part I The 10th ZJU Programming Contest,概述,A Clock 472/614 B CAPTCHA 87/399 C Runaway Robot 11/158 D Game 9/186 E Murder in Restaurant 337/1586 F Strange Country 27/177 G Islands 25/308 H Break Out 3/49 I Circle 392/1751,A Clock,给一个角度0=x=180，问一天之内，时针和分针之间夹角不超过x的时间总共有多长。,A Clock,观察图像可以发现，答案t与x成正比关系，现在已知x为0时t也为0，x为180时t为24*3600 于是t = 24*3600/180*x = 480*x,I Circle,给定一个最多9个点，19条边的无向图，问该图是否为一个环,I Circle,至少要3个点才可以构成环 每个点刚好有两条边 所有点之间联通 条件改变： 如何判断有向图的环(G Islands),E Murder in Restaurant,有最多100个房间和100个客人，每个客人有预定进入了离开房间的时间。 按照时间顺序每次给客人分配编号最小的空房间，没有房间的时候就忽略此客人的请求，问最后每个客人分配到的房间号。,E Murder in Restaurant,首先把所有的请求按时间顺序排列，请求有进入和离开两种。 每次寻找编号最小的空房间，因为数据规模很小，所以可以直接在一个数组中线性查找。 没有进入的人忽略相应的请求。,E Murder in Restaurant,加强条件： 100000个房间，100000个人 用优先队列来记录空房间的信息，每次进入的时候pop出最小号码，出去的时候把房间的号码放入优先队列。,B CAPTCHA,给定每个大写字母的一个点阵表示，然后给一个大图，问大图中包含了哪些字母，字母允许进行180度旋转。,B CAPTCHA,Floodfill法查找一个联通分量 int dx = 1, -1, 0, 0, 1, -1, 1, -1; int dy = 0, 0, 1, -1, 1, 1, -1, -1; void floodfill(int x, int y) if (isvalid(x, y) ,B CAPTCHA,归一法表示一个联通分量 获得所有坐标中的最小x,y坐标xmin,ymin 用相对(xmin,ymin)的偏移量来重新表示坐标 所有坐标排序,B CAPTCHA,归一法表示一个联通分量 举例 (1, 3), (2, 2), (2, 3), (2, 4), (0, 3) xmin=0, ymin=2 (1, 1), (2, 0), (2, 1), (2, 2), (0, 1) (0, 1), (1, 1), (2, 0), (2, 1), (2, 2) (4, 7), (4, 6), (3, 6), (2, 6), (4, 5) xmin=2, ymin=5 (2, 2), (2, 1), (1, 1), (0, 1), (2, 0) (0, 1), (1, 1), (2, 0), (2, 1), (2, 2),B CAPTCHA,计算每个字母的表示 方法一 为每个字母建一个矩阵，然后用前面的方法计算。 比较耗时间，对于26个字母要手动建26个矩阵。 方法二 从题目上复制下来大矩阵。按照从上倒下，从左向右的顺序依次对每个联通分量计算，这个顺序刚好是字典序。,B CAPTCHA,F Strange Country,有n3的路，3条路分别为1-3，1-2-3，1-2-3。则总消耗为2+3+3+1=9,F Strange Country,dpi表示选定前i张地图的最小开销 dpi = min(dpj + Len(j+1 to i) * (i - j) + Extra)，j = 0 to i-1 枚举i这张地图和之前的那些图选择同样的路，Len(j+1 to i)表示从j+1到i的地图都选同样路时，路的最短长度。 求Len，只需要再这些地图的合并图中求最短路即可(合并的时候保留每张图都有的边) 每次选择和之前的地图不通时，Extra为1,F Strange Country,dp1 = 2 dp2 = dp1 + 1 + 1 = 4 dp3 = min dp1 + 1 * 2 + 1, dp2 + 1 + 1 = 5,G Islands,给定最多100个点的有向图，问有多少种加边的方式，可以让最后整个图只由一些环构成，没有多余的边。一个环至少要两个点。,G Islands,首先判断图中是否已经存在多余的边了，每个联通分量只可以是3种情况：环，孤立点，或者一条有头有尾的弧。其他的情况都会导致无解。 环可以直接去掉，因为不可能再在上面加边了。 问题转化为，有x个孤立点，y条弧时，加边的方法总数。,G Islands,dpxy，表示x个孤立点，y条弧时候的答案。 x=0且y=0，dpxy=1 x=0时，dpxy=dpxy-1*y x=1时，dpxy=dpx-1y*y x=2时，dpxy= dpx-1y*y +dpx-2y+1*(x-1) 除了dp的方法，还可以利用组合/错排公式,C Runaway Robot,在一个n*m的地图上，一个机器人要从左上角走到右下角，地图上有地雷，不能踩到，同时机器人也不能走出地图。机器人只接受R(向右走)和D(向下走)两个指令。并且给机器人的指令要事先确定，然后机器人循环执行此指令知道完成任务或者任务失败。问最小的指令多长。,C Runaway Robot,枚举指令中R和U的个数，确定一个窗口，在所有的窗口叠加图中寻找路径。,C Runaway Robot,理论上总的复杂度为2004，但是实际上有些窗口是覆盖不到终点的，因此可以剪枝掉。,D Game,19*19的棋盘上有一些点，两个人进行博弈，第一个人任意选一个点，之后每个人选的点距离上一个人上次选的点的距离不能超过L，问先手和后手谁赢。 博弈？ 图论！,D Game,一般图最大匹配： 给一个图，求最多的点对，使得每个点对之间都有一条边。 算法：Edmonds Blossom-Contraction Algorithm,D Game,把棋盘上的点构图，点之间的距离小于L，则连边。 对图的每个联通分量求最大匹配。先手能赢，当且仅当存在某个联通分量，其最大匹配不是完美匹配（即有未匹配的点）,D Game,证明 对于最大匹配等于完全匹配的图，我们可以把n个点写成n/2个pair (V1, V2), (V3, V4), (Vn-1, Vn) 先手必败，因为先手每选一个点，后手一定可以选匹配边另一边的点。 对于最大匹配不是完全匹配的图，一定存在没有匹配上的点，则先手选这个点。后手如果选有匹配的点，则先手走匹配边；后手如果选没有匹配的点，则可以证明存在更大的匹配，产生矛盾。,H Break Out,打砖块游戏，砖块是最大200*200的矩阵，每个砖块有分值，还有类型，其中打掉类型1的砖块后要扣一条命，一开始有L条命，扣到0的时候游戏结束。,H Break Out,一开始只能从下往上打砖块，当某列砖块被清空后，可以从上下两头打。给定所有砖块的信息以及L，问最多能拿多少分。,H Break Out,首先要分成打穿某列和不打穿某些两种情况来考虑。 然后考虑失去最后一条命的时候，后面那些不伤命的东西是打不到的，而如果不是最后一条命，这些东西在耗了一条命后还是能打到的，就里有一个区别 预处理出在是否击穿的情况下，以及是否在该列消耗最后一条命的情况下，在每一列消耗x条命最多能得到多少分,H Break Out,预处理后，变成了一个背包问题，背包的容量最多为200，有最多200个物品，每个物品不同容量的时候有不同的价值，求使得总价值最高的方案。 复杂度：2002*2003，太大,H Break Out,思路：把枚举转化成dp的一部分 dpijk来表示状态，i表示当前处理到第几列，j表示之前是否击穿过，k表示之前是否有一列使用了最后一条命，这样就把复杂度降低到了2003的级别。 当然，整个写的过程还是非常复杂的，不太容易过。,Part II The 6th ZJPC Programming Contest,概述,A Second-price Auction 294/675 B Light Bulb 134/569 C Connect them 64/745 D Derivative 4/125 E Disaster Area Reconstruction 2/66 F 80ers Memory 284/427 G Reforestation 2/26 H Treasure Map 1/16 I A Stack or A Queue? 297/437 J Dream City 36/662 K K-Nice 107/469,I Stack or A Queue,给出N个元素进入堆栈或者队列的顺序，以及出堆栈或者队列的顺序，要求判断这个容器是堆栈还是队列 堆栈：出栈顺序为进栈顺序的倒序 队列：出列顺序和进列顺序一致,A Second-price Auction,N个人竞价拍卖一个物品，每个人出一个价格，最后最高价格的人以第二高价格拍得此物。问最后是哪一个人以什么价格中标。 保证最高价格唯一，遍历数组寻找最大元素确定中标者，再遍历数组寻找此大元素，确定中标价格。,F 80ers Memory,先给定小于100个长度小于等于20的字符串，然后每次给一些字符串，查询其中有几个出现在之前给的字符串中。 规模很小，暴力匹配即可 strcmp(s1, s2) = 0 使用STL：set,B Light Bulb,如图，给定参数灯高H，人高h，灯到墙壁距离D，求影子的最长长度L,B Light Bulb,方法一：数学解法，列出函数式子，求导解决 方法二：猜测L是关于某个参数的单峰函数，可以采用三分法。,B Light Bulb,二分法 求单调函数在(x1,x2)上的零点 令x=(x1+x1)/2 如果f(x)和f(x1)同号，则用x更新x1 如果f(x)和f(x2)同号，则用x更新x2 每次把区间缩小成原来的1/2，最后收敛到零点。,B Light Bulb,三分法 求单峰函数在(x1,x2)上的极值 令a=(x2-x1)/3 + x1 令b=(x2-x1)/3 *2 + x1 如果f(a)f(b)，则用b更新x2 如果f(a)f(b)，则用a更新x1 每次把区间缩小成原来的2/3，最后收敛到极值点,K K-Nice,对于一个最大15*15的矩阵，如果里面的某一个元素值等于周围4个数的和，则称这个元素是Nice的。如果一个矩阵中有K个Nice的元素，则称这个矩阵是K-Nice的。 现在给定矩阵的大下n*m，以及K，要求输出任意一个K-Nice的矩阵。 例如，输入3*3 1，输出 0 0 0 0 0 0 0 0 0,K K-Nice,构造题，有很多解法。 其中一种简单的解法： 先在前K个非边界点以及这些点的周围填0，其余各自从1开始按顺序递增放数字。 例如4*5 3 1 0 0 0 1 0 0 0 0 0 3 0 0 0 4 5 6 7 8 9,C Connect Them,给一个最多100个点的无向图，其中节点是有编号的，边也是有长度的，要求一个最小生成树，并且按顺序输出组成这棵树的边，这组边是所有最小生成树中，字典序最小的。 对于两条边 (a,b)，(c,d)，如果ac或者a=c且bd，则称(a,b)比(c,d)字典序小 计算最小生成树的方法： Prim Kruskal,C Connect Them,Kruskal算法中，把边按照长度排序，优先选取比较短的边。 在这题中，不光要优先选取比较短的边，在边长相同的时候，还需要优先选择字典序较小的边。 所以，直接采用Kruskal算法，在排序的方法中加入字典序的比较，就可以输出字典序最小的最小生成树了。,J Dream City,有n=250棵树，每棵树初始价值为ai，之后每天增值bi。 每天砍一棵树，连续砍m天，求最大可能收益。 砍树的顺序是任意的，状态不好表示,J Dream City,贪心思路：在任意一个方案中，我们肯定是先砍增值bi小的树，再砍bi大的树。 于是，我们可以把所有的树按照bi排序，则最后的砍树顺序一定是这个序列的一个子序列。 dpij: 一共砍了i棵树，其中最后砍的一棵是j的总收益最大值 dpij = maxdpi-1k + value(j,i) (kj) value(j,i)为第j课树在第i天的价值：aj+(i-1)*bj,I Stack or A Queue,给出N个元素进入堆栈或者队列的顺序，以及出堆栈或者队列的顺序，要求判断这个容器是堆栈还是队列 堆栈：出栈顺序为进栈顺序的倒序 队列：出列顺序和进列顺序一致,D Derivative,给一个N=100元，M=100次的多元函数。然后有100次查询，每次跟定每个变元的值，求对每个变元的偏导值。 数学题，还需比较大的优化避免超时。 具体方法略过，几乎是纯粹的数学公式解题，以及对数学公式多次调用时候的优化。,G Reforestation,在二维坐标中，有一个观察点，以及N=200棵树。每棵树一开始是半径为0的一个圆，然后以1单位/秒的速度增长半径。当某棵树接触到观察点或者接触到其他树的时候就停止增长。问从什么时候开始，观察者的整个360度视野都被树挡住。,G Reforestation,首先考虑，给定当前时刻每棵树的半径，能否判断该时刻是否整个视野都被遮住。 每棵树遮住的是人的0, 2pi中的某个角度 所有角度求并，如果覆盖了整个0,