讲稿集训队作业solution

1、NEERC2006NEERC2006完成情况在PKUOnlineJudge上的测试情况A:PKU1827770hupo0013148Accepted104K306MSPascal5198B2006-12-12B:PKU1827267hupo0013149AcceptedNEERC2006NEERC2006完成情况在PKUOnlineJudge上的测试情况A:PKU1827770hupo0013148Accepted104K306MSPascal5198B2006-12-12B:PKU1827267hupo0013149Accepted5592K479MSPascal2597B2006-12-1

2、2C:PKU1828685hupo0013150Accepted24K1933MSPascal1622B2006-12-1301:38:37 D: -E:PKU1827277hupo0013152Accepted976K999MSPascal5192B2006-12-1218:45:21 F: -G:PKU1827284hupo0013154Accepted4K45MSPascal663B2006-12-12H:PKU1827300hupo0013155Accepted216K6227MSPascal5357B2006-12-12I:PKU1827296hupo0013156Accepted9

3、12K1544MSPascal4537B2006-12-12J:PKU1827303hupo0013157Accepted4K30MSPascal2037B2006-12-12K:PKU1827315hupo0013158Accepted0K60MSPascal1242B2006-12-12第 1 页 共 15 S AASCII BBillingC-D E-FFoolsGHHardIJJavavsKNEERC2006ProblemA:ASCII在w*h网格平面内, 按顺时针给出一个含n个顶点且都在格点上的简单多边形(不自交), 统计每个格子被覆盖的面积的状况. (w, h, n = 100)枚

4、举指定的格子, 再与多边形求交比较麻烦, 复杂度也高. 实际上, 可以对多边形的面积进行梯形剖分即每条边的端点向x轴做投影, 投影点与端点组成的梯形有向面积之和, 原面积. 针输入的, 则从右向左的有向线段对应的梯形面积为负, 从左向右则为正. NEERC2006ProblemA:ASCII在w*h网格平面内, 按顺时针给出一个含n个顶点且都在格点上的简单多边形(不自交), 统计每个格子被覆盖的面积的状况. (w, h, n = 100)枚举指定的格子, 再与多边形求交比较麻烦, 复杂度也高. 实际上, 可以对多边形的面积进行梯形剖分即每条边的端点向x轴做投影, 投影点与端点组成的梯形有向面积

5、之和, 原面积. 针输入的, 则从右向左的有向线段对应的梯形面积为负, 从左向右则为正. 如左图, ABC, AEDB(Green)BDFC(All)CBAEFD接下来处理每个梯形, 枚举被梯形覆盖的每列格子, 按列分别处理. 对于每列, 格子的连续段, 如右图的Yellow部分; 的, 如右图的Red部分. 可以直接处理掉部分. 对于每一个Yellow部分中的格子, 4的平面交, 若不考虑特殊性, 2种情况(对边, 邻边一下即可. 实际上, 我不想那么麻烦, 写了个凸包算面积第 2 页 共 15 NEERC2006ProblemB:Billing11 位的数字串, 按优先级给定一系列区间,

6、每个区间有一个标志. 区间包含(多个, 则取优先级高的), 号码就具有该区间的标志NEERC2006ProblemB:Billing11 位的数字串, 按优先级给定一系列区间, 每个区间有一个标志. 区间包含(多个, 则取优先级高的), 号码就具有该区间的标志. 现在要求输出用前缀表示的带标志序列号码的前缀被匹配, 号码就一定具有该前缀的标志Trie 树的叶子. 号码前缀, 完全包含或被几个标志一样的区间完全包含, 则作为一个叶子结点, 否则继续扩展. 即可12每次检查结点是否被包含, O(n)时间. 总复杂度为O(Ans*n)Ans为叶子总数第 3 页 共 15 NEERC2006Probl

7、emC:Cellular给定一个长度为nA. 定义一种操作, A满足Ai Aj )modmin(|i-j|, n-|i-Ai为所有和i的圆距离不超过dAj之和. 问经过k次操作后的序列(n500,k10000000, m = 1000000, d = n / 2)每次操作, M A A 11NEERC2006ProblemC:Cellular给定一个长度为nA. 定义一种操作, A满足Ai Aj )modmin(|i-j|, n-|i-Ai为所有和i的圆距离不超过dAj之和. 问经过k次操作后的序列(n500,k10000000, m = 1000000, d = n / 2)每次操作, M

8、A A 111010111001100001101A1 A1 0 A A 2 2 A330 1 1 A A n n 其中n*nM为: (上面例子中的矩阵是d=1的情况min(|i-j|,n-|i-j|)Mi, 这就是Mk A, 其中矩阵的幂运算可以用倍增法在O(log k)次矩阵乘法下得出. 然而每次的矩阵乘法还是太慢, 需要改进. 观察矩阵 M 的特殊性: 第二行是第一行右移一位, 第三行是第二行右移一位, ., 等等. 即上行右移一位为下行. 设第一行为x1, x2, ., xn, 则矩阵M 可以写为:xnx2 x1 同样的, 对于列也一样, 左行下移一位为右行. 设第一列为y1y2yn,

9、 则矩阵M可以写为 y2 21yn y 1 称这样的性质为循环矩阵以上两种表示法是同构的两种表示法相乘的结果第 4 页 共 15 NEERC2006 x1y1x2y2 xn x1yn NEERC2006 x1y1x2y2 xn x1yn x2y1 xnx1y2x2y3xny1 xyxy xyxy xyxy xxyxyn 1 2 n 1 2 n 1 2 x y x y x y x xx y x y n 1 1n 1 2 2 n 1 2 结果依然是一个循环矩阵, 即一个循环矩阵乘循环矩阵还是循环矩阵. 一列就可以得到整个矩阵, 就是说每次乘法只要算出结果的第一行或第一列即可. 乘法的时间降为O(n

10、2). 第 5 页 共 15 NEERC2006ProblemD:Driving在平面上有n(n=物, NEERC2006ProblemD:Driving在平面上有n(n=物, 现需要将一个半径为r的圆从A点移动到B点. 求最短路将圆靠着矩形滑动(相切), 圆心的轨迹形成了一个导圆角矩形. 导圆角矩形是由原矩形的 4 条边向外平移一个半径的距离, 加上4 个1/4 圆作为导角. 导圆角矩形圆心无法进入. 问题转化成, 在若干导圆下, 一个点移动到另一个点的最短路由于在曲线上点是连续的, 无法使用图论算法, 所以需要根据最短路的性质进行点的离散化, 图(1) 边上的点如下图, 粗蓝色代表导圆角矩

11、形上的完整的直线段. 的任意一点 由三角形的性质, ADCD一定比ABD,CBD短. A, C, 点作为离散点第 6 页 共 15 NEERC2006DABC(2) 弧上的(2.1)如下图, 对于在另一个导圆角矩形NEERC2006DABC(2) 弧上的(2.1)如下图, 对于在另一个导圆角矩形上的弧l, 与弧AB的相切, 切线段为CD, C, D分别为两段弧上的切点C,D都应作为离散点A到l的最短路必经过C,D, CD为该路径上离开或进入导圆角矩形的ACBD(2.2)如下图, 对于不在导圆角矩DDAB相切于C. C应作为离散点. 因为从BD的路径只有过C点的路径最短, 且C为离开导圆角矩形的

12、事件点DACB由于(2.1)O(n2)个离散点, O(n2)条边; 接着(2.2)会在(2.1)的基础上产生(n3)的离散点, O(n3)条边. 实际上, 在(2.1)中, 点和边是共生的, 即在产生边的过程中, 若该边与 相交, 则需要取消离散点. 判断边与 相交需要 O(n), O(n4).最后运行Dijkstra算法即可, 复杂度为O(VE)logV)O(n3log第 7 页 共 15 NEERC2006ProblemE:NEERC2006ProblemE:卖订单SellOrder含: 供应物品个数, 价格.Buy Order 含: 需物品个数, 出价.要求写一个交易系统. 对于当前买订

13、单, 若当前价格最低的卖订单低于当前出价, 则发生交易. 对于当前卖订单, 若当前出价最高的买订单, 高于当前价格, 则发生交易. 当出价或价格相同时, 按订单的先后循序发生交易. 发生交易时, 按供需物品个数的最小值交易. 交易后, 需要修改订单的供需物品个数. 订单可以取3种命令: BUY, 卖订单SELL, CANCEL. 共n个命令每个命令后, (n=格的物品总数和当前处于最高出价的物品总数每次要取最小或最大, 所以订单队列是一个优先队列. 用最大堆模拟买订单, 用最小堆模拟卖订单. 接模拟. O(nlog第 8 页 共 15 NEERC2006ProblemNEERC2006Prob

14、lemF:Fools第 9 页 共 15 NEERC2006ProblemG:10000的圆上, 等距分布着NEERC2006ProblemG:10000的圆上, 等距分布着n个点. 现在再加入m个点. 要使得nm个点在圆在等距分布. 这就可能需要移动原来的n 个点到新位置上, 要求移动(沿着圆周移动)的总距离和最小. (n, m = 0, z(量Xv,Yez(中, 必会得到一个更大的z值, 所以z 单调递减. 所以有z()0 z()0 这就意味着可以进行二分搜* . 注意初始范围: *0,|E|. 关于01 分数规划参见1或优比率生成树的解法zYe Xv 的最大值. 它需要满足限制: 边(u

15、, v)的选取, u, v 选取. 这样的依赖关系与函数的形式使 想到了最小割来解决这类问题, 参见2. 建立二分图XXv代表点vY部的点Ye代表边e. 若边e 2 个点u, v, 则分别从Xu, Xv Ye 连一条容量为正无限的边. 再S, T. S Xv 连容量为的边, Ye T 1 的边. |E|Mincut割Mincut. STEdmonds Karp 算法. O(|V|+|E|), O(|E|). 第 11 页 共 15 NEERC2006O(|E|). O(|E|2)次. 算法总复杂度为O(|E|3 log R). 而实际情况会比这个估计好很多NEERC2006O(|E|). O(

16、|E|2)次. 算法总复杂度为O(|E|3 log R). 而实际情况会比这个估计好很多. 稀疏二分图的增O(|E|2). 这题使用Relabel to front Preflow Push O(|E|3), 反而会超时.另一解ST直接保留原图即若原图存在边(u,vXuXv连一条容量为正无限的边, XvXu也连一条容量为正无限的边STSXvm的边, XvT m-Dv+2的边Dv表示点v的度O(|V|), O(|E|). PreflowPushO(|V|3), 效果 ProblemsysisofDinkelbachsAlgorithmfor0-1Fractional2roductiontoAlg

17、orithm,Problems26-3:huttle12 页 共 15 NEERC2006Problem给出无向图G(VE). 每次操作任意加一条非自环的边(u,v), 每条边的选择是等概率的. G连通的期望操作次数. (|V| = 30, |E| = 1000)图的状态的表示NEERC2006Problem给出无向图G(VE). 每次操作任意加一条非自环的边(u,v), 每条边的选择是等概率的. G连通的期望操作次数. (|V| = 30, |E| = 1000)图的状态的表示: 由于每次加边是等概率的, 且只需要考虑图的连通性, 每次加边要么不改变连通性,要么把两个连通块合并. 只要把图的

18、连通状况表示出来. 于是, 状态就是每个连通块的大小的集合. (|C1 |,|C2 |,|Ck |. Ci 为每个连通块, k 个连通块. 这样的状态有多少个呢? 实际上就是 应n的整数拆分的个数f(n,k)表示把n拆分为k份的个数, 有f (n,k) f (nk,k) f (n,k 由上式得到f(30,30)5604. 状态数不多记当前状态为 S |C1 |,|C2 |,|Ck |由于点的标号是没有关系的, 为避免状态重复, 规 定|C1 |C2 |Ck |.g(SS 到完全连通的期望步数. g(n) 0. 有如下方程 立j |g(S)g(S C(n, C(n, 1i 其中 S |C1 |,|C2 |,| Ci1 |,| Ci | | Cj |,| Ci1 |,| Cj1 |,| Cj1 |,| Ck | , 示连通块Ci, Cj 合并后的状态. |Ci |Cj |表示使连通块Ci, Cj 合并的可能加边的个数C(n2)表示总可能加边数p C(n2|Ci |Cj |, 表示使状态S不改变的可能加边的个数. 该方程等式右边有两个部分1i j每次加边要么不改变连通性, 要么把两个连通块合并.S与S是满足拓补序的, 即g(S)不会依赖g(S). 这样就可以动态规划. 最后关于g(