《acm基础算法入门》由会员分享，可在线阅读，更多相关《acm基础算法入门（32页珍藏版）》请在金锄头文库上搜索。
1、ACM基础算法入门,.基础动态规划 .基础的“穷竭搜索” .贪心的三种区间问题 .数论那些事 .二分的另类法,引言,算法简单但思想及其重要 介绍的算法都堪称为经典中的经典,基础动态规划,多阶段决策过程最优化的数学方法 三要素： -阶段 -决策 -状态,动态规划的适用范围,最优子结构（最优化原理） 当前状态依赖于前面的状态得到，是前面状态的完美总结 无后效性（不成环）,经典模型,数塔模型 背包问题 区间最大和模型 最长非降子序列模型 最长公共子序列 数字归并（区间dp） 旅行商问题（状态压缩）,求解从顶到下经过节点的最大值是多少,解题思路,列状态 v I j 表示走到第i层的第j个节点的最大值
2、分阶段 每一个层就是一个阶段 状态转移方程（决策） V i-1 j += V I j v I j + 1 ? V I j : v I j + 1 ;,单调递增非降子序列,给定一整型数列a1,a2.,an（0n=100000），找出单调递增最长子序列，并求出其长度。 如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。,解题思路,定义状态 dp【i】以i为结束节点最长单调子序列长度 阶段 每一个点选择过程即阶段 转移方程： Dp【i】= max（dp【1（i-1）】） + 1 想想有没有更好的方法？,dp总结,模型匹配法 三要素法 先确定阶段（数塔问题）
3、 先确定状态（一般题目都是） 先确定决策（背包问题）,贪心的三种区间问题,选择不相交区间 区间选点 区间覆盖,选择不相交区间,数轴上有n个开区间（ai,bi），选择尽量多个区间， 使得这些区间两两没有公共点。,【分析】 首先明确一个问题：假设有两个区间x,y,区间x完全 包含y。那么，选x是不划算的，因为x和y最多只能选一个， 选x不如选y，这样不仅区间数目不会减少，而且给其他区 间留出了更多的位置。接下来，按照bi从小到大的顺序对 所有区间排序。,会场安排问题,先对n个区间按照bi从小到大的顺序排序，如果 bi相同，则ai按照从大到小的顺序排序。然后从前往后 扫描每个区间，找出所有的符合条件
4、的区间。 注意：排序后第一个区间一定会选，因为它的bi最小， 它不影响后面区间的选取，而且如果不选此区间，最终 求出的区间数目会变少。,区间选点问题,数轴上有n个闭区间ai, bi。取尽量少的点，使得每个 区间内都至少有一个点（不同区间内含的点可以是同一个）。,【分析】 如果区间i内已经有一个点被取到，我们称此区间已经被 满足。受上一题的启发，我们先讨论区间包含的情况。由于 小区间被满足时大区间一定也被满足。所以在区间包含的情 况下，大区间不需要考虑。 因此，我们把所有区间按b从小到大排序（b相同时a从 大到小排序），则如果出现区间包含的情况，小区间一定排 在前面。第一个区间应该选取哪一个点呢
5、？正确的贪心策略 是：取最后一个点。如下图。,解题思路,根据刚才的讨论，所有需要考虑的区间的a也是递增的， 我们把它画成上图的形式。如果第一个区间不选最后一个点， 而是去中间的，如灰色点，那么把它移动到最后一个点后， 被满足的区间增加了，而且原先被满足的区间现在一定被满 足。这样才能保证选取的点最少。,区间覆盖问题,数轴上有n个闭区间ai, bi，选择尽量少的区间覆盖 一条指定线段s, t。,【分析】 本题的突破口仍然是区间包含和排序扫描，不过要先 进行一次预处理。每个区间在s,t外的部分都应该预先被切 掉，因为它们的存在是毫无意义的。例如要覆盖线段3,5， 闭区间0,1的存在无意义。在预处理
6、后，在相互包含的情况 下，小区间显然不应该被考虑。,解题思路,把各区间按照a从小到大顺序。如果区间1的起点不是s， 则无解，即s,t无法被完全覆盖（因为其他区间的起点更大， 不可能覆盖到s点），否则选择起点在s的最长区间。选择此 区间ai,bi后，新的起点应该被设置为bi,并且忽略所有区间在 bi之前的部分，就像预处理一样。虽然贪心策略比上面的题 复杂，但是仍然只需要一次扫描。如下图5所示。s为当前有 效起点（此前部分已被覆盖），则应该选择区间2。,s,穷竭搜索是指将所有的可能性罗列出来，在其中寻找答案的方法。,概念：,这里，我们主要介绍：,深度优先搜索,宽度优先搜索,基础的“穷竭搜索”,深度
7、优先搜索,深度优先搜索（DFS，Depth-First Search）是搜索的手段之一。 它从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直至找到最终的解。 根据深度优先搜索的特点，采用递归函数实现比较简单。,例题,给定整数 a1,a2,a3,an, 判断是否可以从中选出若干个数，使他们的和恰好为k。 限制条件： 1=n20 -108=ai=108 -108=k=108 输入： 4 1,2,4,7 13 输出： Yes,输入： 4 1,2,4,7 15 输出： No,解题过程,i=3 sum=2,i=1 sum=1,i=1 sum=0,i
8、=2 sum=0,i=0 sum=0,i=3 sum=6,i=2 sum=2,+1,+4,+2,从a1开始按顺序决定每个数加或不加，在全部n个数决定后在判断他们的和是不是k即可。,宽度优先搜索,宽度优先搜索（BFS，Breadth-First Search）也是搜索的手段之一。与深度优先搜索类似，从某个状态出发探索所有可以到达的状态。 与深度优先搜索的不同在于搜索的顺序，宽度优先搜索总是先搜索距离初始状态近的状态，也就是说它是按照开始状态-只需1次转移就可到达的所有状态-只需2次转移就可到达的状态-，这样的顺序进行搜索。对于同一状态，宽度优先搜索只经过一次，因此复杂度为O（状态数*转移的方式）
9、。 根据宽度优先搜索的特点，采用队列进行实现。,例题：,水池数目 南阳理工学院校园里有一些小河和一些湖泊，现在，我们把它们通一看成水池，假设有一张我们学校的某处的地图，这个地图上仅标识了此处是否是水池，现在，你的任务来了，请用计算机算出该地图中共有几个水池。 输入m行每行输入n个数，表示此处有水还是没水 （1表示此处是水池，0表示此处是地面） 0m100 0n100 输入： 3 4 1 0 0 0 0 0 1 1 1 1 1 0 输出： 2,输入： 5 5 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 输出： 3,解题过程,本题是简单的搜索
10、问题，采用深度优先遍历可以解决，根据题目要求，假设从任意一点值为1的出发，将这点的坐标上下左右全部用0替换，1次DFS后与初始动这个1连接的1全部被替换成0，因此，直到图中不再存在1为至，总共进行的DFS的次数就是最后的结果咯！那么，根据题目要求，有4个方向，时间复杂度为O(4*n*m)。,数论那些事,数学，特别是数论与计算机科学有着密切的联系，所以也常被选作题材。虽然数学问题大多需要使用特定方法求解，但其中有几个基础算法扮演着重要的角色。,数论基础,辗转相除法 有关素数的基础算法 快速幂,1、求最大公约数 2、扩展欧几里得 3、ax+by=gcd(a,b),1、埃氏筛法 2、区间筛法,辗转相
11、除法,扩展欧几里得 双六 一个双六上面有向前向后无限延续的格子，每个格子都写有整数。其中0号格子是起点，1号格子是终点。而骰子上只有 a , b , -a , -b 四个整数，所以根据 a 和 b 的值的不同，有可能无法到达终点。 格子如下： -4 -3 -2 -1 0 1 2 3 4 掷出四个整数各多少次可以到达终点？输出任意一组解。 1= a , b =109 输入： 4,11 输出： 3001,解题过程,这个问题用数学语言表述就是：“求整数 x 和 y 使得 ax + by =1”。 可以发现如果gcd(a,b)!=1,无解。反之，则可以通过扩展辗转相除法来求解。 设 ab。 1，显然当
12、 b=0，gcd（a，b）=a。此时 x=1，y=0； 2，ab!=0 时 设 ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b); 根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b); 则:ax1+by1=bx2+(a mod b)y2; 即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2; 根据恒等定理得：x1=y2; y1=x2-(a/b)*y2; 这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2. 上面的思想是以递归定义的，因为 gcd 不断的递归求解一
13、定会有个时候 b=0，所以递归可以结束。,埃氏筛法,给定整数n，请问n以内多少个素数 n=106 输入 25 输出 9,解题思路,要枚举n以内素数，可以用埃氏筛法 列出2以后的所有序列： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 标出序列中的第一个素数，也就是2，序列变成： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2 将剩下序列中，划摽2的倍数，序列变成： 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14、 16 17 18 19 20 21 22 23 24 25 4 6 8 10 12 14 16 18 20 22 24 （划出的数） 如果现在这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。 本例中，因为25大于2的平方，我们返回第二步： 剩下的序列中第一个素数是3，将主序列中3的倍数划出，主序列变成： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 4 6 8 9 10 12 14 15 16 18 20 21 22 24 （划出的数） 我们得到的素数有：2，3
15、25仍然大于3的平方，所以我们还要返回第二步： 现在序列中第一个素数是5，同样将序列中5的倍数划出，主序列成了： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 （划出的数） 我们得到的素数有：2 3 5 。 因为25等于5的平方，跳出循环. 结论：去掉数字，2到25之间的素数是：2 3 5 7 11 13 17 19 23。,总结,算法竞赛是展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的竞赛。 在此送上楼教主一句名言： 虽然我不会这道题，但是AC还是没有问题的！,谢谢,thank you,
