基础算法策略枚举.ppt

基础算法策略 枚举策略 枚举策略的基本思想 枚举法 又称穷举法 指在一个有穷的可能的解的集合中 一一枚举出集合中的每一个元素 用题目给定的检验条件来判断该元素是否符合条件 若满足条件 则该元素即为问题的一个解 否则 该元素就不是该问题的解 枚举策略 解题思路为 首先确定可能的解集合 抽象出解包含的参数 确定每个参数的数据范围 对解的每个参数的数据范围采用循环语句一一枚举 对每次枚举 根据题意给定的条件判定是否解 是否是最优解 设某个问题的解所涉及的参数 状态参数 有n个 分别表示为a1 a2 an 其中ai1 状态元素ai的最小值 aik 状态元素ai的最大值 1 i n 即a11 a1 a1k a21 a2 a2k ai1 ai aik an1 an ankfora1 a11toa1kdofoa2 a21toa2kdo forai ai1toaikdo foran an1toankdoif状态 a1 ai an 满足检验条件then输出问题的解 枚举策略 枚举法常用于解决 是否存在 或 有多少种可能 等类型的问题 例如 求解不定方程的问题就可以采用列举法 枚举法的特点是算法比较简单 在用枚举法设计算法时 重点注意优化 减少运算工作量 枚举策略的优化 枚举算法的时间复杂度 状态总数 单个状态的耗时主要优化方法 减少状态总数 降低单个状态的考察代价优化过程从以下几个方面考虑 枚举对象的选取 枚举方法的确定 采用局部枚举或引进其他算法 枚举算法的应用 若将一个正整数转化为二进制数后 0的个数多于1的个数的这类数称为A类数 否则称为B类数 例如 13 10 1101 2 13为B类数 10 10 1010 210为B类数 24 10 11000 224为A类数 程序要求 求出1 1000之中 包括1与1000 全部A B两类数的个数 例题1 二进制数的分类 分析 此题是一道统计类题目 解决统计问题的一个常用方法是枚举法 逐一枚举所有情况 同时进行统计 枚举结束时 统计也完成 得到结果 具体对本题而言 采用枚举法的正确性与可行性是显然的 而本题的数据规模又仅为1 1000 所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的 例题2 01统计 将问题的数据规模扩充到求1到m m 1030 中A类数的个数 讨论 分析 本题是统计问题 但使用1 m的循环来逐个判断显然耗时过多 对于m较大时无法在规定的时间内出解 所以我们希望通过分类统计的方法 进一步抽象问题 得到可行的算法 我们发现虽然m很大 但是这些数变成二进制后 其位数却不大 因此可以考虑从这m个数的每一位来分类进行统计 设m 112 10 1110000 2 求1 m的A类数个数 可以将112个数分为以下几类 例 数字形式为 111xxxx 2这一类数只有1个 即 1110000 2 是A类数 数字形式为 110 xxxx 2设4个填数位置填0的个数为S0 填1的个数为S1 则S0 S1 4 若为A类数 则S0 1 S1 2 可以取S0 4S1 0 S0 3S1 1 这一类数中的A类数个数 44 34 数字形式为 10 xxxxx 2设5个填数位置填0的个数为S0 填1的个数为S1 则S0 S1 5 若为A类数 则S0 1 S1 1 可以取S0 5S1 0 S0 4S1 1 S0 3S1 2 这一类数中的A类数个数 55 45 35 数字形式为 0 xxxxxx 2这一类数字的分析与前几类略有不同 因为前几类二进制数的位数都是7 而这一类数还需对位数进行讨论 1 1位数 即 1 2 不是A类数 2 2位数 即 1x 2 10 2和 11 2都不是A类数 3 3位数 即 1xx 2 A类数个数为 22 1 4 4位数 即 1xxx 2 A类数个数为 33 1 5 5位数 即 1xxxx 2 A类数个数为 44 34 5 6 6位数 即 1xxxxx 2 A类数个数为 55 45 6最后的答案是1 5 16 1 1 5 6 35 对于一般情况 设m的二进制数为a1a2 an 其中a1为最高位 设a1a2 ak中0的个数为S0 k 1的个数为S1 k 设b1b2 bn为1 m的一个数 此时可分为 第一大类 当b1 1时 可根据前缀的不同来分类统计 第二大类 当b1 0时 可根据二进制数位数的不同来分类统计 12 i n 最高位 最低位 左数第i位 设左数第i位为1 后n i位 画X的位 中有j个0 记前k位 从左数 中0的个数为S0 k 1的个数为S1 k 可预先求出 则前缀为 1 0X X 2的A类数共有 0 个A类数 其中S0 i 1 1 j S1 i 1 n i j 第一大类 j个0 要对从第2 n位上的每一个1进行上述统计 即第一类的最终结果应为 第一大类 条件 当第i位为1 且S0 i 1 1 j S1 i 1 n i j 第二大类 12 i n 最高位 最低位 左数第i位 如果左数第i位为1 即为n i 1位的二进制数 其中的A类数共有 个 其中j为后n i位中0的个数 且满足后n i 1位中0的个数多于1的个数 第二大类 故第二大类总的A类数个数为 以上两大类统计的均是小于m的A类数 如果m本身是A类数 那么ans3 1 否则ans3 0 问题的解即为ans1 ans2 ans3 根据二进制数的前缀来分类是合理的 既没有重复也没有遗漏 当m的二进制数长度为n时 最多有2n种类型 即种 比直接穷举m个数有了很大进步 总结 枚举对象的确定 在一个8 8的棋盘上 有一个国王和若干个骑士 其中 国王走一字步 骑士走马步 玩家必须选择一个骑士跟国王一起行动 其他的骑士则自己单独走到集中点 骑士和国王一起走的时候 只算一个人走的步数 求一个点 使所有的骑士和国王相聚在这个点上的所走的步数最少 例题3 圆桌骑士 IOI98 usaco3 3 此题可从3个方面考虑 分治 枚举 数学方法 由于无法将这个问题划分为各自独立的小问题来解决 分治显然是不行的 又因武士和国王位置的不固定性和其走法的差异 推导不出一个数学公式 因此考虑使用枚举 需要枚举对象有 分析 1 最后的汇聚点 2 国王与背他的骑士的汇聚点 3 背国王的骑士 国王最多只会与一个骑士结合 因为骑士的最终目标也是最终汇聚点 一旦国王与某个骑士汇合后 即马上可与其结合 剩下的只需要将所有的骑士汇合就可以了 更没有必要在中途中有将国王托付给其他的骑士 这样我们估算一下时间为O 8 8 8 8 63 O 36 10 4 完全可以承受 另外 我们需要预先将2点之间走马字步的距离计算出来 可以使用Floyd或是Bfs 分析 图中红色格子为假设的集结点 绿色格子为假设的某骑士跟王接头地点 蓝色的Q为前去背王的人 增量为黑色路线步数的和减去蓝色虚线的步数 算法流程 dis x1 y1 x2 y2 x1 y1 x2 y2 之间的距离 ForI 1to8do 枚举汇合点 Forj 1to8dobeginAll 所有骑士到这一点的和 Best min best all 国王到汇聚点的步数 Forx 1to8do 枚举武士国王的相会点 Fory 1to8dobeginForkk 1tokdo 枚举与国王结合的武士 Ifdis knight kk x knight kk y x y minthenbeginMin dis knight kk x knight kk y x y Mink k End End Now all mink武士走到汇合点的距离 mink武士走到汇聚点的距离 国王走到汇聚点的距离 从汇聚点到汇合点的距离 Best min best now End 局部枚举 某城里有n个车站 m条双向公路连接其中的某些车站 每两个车站最多用一条公路直接相连 从任何一个车站出发都可以经过一条或多条公路到达其他车站 但不同的路径需要花费的时间可能不同 在一条路上花费的时间等于路径上所有公路需要的时间之和 例题4 新年好 佳佳的家在车站1 他有五个亲戚 分别住在车站a b c d e 过年了 他需要从自己的家出发 拜访每个亲戚 顺序任意 给他们送去节日的祝福 怎样走 才需要最少的时间 e a b c d 1 分析 算法框架 1 用5次最短路 计算出6个点两两之间的距离 2 枚举5个结点的全排列 找到一个使得总路程长度最短的方案 其它实例 火柴棒等式 NOIP2008 给你n n 24 根火柴棍 你可以拼出多少个形如 A B C 的等式 等式中的A B C是用火柴棍拼出的整数 若该数非零 则最高位不能是0 用火柴棍拼数字0 9的拼法如图所示 注意 1 加号与等号各自需要两根火柴棍2 如果A B 则A B C与B A C视为不同的等式 A B C 0 3 n根火柴棍必须全部用上 分析 0 9的数字所用的火柴数 6 2 5 5 4 5 6 3 7 6对于N 24 去掉 实际上数字只有20根火柴 首先考虑解集合 因为最多为20根火柴组成数字 不可能为10个1 不可能8个1 1个4 不可能为7个1 2个7或1个0 C不会超过1000 枚举答案 设F I 表示数为I时的火柴棍数FORA 0TO1000DOIFF A N 4THENFORB 1000 ADOIFF A F B F A B N 4THEN输出 其它实例 侦探推理 NOIP2003 证词中出现的其他话 都不列入逻辑推理的内容 明明所知道的是 他的同学中有N个人始终说假话 其余的人始终说真话 现在 明明需要你帮助他从他同学的话中推断出谁是真正的凶手 请记住 凶手只有一个 要求 判断谁是罪犯 输入样例 315 共有3个嫌疑人 其中有1个人始终说假话 有5条证词 MIKECHARLESKATEMIKE Iamguilty MIKE TodayisSunday CHARLES MIKEisguilty KATE Iamguilty KATE Howareyou 输出样例 MIKE 分析 这道题的关键点是 如何能够快速正确实现出来 事实上这道题对编码能力的要求要大于对算法本身的要求 由于这道题的数据范围并不是很大 但需要进行 字符串处理 这种比较麻烦的工作 因此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单 推荐的算法分为两步 1 预处理每个人的每一句话 并把它们分类处理 2 枚举罪犯和当前星期几 找出所有可能发生的情况 分析 由题目描述可以发现语句可分为三类 1 指明i是否是罪犯的语句 2 指明今天是星期d的语句 3 没有意义的语句 不符合格式要求 我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去 这样在处理每个语句的时候就必须要考虑该语句是否符合格式要求 通过以上的处理 我们对于每一个语句用几个变量就可以表示了 对于第二步的细化 我们在枚举完罪犯和当前星期几之后 就可以比较方便的判断每一句话的真伪了 这样我们再根据每个人所说的话把人进行分类 1 没说任何一句有意义的话 2 只说真话 3 只说假话 4 既说真话也说假话 分析 需要注意的是 对于第一类人我们既可以把他当成说真话的 也可以把他当成说假话的 而如果第四类人存在的话 那么从他本身就可以推出矛盾了 最后 如果对于罪犯i存在一个d使得当前情况是可能的 我们就说i就是可能的罪犯 时间效率 O MP Day 其中Day Sunday Monday Tuesday Wednesday Thursday Friday Saturday 优化 我们可以发现在对罪犯和当前星期几进行 双重枚举 时 进行了很多重复的操作 于是我们想到 能不能不枚举是当前星期几 这样我们把这类语句与判断罪犯的语句分离 可以先由判断罪犯的语句中确定一部分人肯定说真话 一部分人肯定说假话 剩下的一部分人就要根据他所说的当前星期几的语句来判断了 首先我们假设所有人判断星期的语句不自相矛盾 这样每个人将在判断这类问题里面至多有一个答案 我们便可以统计判断当前是星期d的总人数 于是改进后的算法对于每一个可能的罪犯 先用O p 的时间处理所有的话 再用O Day 的时间枚举星期几 这样 改进后算法的复杂度就是O m p Day 现有一个棱长为n的立方体 可以分成n3个1 1 1的单位立方体 每个单位立方体都有一个整数值 n3个单位立方体的数和不会超过longint范围 现在要求在这个立方体找到一个包含完整单位立方体的长方体 使得该长方体内所有单位立方体的数和最大 输入 n 1 n 20 n个n n的数字矩阵 每个数字矩阵代表一层 每个数字代表一个单位立方体的整数值 999 单位立方体的整数值 999输出 长方体的数和 其它实例 立方体问题 简单 枚举过程 1 枚举所有可能的平面forx1 1tondoforx2 1tondofory1 1tondofory2 1tondoforz1 1tondoforz2 1tondo考察状态 x1 y1 z1 x2 y2 z2 2 考察状态 x1 y1 z1 x2 y2 z2 过程如下sum 0 forx x1tox2do 计算长方体的体积 fory y1toy2doforz z1toz2dosum sum map x y z 调整最优解 ifsum bestthenbest sum 这个算法枚举状态为O n9 从减少重复计算入手 记录先前考察的结果 在统计长方体2时 只要将长方体1的统计结果加上长方体3就可以了 而不必按上述算法那样重新进行计算 考察过程改为 forx x1tox2do 计算长方体的体积 fory y1toy2dosum sum map x y z2 ifsum bestthenbest sum 调整最优解 由于利用了计算出的结果 整个算法的时间复杂度降为O n8 3 提取恰当的信息上述考察实际上求出z轴坐标为z2的平面中矩形 x1 y1 x2 y2 的数和 我们将这个数和记为value a value A value ABCD value B value BC value BD 这就启发我们用另一种方法表示立方体的信息 设rec x y z 表示z轴坐标为z的水平面中矩形 1 1 x y 的数和 z轴坐标为z的水平面中左上角为 x1 y1 右下角为 x2 y2 的矩阵的数和为rec x2 y2 z rec x1 y1 z rec x2 y1 z rec x1 y2 z Rec数组可以在输入数据的同时计算