基础算法(枚举、贪心、分治策略)

基本算法策略，曹，长沙市第一中学，第一部分，枚举策略，枚举策略的基本思想，枚举法，又称穷举法，是指逐一枚举集合中每一个可能解较差的元素，并判断该元素是否满足题目给出的测试条件。如果条件满足，该元素就是问题的解决方案；否则，该元素不是问题的解决方案。枚举策略的基本思想，枚举方法也是一种搜索算法，即扫描或遍历问题的所有可能解决方案的状态集。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。枚举法常用于解决“是否有”或“有多少可能性”等类型的问题。例如，枚举法可以用来解决不定方程的问题。虽然枚举本质上是一种搜索策略，但它不同于回溯。因为用枚举法求解的问题必须满足两个条件：(1)每个状态的元素数n可以预先确定；状态元素a1、a2、和是连续的值范围。设置ai1状态元素ai的最小值；aik-状态元素ai (1in)的最大值，即a11a1a1k，a21a2a2k，ai1aiaik。an1 an ankfora1 a11至a1kdo foa2 a21toa2kdo.forai ai1 toaikdo.对于an1到kdoif状态(a1，人工智能，an)满足测试条件则输出问题，枚举策略的基本思想，枚举法的特点是算法相对简单，在使用枚举法设计算法时，注重优化，减少计算量。组织、完善和系统化与问题相关的知识，找出规律，减少列举数量。枚举方法的优化和枚举算法的时间复杂度：状态总数*单个状态的时间消耗。主要优化方法有：(1)减少状态总数；(2)降低单一状态的检查成本。优化过程从以下几个方面考虑：(1)枚举对象的选择；(2)计数方法的确定；(3)采用局部枚举或引入其他算法来应用枚举算法。例1:二进制数的分类如果一个正整数被转换成二进制数，0大于1的数称为A类数，否则称为B类数。例如：(13)10=(1101)2，13是一个B类数；(10)10=(1010)210为乙级数；(24)10=(11000)224是甲类号码；程序要求：找出1 1000(包括1和1000)中所有a型和b型的数量。这个主题是一个统计主题。解决统计问题的一种常用方法是枚举法：逐一枚举所有情况，同时计数。在计数结束时，计数完成并获得结果。对于本课题，枚举法的正确性和可行性是显而易见的，而本课题的数据规模只有1 1000，因此枚举法的时间复杂度是完全可以接受的。枚举算法应用，例2: 01统计，例3:围巾裁剪(NOI测试)将一个边长为n(n=100)的大正三角形平均分成n*n个小三角形，一些小三角形已经损坏。找出面积最大的两个亚规则三角形(即小三角形数量最多的三角形)，并要求这两个亚规则三角形中没有损坏的小三角形。对于枚举算法的应用，三角形的分割必须沿其分割线进行。由于n =100，每个分隔线被枚举一次，最大值为100*3，因此可以考虑枚举。在列举了分界线之后，我们目前最重要的任务是如何找到上下三角形中最大的子三角形。我们也可以使用枚举来找到最大面积，可以通过使用每个点作为顶点来扩展。为了减少枚举的数量，我们可以首先考虑计算并保存它们的值。枚举算法的应用，定义变量：lupI，j表示最大可扩展区域，第I行和第j列上的小三角形作为上顶点。LdownI，j代表最大可扩展区域，第I行和第j列中的倒小三角形为下顶点。向上I，j表示位于第I行和第j列的小三角形是否损坏。向下I，j表示行I和列j中的倒三角形是否损坏。利用枚举算法，很容易得到lup，LDOW I，J的递推公式：min LUP I 1，j，LUP I 1，J 1 1下I 1，J=TRUE LUP I，J:=1下I 1，J=FALSE 0 UP I，J=FALSE边界：lupn，I:=1 min ldown i-1，J，ldown i-1，j-1 j=false0下i，j=false在lup、ldown被发现后，算法的设计并不困难。 此外，还必须注意三角形的60度旋转。对于位于彼此前面的三角形：xx:=n-y1yy:=x-(n-xx)对于位于相反方向的三角形：xx:=n-y1yy:=x-1-(n-xx)，枚举算法的应用，示例4:圆桌骑士(IOI测试)在8*8棋盘上，有一个国王和几个勇士。其中，国王一步一步地走，骑士一步一马地走。如果国王和骑士在同一时间相遇，国王可以选择让骑士把他带走。寻找一个点，这样所有的骑士和国王都会从这个点走最少的几步。这个问题可以从三个方面来考虑：分而治之、枚举和数学方法。因为不可能把这个问题分成单独的小问题，所以划分显然是不可能的。此外，由于战士和国王的位置的不确定性以及他们行走方式的不同，无法推导出数学公式。因此，要考虑枚举，需要三个关键点：1 .最后一个汇合点。2.国王和他的骑士的聚集地。3.国王和他的骑士。枚举算法应用，国王最多只会和一个骑士结合，因为骑士的最终目标也是最终的收敛点，一旦国王和一个骑士相遇，就可以立刻和它结合，剩下的只需要加入所有的骑士。没有必要把国王托付给中间的其他骑士。这样，我们可以估计时间是O(8 * 8 * 8 * 8 * 63)=O(36 * 10 4)，这是完全可以忍受的。另外，我们需要提前计算两点之间的距离。可以使用Floyd或Bfs。枚举算法的应用，算法流程：dis之间的距离x1，y1，x2，y2-(x1，y1)(x2，y2)。Fori:=1到8 do enumeration junction forj:=1到8 dobeganl:=至此所