《国家集训队2007论文集5.陈雪《问题中的变与》由会员分享，可在线阅读，更多相关《国家集训队2007论文集5.陈雪《问题中的变与（25页珍藏版）》请在金锄头文库上搜索。
1、问题中的变与不变长沙市雅礼中学 陈雪引言对变量进行操作是信息学中的常见问题。如果能找到变量之间的关系，把变量转化 成不变量，那么算法的效率就将得到质的 提升。例一蚂蚁一条树枝上有N只蚂蚁。给出他们的位置，如何安排蚂 蚁初始的方向使得全部蚂蚁掉落的时间最早或最晚。最多1,000,000只蚂蚁。感性认识左边的蚂蚁向左端走，右边的蚂蚁向右端走。如何使全部掉落的时间最晚？猜想：让左边的蚂蚁向右端走，同时右边的蚂 蚁向左端走。理性分析直接证明猜想难度比较大。看一般的情况:纪录2只蚂蚁的有用信息:速度 和位置 。设 。在蚂蚁相遇前一刻,在蚂蚁相遇后一颗,一个集合内蚂蚁相遇 集合不变继续分析另任何两只属于集
2、合U内的蚂蚁相遇之后， 集合U不变。集合U只随着时间的变化而变化。Ansi=蚂蚁I按起始方向走到端点继续分析回到原问题 最早时间= 最迟时间=猜想得证！最终时间复杂度O( n )。即左边蚂蚁向左走，右边蚂蚁向右走Max蚂蚁I向近端出发Max蚂蚁I向远端出发即左边蚂蚁向右走，右边蚂蚁向左走小结分析题目的特殊特点:1.原路返回 2.速度相同将速度变量固定，成为常量。问题得到了简化。例二circular way安排一种方案使得总代价最小n50000最小权匹配！ 无法满足题目要求！设A类点顺时针排序的坐标为A1,A2 An设B类点顺时针排序的坐标为B1,B2 Bn优化算法最小权匹配必然满足下面的性质:
3、通过调整可以得到更优解两条匹配边不会交叉算法二1.枚举和A1匹配的点Bk。2.然后按顺序一一求出和Ai匹配的点。3.最后统计当前的代价和，更新答案。时间复杂度继续分析另Ci表示当前Ai与它匹配的Bj的距离。当前的代价sum=CiCi随着我们枚举k而变化。找出Ci中蕴含的不变？观察Ci由于Ai到Bj有顺时针，逆时针2种走法。Ci =Min|Ai-Bj|,L-|Ai-Bj|Ci只同Ai和Bj有关。不妨把Ci看成Ai和Bj的函数。设Ci=f(Ai)+g(Bj)讨论Ci0从 顺时针走到讨论Ci0从 逆时针走到讨论Ci0从 顺时针走到讨论Ci0从 逆时针走到继续分析根据Ai,Bi的有序性，得到f(Ai)
4、的每种情 况对应的Bj都是连续的一段。f(Ai)在枚举和A1匹配的点Bk的过程中 只会发生4次变化。 从Ci的N次变化 f(Ai),g(Bi)的4次变化回到原问题当前的代价sum=Ci=f(Ai)+g(Bi)A1匹配Bk，sum已经求出。当A1匹配Bk+1，更新f(Ai),g(Bi),sum。sum=sum-f(Ai)+f(Ai)-g(Bi)+g(Bi)把一个-f(Ai)+f(Ai)和-g(Bi)+g(Bi) 看成一次事件f(Ai)表示上一时刻f(Ai)f(Ai)表示当前f(Ai)举例A1匹配B4，有A1匹配B1，有看成一次事件看成一次事件分析事件总数8n根据Ai,Bi的有序性，预处理用指针即
5、可知道下一时刻k+1会发生的事件 更新sum得到f (Ai)4种情况对应的Bj范围每件事件发生时间小结算法流程如下 1将Ai,Bi排序 2预处理求出每个事件发生时间 3枚举和A1匹配的点Bk,更新sum。 4输出时间复杂度 O(排序+事件总数)=O(nlgn)小结将变化的Ci转化成“不变”的f(Ai)和g(Bi)减少了操作规模问题迎刃而解总结 例一蚂蚁 以不变应万变 例二circular way 将变量的操作规模缩小 仔细分析，大胆猜想把握问题的本质问题迎刃而解变 不变参考文献: 1 刘汝佳,黄亮.算法艺术与信息学竞赛. 清华大学出版社.2003 2 zju online judge 2376 ants. http:/ 3 sgu online judge 313 circular railway. http:/acm.sgu.ru/problem.php?contest=0&problem=313
