APIO'XXXX 世界大赛赛题选讲 吴翼

清华大学计算机科学实验班吴翼三大个人赛事◦InternationalOlympiadinInformatics(IOI)◦GoogleCodeJam(GCJ)◦TopcoderOpen(TCO)◦TopcoderCollegiateChallenge(TCCC)集体赛事◦ACM/ICPCWorldFinals(WF)第一次中国举办，由哈尔滨工程大学承办上海交通大学第三次夺得世界冠军清华大学位列第六给定一颗N个点的树，每个点是一个城堡进攻城堡k会死去die[k]个士兵攻下城堡k之后需要派cap[k]个士兵留守一个进攻方案即派遣军队从某一个城堡出发，经过每条边至多两次，占领所有的城堡问在最佳进攻方案中最少需要多少士兵才能够占领所有城堡？N100留守的士兵相当于死去枚举起始点，进行树形动态规划每个点的决策为按照什么顺序遍历其孩子目标是使得占领所有城堡之后存活的士兵最少结论：按照子树的存活人数从大到小依次遍历子树给定一个N行M列（N≤20，M≤9）的地形图，某一些格子是不能占用的要从现在要从左上角向右下角挖一个河道，要求河道本身不能自相接处（否则的话河流的走势会产生歧义）右侧两个河道是不合法的求总方案数C.CCCC.C.CCCC.C...CC...C....CCC...CCCC..CC..C...C...CC判断一个N*M（N,M≤100）的巧克力进行若干次切割后（每次只能够垂直或者水平切割）是否能够分割成k(k16)块面积分别为S1,S2…Sk的小块F(n,m,S)表示n*m的巧克力能不能分解成S集合内的小块预处理所有可能的面积所对应的可能的小块的集合枚举分割线查表进行转移给定一个N行M列（N,M≤8）的格子地图有一个机器人需要从(0,0)出发经过每个格子一次且恰好一次，最后到达(1,0)，要求机器人第个（1≤i≤3）到达的格子恰好为(xi,yi)求总的方案数4NMi搜索剪枝剪枝1：距离剪枝◦时间T处于(x,y)，要在S到达(a,b)，若|x-a|+|y-b|S-T则当前路径一定不合法剪枝2：精确距离剪枝◦距离计算采用BFS而非粗略的曼哈顿距离计算剪枝3：度数剪枝◦抽象成图论模型，题目要求求出一条HamiltonianPath◦除了起点和终点每个点的度数至少为2，否则无解剪枝4：连通性剪枝◦当前图不连通必然无解◦考虑如下几种产生孤立区域情况（深紫色格子）程序No.1No.2No.3No.4No.5No.6剪枝1***剪枝2***剪枝3****剪枝4**运行时间N/AN/A1.174s1.209s1.145s1.172s给出平面图中N个点的坐标和海拔，以及S条山脊各自所连接的山顶名称，保证给出的图是三角剖分好的每个三角区域对应山谷中的一个山坡（即一个平面）地图上无法确定高度的部分海拔高度为0，与大海相连现在下了一场大雨，问现在在这片山地中形成了多少个湖，输出各个湖水平面的海拔高度一个湖必须包含体积为正的水。每一个湖内部，乘坐一条体积不为0（可以认为是一个点，但是存在体积）的船，必须能够周游湖面上任意一个地方。题目没有给出数据规模。设点x的高度为hx对于一个面x,y,z，设hxhyhz对于一条边x,y（山脊），定义边的高度h(x,y)=min{hx,hy}显然一个湖的高度必然与某一条边的高度相同一个面至多与一个湖泊相关BFAlgorithm:◦从高到低枚举所有可行高度◦对于每一个面计算被当前湖泊覆盖了怎样的区域◦FloodFill找出每一个湖泊的形状考虑相邻的面p1:x,y,z和p2:x,y,w设p1上的水位高度为h1，p2为h2则必然有◦h1=h2；或者◦h1,h2=h(x,y)抽象得到不等关系◦h2=max{h(x,y),h1}考虑平面图的对偶图每个区域抽象成点每条边(u,v)有权值C(u,v)（对应边的高度）每个点u有权值D(u)（对应面上的水位高度）满足不等关系最外侧的点的权值为0最大化每个D(u)Dijkstra算法minmax,,(,)DuDvCvuvuGACRush以压倒性优势夺冠（$5,000）Qizichao位列第二（$2,000）给出平面上的N个点，第i个点Pi的坐标为(xi,yi)，求所有可能构成的三角形周长的最小值（这里三角形即使退化成线段也认为是三角形）。数据保证任意两个点不会重合。SmalldatasetN≤10000LargedatasetN≤1000000类似平面上最近点对的分治算法假设当前分治后得到的最优解是P考虑分割线两侧的带状区域对于P/2*P的box每个box内至多存在常数个点复杂度O(NlogN)常数？可以证明box内至多8个点给出平面上N个通讯站各自的坐标，第i个通讯站的数据传送范围Ri，它会向在范围内的其他通讯站传送数据。目前所有通讯站均使用旧的通信协议A。现在有一个新的通信协议B，如果我们第i个站从协议A升级至协议B，则我们会得到一个转换的收益Si（Si可正，可负）。同时，升级有一个重要的限制：如果一个通讯站升级到B，那么它可以传送到数据的站也必须升级到B——因为使用A协议的通讯站无法解析B协议，而B协议却可以解析A协议下传送的信息。问如何选择通讯站的集合使得收益最大化。数据规模满足：SmalldatasetN≤15LargedatasetN≤500最小割minimumweightedclosureSi0，连边Source,icap=SiSi0，连边i,Sinkcap=-Si选择x必须要选择y，连边x,ycap=inf答案为正收益和减去最小割对于割集，要么是损失正收益要么是负收益x,y必然处于同一个集合给出一个N*M的方格纸，在方格内可以任意填写字母a到z，但是必须保证，任意一行从左到右字母的字典序必须保证不降，同时任意一列也必须保证字典序不降。现在一些格子已经填上了一些字母，现在要求将剩余没有填写的空格子填满，同时要使得整个方格纸上满足双调不降的要求。问总的方案数取模10007的值。SmalldatasetN,M≤4LargedatasetN,M≤10朴素的状态压缩动态规划或者记忆化搜索只能够通过小数据改进状态的表示方法观察某种特定字母所占区域的轮廓线（黄色）轮廓线必然为一条单调路径若路径P1与P2不严格相交且P1上存在某点严格处于P2上方，则称P1P2对于字母x的轮廓P1,x和P2,x必然满足P1,xP2,xaaabbbaaabbcaabbcebbbbcebbbeeebbceeeF(P,c)表示处理了前c个字母，边界线为P轮廓线共C(N+M,N)=184756平方级别的转移时间过大，考虑优化观察紧贴P的格子中填有字母c的格子考虑下凸点（橘红色格子）枚举这些点是否填写字母c容斥原理复杂度为O(C2N+M+M)CBA容斥原理加速修改状态F(P,k,c)表示当前边界线为P，填写了前c个字母，并且第c个字母严格分布在第1～k列转移时仅讨论第k列是否存在字母c复杂度为O(CM2N+M)有2N个珠子顺次排放在(1,0)，(2,0)，……，(2N,0)。每个珠子有一个颜色，并且一定存在N种不同的颜色，同时任意一种颜色都有两个相应颜色的珠子。现在要将相应的珠子用线连起来，连线要求除了在开始和结尾连接两个珠子的地方之外，不能与直线y=0有任何一个交点，同时要求连线上的任意部分必须水平或者垂直，并且所有的拐点都必须是整点。问最优情况下，所有连线上纵坐标最大的点的纵坐标，与纵坐标最小的点的纵坐标的差值最小是多少。无解输出-1。SmalldatasetN≤20LargedatasetN≤500容易发现连线方式一定如图动态规划表示区间[l,r]内，y0的平面内（后面我们简称为上方）花费高度不超过up，y0平面内（后面我们简称为下方）花费高度不超过lo的连线方案是否可行。[][][][]trueorfalseflruplof[l][r][up]表示，区间[l,r]内，上方利用不超过up的高度，要使得存在可行连接方案，下方最少需要的花费的高度。考虑连通块：f[i][up]表示区间恰好为[L[i],R[i]]，上方使用不超过up的空间，要是的存在可行连接方案，下方最少需要的高度。优化转移：所有转移将形成一棵树形结构将一个连通块看成一个整体如下图每个连通块只有两种选择树形DP，转移均摊O(1)，总复杂度O(N2)Problem1:◦给定一颗N个结点的带边权的树◦1号点在树上到任意其他点经过的边不超过30条◦对于每个点i，分别求出距离i第K远的点的距离Problem2:◦给定h[1…N]，可以花费1的代价使得h[i]-1◦要求花最少的代价使得h中peak的数量不超过P◦Peak:h[l…r]满足[l..r]内h值全部相同，且大于h[l-1]和h[r+1]