经典算法的非典型实现课件.ppt

1、引言引言状态平衡状态状态稳定引言引言 例题一：任意图匹配修改主算法平衡思维与实现复杂度例题二：高精度计算修改程序实现细节平衡程序各部分之间的复杂度效果优秀的非完美算法例题三：NOI2007 day2 Catch非完美算法取得优秀效果的实例平衡所花时间与所取得的成果复杂问题的简单化构造例题四：数列维护模型简化平衡时空复杂度与实现复杂度例题五：树的维护特例与一般的转化平衡特例与一般的关系经典算法的非典型实现经典算法的非典型实现经典算法的非典型实现经典算法：经典简单有效解决一类问题障碍平衡规划经典算法的非典型实现经典算法的非典型实现Jackpot(PKU 2103)题目描述：等概率选择任意整数，求选

2、到的数能被给定的p1,p2,p3.pn中至少一个数整除的概率（用最简分数表示，n16）。实现不同性能不同12limkSPkk经典算法实现方法实现方法实现方法实现方法经典算法的非典型实现经典算法的非典型实现10k压位的高精度实现for i 1 to a0+1 do begin p ai*b+;ai ;end;2k压位的高精度实现for i 1 to a0+1 do begin p ai*b+p shr k;ai p and(2k-1);end;p div 10kp mod 10k实现不同性能不同常见优化：压位有效减少数组长度 输出速度运算速度 经典算法的非典型实现经典算法的非典型实现难思维难实现

3、简单实用经典算法 有效解决一类问题。经典简单经典算法的非典型实现经典算法的非典型实现警卫安排问题(ural 1099)题目描述：给定若干警卫间搭档关系，要求成对给警卫安排保卫工作，求能够安排警卫的最大值。（警卫人数不超过222）模型：任意图的最大匹配！经典算法：带花匈牙利树经典算法：交错增广树联想：二分图最大匹配经典算法的非典型实现经典算法的非典型实现反例345216783452167321678经典算法的非典型实现经典算法的非典型实现34521678另一个反例345216734521678经典算法的非典型实现经典算法的非典型实现主要问题：无法找到可调整的 交错增广树。解决方法：随机搜索序；多

4、次运行；进一步优化：设置失败上限提高单次运行最优解出现概率问题解决？经典算法的非典型实现经典算法的非典型实现初始算法进一步优化后的算法运行次数失败上限10-120-150-15-55-1020-10Accepted0%60%100%90%100%0%Wrong answer100%40%0%10%0%0%Time limitexceeded0%0%0%0%0%100%平均AC时间-0.0390.0800.0760.147-数据来源：Ural1099时限：0.5秒经典算法的非典型实现经典算法的非典型实现任意图匹配难以实现的经典二分图匹配直接套用失败设置失败上限时间复杂度提高随机搜索序准确率不高总

5、结总结木桶理论最短的木板决定最大的容量取长补短容量最大构建平衡弱点 vs.优势总结总结实践才是感悟这一类问题最有效的途径。纸上得来终觉浅，绝知此事要躬行。经典经典简单简单平衡平衡万能万能效果优秀的非完美算法效果优秀的非完美算法NOI2007 Catch题目描述：给定树状公路土图，要求制定一个抓捕大盗Frank的方案。你的操作有：1、在某个城市空降一位警探。2、把留在某个城市里的一位警探直接召回指挥部。3、让待在某个城市的一位警探沿着公路移动到另一个城市。效果优秀的非完美算法效果优秀的非完美算法类似树状DP的贪心存在反例。实际的解给部分的解提供了一个弹性空间。1000组随机数据：约85%：5个警

6、探，约15%：6个警探 随机数据：至少60%的分数复杂问题的简单化构造复杂问题的简单化构造树的维护(PKU 3237)题目描述：给定一棵有N个节点的树，点编号为1N，边按给定顺序编号为1N-1，每一条边有一个边权。需要对这棵树维护三个操作：1、将某一条边的权值修改为V。2、将点A到B的路径上的边权值取负号。3、询问点A到B的路径上的权值最大值。数据组数不超过20，点个数不超过10000。复杂问题的简单化构造复杂问题的简单化构造主要方法：拆链+线段树维护拆链准则：自下而上，链长度尽量长。小优化：边权下放至点。最多拆链最坏时间复杂度)(nOnnqnnOloglog复杂问题的简单化构造复杂问题的简单

7、化构造 证明证明 集合S，它的元素是x到root之间所有的边。设S中的边属于k条拆分链，这些拆分链与路径公共部分的最上层节点为P1，Pk，其中Pk=root。P2必然连接着另外一条向下走的拆分链，这条拆分链除去属于S的部分至少还有1个点；P3必然连接着另外一条向下走的拆分链，这条拆分链除去属于S的部分至少还有2个点；Pk连接的向下走的拆分链除去属于S的部分至少还有k-1个点。最少点数：最多点数：n(1)123.12k kkknOnk2118经典算法的非典型实现经典算法的非典型实现随机搜索序表面：根据克制数据的顺序依赖性予以回避。实质：设置随机权值，改变状态属性，回避特殊情况的生成。对于本题：回避克制数据的生成。适用范围：特殊情况依赖一定权值属性的情况。其他实例：Treap，随机快排经典算法的非典型实现经典算法的非典型实现设置失败上限随机算法还是有可能无法得到我们理想的状态或结果。提高准确率的一个优化。通过对于局部问题的精益求精来强化全局最优解出现概率。实例：大素数的测试。