吴翼世界大赛赛题选讲.pptx

世界大赛赛题选讲 清华大学 计算机科学实验班 吴翼 三大个人赛事 International Olympiad in Informatics (IOI) Google Code Jam (GCJ) Topcoder Open (TCO) Topcoder Collegiate Challenge (TCCC) 集体赛事 ACM/ICPC World Finals (WF) 简介 第一次中国举办，由哈尔滨工程大学承办 上海交通大学第三次夺得世界冠军 清华大学位列第六 ACM/ICPC World Finals 2010 给定一颗N个点的树，每个点是一个城堡 进攻城堡k会死去diek个士兵 攻下城堡k之后需要派capk个士兵留守 一个进攻方案即派遣军队从某一个城堡出发，经过 每条边至多两次，占领所有的城堡 问在最佳进攻方案中最少需要多少士兵才能够占领 所有城堡？ NS-T 则当前路径一定不合法 剪枝2：精确距离剪枝 距离计算采用BFS而非粗略的曼哈顿距离计算 I. Robot Solution 剪枝3：度数剪枝 抽象成图论模型，题目要求求出一条Hamiltonian Path 除了起点和终点每个点的度数至少为2，否则无解 剪枝4：连通性剪枝 当前图不连通必然无解 考虑如下几种产生孤立区域情况（深紫色格子） I. Robot Solution 程序No.1No.2No.3No.4No.5No.6 剪枝1 * 剪枝2 * 剪枝3 * 剪枝4 * 运行时间N/AN/A1.174s1.209s1.145s1.172s I. Robot Solution 给出平面图中N个点的坐标和海拔，以及S条山脊各自 所连接的山顶名称，保证给出的图是三角剖分好的 每个三角区域对应山谷中的一个山坡（即一个平面） 地图上无法确定高度的部分海拔高度为0，与大海相连 现在下了一场大雨，问现在在这片山地中形成了多少个 湖，输出各个湖水平面的海拔高度 一个湖必须包含体积为正的水。每一个湖内部，乘坐一 条体积不为0（可以认为是一个点，但是存在体积）的 船，必须能够周游湖面上任意一个地方。 题目没有给出数据规模。 H. Rain 设点x的高度为hx 对于一个面，设hx（山脊），定义边的高度 h(x,y)=minhx,hy 显然一个湖的高度必然与某一条边的高度相同 一个面至多与一个湖泊相关 BF Algorithm: 从高到低枚举所有可行高度 对于每一个面计算被当前湖泊覆盖了怎样的区域 Flood Fill 找出每一个湖泊的形状 H. Rain Solution 考虑相邻的面p1:和p2: 设p1上的水位高度为h1，p2为h2 则必然有 h1=h2；或者 h1,h20，连边 cap = Si Si cap = -Si 选择x必须要选择y，连边 cap = inf 答案为正收益和减去最小割 对于割集，要么是损失正收益要么是负收益 x,y必然处于同一个集合 D. Wifi Tower Solution 给出一个N*M的方格纸，在方格内可以任意填写字母a 到z，但是必须保证，任意一行从左到右字母的字典序 必须保证不降，同时任意一列也必须保证字典序不降。 现在一些格子已经填上了一些字母，现在要求将剩余没 有填写的空格子填满，同时要使得整个方格纸上满足双 调不降的要求。问总的方案数取模10007的值。 Small dataset N,M4 Large dataset N,M10 C. Doubly-sorted Grid 朴素的状态压缩动态规划或者记忆化搜索只能够通 过小数据 改进状态的表示方法 观察某种特定字母所占区域的轮廓线（黄色） 轮廓线必然为一条单调路径 若路径P1与P2不严格相 交且P1上存在某点严格 处于P2上方，则称P10的平面内（后面我们简称为 上方）花费高度不超过up，y0平面内（后面我们 简称为下方）花费高度不超过lo的连线方案是否可 行。 E. Marbles Solution flrup表示，区间l,r内，上方利用不超过up的 高度，要使得存在可行连接方案，下方最少需要的 花费的高度。 考虑连通块： fiup表示区间恰好为Li,Ri，上方使用不超过 up的空间，要是的存在可行连接方案，下方最少需 要的高度。 E. Marbles Solution 优化转移： 所有转移将形成一棵树形结构 将一个连通块看成一个整体 如下图 每个连通块只有两种选择 树形DP，转移均摊O(1)，总复杂度O(N2) E. Marbles Solution Problem1: 给定一颗N个结点的带边权的树 1号点在树上到任意其他点经过的边不超过30条 对于每个点i，分别求出距离i第K远的点的距离 Pr