ACM入门技巧讲课ppt课件.pptx

《ACM入门技巧讲课ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM入门技巧&算法2018BYnpugeh目录/Contents01算法复杂度030402贪心算法尺取法枚举算法01算法复杂度时间复杂度计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。常数阶:O(1)线性阶:O(n)平方阶:O(n^2)指数阶:O(logn)空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。同样常用大O符号表述，不包括这个函数的低阶项和首项系数。举个栗子intnum[1000

2、][1000];所需内存大小：1000*1000*4*8/1024/1024=30.5Mb比赛相关时间：比赛中1秒钟的时间一般可进行1e7次运算空间：入门阶段一般不会遇到超内存的情况02贪心算法贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心例一：区间完全覆盖问题题目描述：给定一个长度为m的区间，再给出n（1<=n<=1e5）个区间的起点和终点，求最少使用多少个区间可以将整个区间完全覆盖。例二：最大不相交区间数

3、问题题目描述：数轴上有n个区间[ai,bi]，要求选择尽量多个区间，使得这些区间两两没有公共点。情形一：情形二：例三：区间选点问题题目描述：数轴上有n（1<=n<=1e5）个闭区间[ai,bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。思路：给区间排个序，右端点从小到大，右端点相同时，左端点从大到小。例四：国王游戏题目描述：恰逢H国国庆，国王邀请n（1<=n<=1e5）位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上

4、各写一个正整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。推导：设A大臣的左右手分别为La,Ra,和B大臣左右手分别为Lb,Rb，前面所有人的左手乘积为S，假设A在B前面比B在

5、A前面更优。结论：按照每个大臣左右手的乘积从小到大排序，就是最优的排队方案。A在B前面：A大臣所获奖赏：S/RaB大臣所获奖赏：S*La/Rb即：max(S/Ra，S*La/Rb)S/Rb因此上式成立当且仅当S*La/Rb

6、是指对数组保存一对下标（起点、终点），然后根据实际情况交替推进两个端点直到得出答案的方法，因为这种方法像尺取虫的爬行方式所以得名。尺取法例一：Subsequence题目描述：给定长度为n（n<=1e7）的整数数列以及整数S，求出总和不小于S的连续子序列的长度的最小值，如果解不存在，输出0。A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]第一次51351074928第二次51351074928第三次51351074928第四次51351074928第五次51351074

7、928第六次51351074928第七次51351074928第八次51351074928过程模拟例二：唯一的雪花04枚举算法尺取法通常是指对数组保存一对下标（起点、终点），然后根据实际情况交替推进两个端点直到得出答案的方法，因为这种方法像尺取虫的爬行方式所以得名。枚举算法例一：4ValueswhoseSumis0题目描述：给定4个n（1<=n<=4000）元素集合A，B，C，D，要求分别从中选取一个元素a，b，c，d，使得a+b+c+d=0，问有多少种选法。例二：校门外的树（简单版）题目描述：某校

8、大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。L（1<=L<=100