算法合集之《正难则反–浅谈逆向思维在解题中的应用》

《算法合集之《正难则反–浅谈逆向思维在解题中的应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、绍兴市第一中学唐文斌正难则反–浅谈逆向思维在解题中的应用绍兴市第一中学唐文斌【摘要】逆向思维是一种思考问题的方式，它有悖于通常人们的习惯，而正是这一特点，使得许多靠正常思维不能或是难于解决的问题迎刃而解。本文通过几个例子，总结了逆向思维在信息学解题中的应用。【关键字】逆向思维容斥原理参数搜索二分动态规划记忆化【正文】引言我们先看一个简单的问题：平面上有四个点，构成一个边长为1的正方形。现在进行一种操作，每次可以选择两个点A和B，把A关于B对称到C，然后把A去掉。求证：不可能经过有限次操作得到一个边长大于1的正方形操作后的结果是相当复杂的，

2、如果我们从正面着手，很难证明命题。不妨从反面来看问题：观察可以发现，每一步操作都是可逆的。即，我们如果可以把正方形变大，也可以把正方形变小。证明：不妨设四个顶点都是整点。假设我们可以通过有限次操作得到一个边长大于1的正方形，那么我们把所有操作反过来对原正方形进行操作，我们可以得到一个边长小于1的正方形。因为四个顶点都是整点，操作之后，点的坐标依然是整数。所以我们得到一个边长小于1且四个点都是整点的正方形。这显然不可能。所以假设不成立。命题得证。第10页共10页绍兴市第一中学唐文斌上面的例子说明了逆向思维在数学问题中的应用。山重水复疑无路，

3、应用逆向思维，换个角度看问题，便柳暗花明又一村了。例一、DinnerIsReadyZhejiangUniversityOnlineJudge1442(acm.zju.edu.cn)题目大意：妈妈烧了M根骨头分给n个孩子们，第i个孩子有两个参数Mini和Maxi，分别表示这个孩子至少要得到Mini根骨头，至多得到Maxi根骨头。输入：第一行包含两个数n(0

4、孩子们）初步分析：该题模型很简单，即求如下方程组的整数解的个数：我们知道，方程组简单形式的整数解个数为这是一个很经典的组合问题，可由隔板原理得出答案。设Yi=Xi+Mini，则原方程组转化为对于下界限制，我可以通过换元得到简单形式，但是因为有上界的限制，我们似乎还无法直接计算出答案。应用逆向思维：第10页共10页绍兴市第一中学唐文斌设S为全集，表示满足Xi≥Mini的整数解集。设为S中满足约束条件Xi≤Maxi的整数解的集合,为在S中的补集，即满足Xi>Maxi。无法计算，但是，可解！！！我们希望把的计算转化到可解的。于是：这是一种容斥原

5、理的形式。至此，问题已经解决。我们应用逆向思维，在原集合的模不可解的情况下，通过可解的得到答案。并给出了一个基于容斥原理的算法。时间复杂度为O(2n*(n+M))。例二、GreedyPathSaratovStateUniversityOnlineJudge236(acm.sgu.ru)题目大意：有n个城市，被m条路连接着。最近成立了一些旅行社，在这些城市之间给旅行者们提供服务。旅行者从城市i到城市j需要付给旅行社的费用是Ci,j，需要的时间为Ti,j。很多旅行者希望加入旅行社，但是旅行社只有一辆车。于是旅行社的老板决定组织一次旅行大赚一笔

6、。公司里的专家需要提供一条使得贪心函数F(G)最大的回路G。F(G)等于总花费除以总时间。但是没有人找到这样的回路，于是公司的领导请你帮忙。输入：第一行包含两个数n(3≤n≤50),m分别表示点数和边数。接下来m行每行包含一条路的描述。输入四个数,A,B,CA,B,TA,B（0≤CA,B≤100，0≤TA,B≤100）输出：如果不存在这样的路，输出0。否则输出回路中包含的城市个数，然后依次输出通过的城市的顺序。如果有很多条这样的路，输出任意一条。初步分析：题目要求是求一条回路，但不是边权和最大或者最小，所以我们不能直接使用经典算法。设G=

7、(V,E)，S为G中所有回路C=(V’,E’)组成的集合。我们的目标是找到集合S中的一条回路使得F(C)取到最大值：应用逆向思维：第10页共10页绍兴市第一中学唐文斌如果我们知道C*=(V*,E*)S是一条最优回路，那么于是我们定义函数o(t):o(t)=我们做一个猜想：如果有o(t*)=0，那么存在C*=(V*,E*)S满足我们认为C*就是一条最优回路。证明：假设存在另一条回路C1=(V1,E1)S更优，则：但是这与o(t*)=0矛盾。所以C*是一条最优回路。如果t*是最优答案，则存在：（性质一）于是我们就得到了算法：我们从一个包含t*

8、的区间(tl,th)开始。（例如tl=,th=）每一次，选取tl与th的中点t,计算O(t)。O(t)的计算方法：对于边eE,设一个新的参数We=Ce–t*Te用Floyd算法计算有向图的最大