网站建设公司特点,做淘客网站用什么程序,设计开发流程,微网站建设及微信推广方案目录枚举例题应用#xff1a;模拟技巧递归$分治递归分治算法贪心常见题型与动态规划的区别例题#xff1a;应用排序选择排序冒泡排序插入排序计数排序基数排序二分最大值最小化STL 的二分查找三分法最大化平均值#xff08;01分数规划#xff09;枚举
枚举#xff08;英语…
目录枚举例题应用模拟技巧递归$分治递归分治算法贪心常见题型与动态规划的区别例题应用排序选择排序冒泡排序插入排序计数排序基数排序二分最大值最小化STL 的二分查找三分法最大化平均值01分数规划枚举
枚举英语Enumerate是基于已有知识来猜测答案的一种问题求解策略。 枚举的思想是不断地猜测从可能的集合中一一尝试然后再判断题目的条件是否成立。
要点 给出解空间 建立简洁的数学模型。 枚举的时候要想清楚可能的情况是什么要枚举哪些要素减少枚举的空间 枚举的范围是什么是所有的内容都需要枚举吗 在用枚举法解决问题的时候一定要想清楚这两件事否则会带来不必要的时间开销。选择合适的枚举顺序 根据题目判断。
例题
一个数组中的数互不相同求其中和为 的数对的个数
解题思路 枚举两个数的代码很容易就可以写出来。
for (int i 0; i n; i)for (int j 0; j n; j)if (a[i] a[j] 0) ans;来看看枚举的范围如何优化。原问题的答案由两部分构成两个数相等的情况和不相等的情况。相等的情况只需要枚举每一个数判断一下是否合法。至于不相等的情况由于题中没要求数对是有序的答案就是有序的情况的两倍考虑如果 (a, b) 是答案那么 (b, a) 也是答案。对于这种情况只需统计人为要求有顺序之后的答案最后再乘上 就好了。 不妨要求第一个数要出现在靠前的位置。代码如下
for (int i 0; i n; i)for (int j 0; j i; j)if (a[i] a[j] 0) ans;不难发现这里已经减少了 的枚举范围减少了这段代码的时间开销。
然而这并不是最优的结果。
两个数是否都一定要枚举出来呢枚举其中一个数之后题目的条件已经确定了其他的要素另一个数如果能找到一种方法直接判断题目要求的那个数是否存在就可以省掉枚举后一个数的时间了。
// 要求 a 数组中的数的绝对值都小于 MAXN
bool met[MAXN * 2];
// 初始化 met 数组为 0
memset(met, 0, sizeof(met));
for (int i 0; i n; i) {if (met[MAXN - a[i]]) ans;// 为了避免负数下标met[a[i] MAXN] 1;
}应用
POJ Subset 3977 折半枚举二分
模拟
模拟就是用计算机来模拟题目中要求的操作。 模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大经常会出现难以查错的情况如果在考试中写错是相当浪费时间的。
技巧
写模拟题时遵循以下的建议有可能会提升做题速度
在动手写代码之前在草纸上尽可能地写好要实现的流程。在代码中尽量把每个部分模块化写成函数、结构体或类。对于一些可能重复用到的概念可以统一转化方便处理如某题给你 “YY-MM-DD 时分” 把它抽取到一个函数处理成秒会减少概念混淆。调试时分块调试。模块化的好处就是可以方便的单独调某一部分。写代码的时候一定要思路清晰不要想到什么写什么要按照落在纸上的步骤写。 实际上上述步骤在解决其它类型的题目时也是很有帮助的。
递归$分治
递归英语Recursion在数学和计算机科学中是指在函数的定义中使用函数自身的方法在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。
分治英语Divide and Conquer字面上的解释是“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。 详细介绍
递归 要理解递归就得先理解什么是递归。 递归的基本思想是某个函数直接或者间接地调用自身这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题而不需要过分关注这个子问题是如何被解决的。 递归代码最重要的两个特征结束条件和自我调用。自我调用是在解决子问题而结束条件定义了最简子问题的答案。
int func(传入数值) {if (终止条件) return 最小子问题解;return func(缩小规模);
}递归的缺点 在程序执行中递归是利用堆栈来实现的。每当进入一个函数调用栈就会增加一层栈帧每次函数返回栈就会减少一层栈帧。而栈不是无限大的当递归层数过多时就会造成 栈溢出 的后果。递归优化 主要搜索优化 和 记忆化搜索 比较初级的递归实现可能递归次数太多容易超时。这时需要对递归进行优化。
分治算法
分治算法的核心思想就是“分而治之”。 大概的流程可以分为三步分解 - 解决 - 合并。
分解原问题为结构相同的子问题。分解到某个容易求解的边界之后进行递归求解。将子问题的解合并成原问题的解。 分治法能解决的问题一般有如下特征该问题的规模缩小到一定的程度就可以容易地解决。该问题可以分解为若干个规模较小的相同问题即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解。该问题所分解出的各个子问题是相互独立的即子问题之间不包含公共的子问题。 要点
写递归的要点 明白一个函数的作用并相信它能完成这个任务千万不要跳进这个函数里面企图探究更多细节 否则就会陷入无穷的细节无法自拔人脑能压几个栈啊。 区别递归与枚举的区别 递归和枚举的区别在于枚举是横向地把问题划分然后依次求解子问题而递归是把问题逐级分解是纵向的拆分。递归与分治的区别 递归是一种编程技巧一种解决问题的思维方式分治算法很大程度上是基于递归的解决更具体问题的算法思想。
贪心
贪心算法英语greedy algorithm是用计算机来模拟一个“贪心”的人做出决策的过程。这个人十分贪婪每一步行动总是按某种指标选取最优的操作。而且他目光短浅总是只看眼前并不考虑以后可能造成的影响。 可想而知并不是所有的时候贪心法都能获得最优解所以一般使用贪心法的时候都要确保自己能证明其正确性。 适用范围 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决子问题的最优解能递推到最终问题的最优解。 证明方法 贪心算法有两种证明方法反证法和归纳法。一般情况下一道题只会用到其中的一种方法来证明。
反证法如果交换方案中任意两个元素/相邻的两个元素后答案不会变得更好那么可以推定目前的解已经是最优解了。归纳法先算得出边界情况例如n1n1n1 的最优解F1F_{1}F1 然后再证明对于每个nnn FnF_{n}Fn都可以由Fn1F_{n1}Fn1 推导出结果。
常见题型
在提高组难度以下的题目中最常见的贪心有两种。
「我们将 XXX 按照某某顺序排序然后按某种顺序例如从小到大选择。」。「我们每次都取 XXX 中最大/小的东西并更新 XXX。」有时「XXX 中最大/小的东西」可以优化比如用优先队列维护 二者的区别在于一种是离线的先处理后选择一种是在线的边处理边选择。
排序解法 用排序法常见的情况是输入一个包含几个一般一到两个权值的数组通过排序然后遍历模拟计算的方法求出最优值。后悔解法 思路是无论当前的选项是否最优都接受然后进行比较如果选择之后不是最优了则反悔舍弃掉这个选项否则正式接受。如此往复。
与动态规划的区别
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择不能回退。动态规划则会保存以前的运算结果并根据以前的结果对当前进行选择有回退功能。
例题
邻项交换法的例题 恰逢 H 国国庆国王邀请 n 位大臣来玩一个有奖游戏。首先他让每个大臣在左、右手上面分别写下一个整数国王自己也在左、右手上各写一个整数。然后让这 n 位大臣排成一排国王站在队伍的最前面。排好队后所有的大臣都会获得国王奖赏的若干金币每位大臣获得的金币数分别是排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏所以他想请你帮他重新安排一下队伍的顺序使得获得奖赏最多的大臣所获奖赏尽可能的少。注意国王的位置始终在队伍的最前面。 解题思路
struct uv {int a, b;bool operator(const uv x) const {return max(x.b, a * b) max(b, x.a * x.b);}
};应用
后悔法贪心
排序
排序算法英语Sorting algorithm是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样性质也大多不同。 性质
稳定性 稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。 拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序即如果一个排序算法是稳定的当有两个相等键值的纪录 XXX和YYY 且在原本的列表中 XXX出现在YYY 之前在排序过的列表中 XXX也将会是在 YYY 之前。
基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。选择排序、堆排序、快速排序不是稳定排序。
时间复杂度 时间复杂度用来衡量一个算法的运行时间和输入规模的关系通常用 OOO表示。 简单计算复杂度的方法一般是统计“简单操作”的执行次数有时候也可以直接数循环的层数来近似估计。 时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。OI 竞赛中要考虑的一般是最坏时间复杂度因为它代表的是算法运行水平的下界在评测中不会出现更差的结果了。 基于比较的排序算法的时间复杂度下限是 O(nlogn)O(nlog_{n})O(nlogn)的。 当然也有不是 O(nlogn)O(nlog_{n})O(nlogn)的。例如计数排序的时间复杂度是O(nm)O(nm)O(nm)其中 m代表输入数据的值域大小。 几种排序算法的比较
选择排序
选择排序英语Selection sort是排序算法的一种它的工作原理是每次找出第 iii小的元素也就是A1...nA_{1...n}A1...n中最小的元素然后将这个元素与数组第 iii个位置上的元素交换。时间复杂度为O(n2)O(n^{2})O(n2) 。
冒泡排序
冒泡排序英语Bubble sort是一种简单的排序算法。由于在算法的执行过程中较小的元素像是气泡般慢慢「浮」到数列的顶端故叫做冒泡排序。 它的工作原理是每次检查相邻两个元素如果前面的元素与后面的元素满足给定的排序条件就将相邻两个元素交换。当没有相邻的元素需要交换时排序就完成了。 经过 iii次扫描后数列的末尾 iii项必然是最大的 iii项因此冒泡排序最多需要扫描 n−1n-1n−1遍数组就能完成排序。时间复杂度为O(n2)O(n^{2})O(n2) 。
插入排序
插入排序英语Insertion sort是一种简单直观的排序算法。它的工作原理为将待排列元素划分为“已排序”和“未排序”两部分每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。 一个与插入排序相同的操作是打扑克牌时从牌桌上抓一张牌按牌面大小插到手牌后再抓下一张牌。时间复杂度为O(n2)O(n^{2})O(n2) 。
void insertion_sort(int* a, int n) {// 对 a[1],a[2],...,a[n] 进行插入排序for (int i 2; i n; i) {int key a[i];int j i - 1;while (j 0 a[j] key) {a[j 1] a[j];--j;}a[j 1] key;}
}计数排序
计数排序英语Counting sort是一种线性时间的排序算法。 计数排序的工作原理是使用一个额外的数组CCC其中第iii 个元素是待排序数组 AAA中值等于 iii的元素的个数然后根据数组 CCC来将 AAA中的元素排到正确的位置。 它的工作过程分为三个步骤
计算每个数出现了几次求出每个数出现次数的前缀和利用出现次数的前缀和,从右至左计算每个数的排名。 计数排序的时间复杂度是O(nm)O(nm)O(nm)其中 m代表输入数据的值域大小。
const int N 1e510;
const int M 1e510;
int n, w, a[N], cnt[M], b[N];void counting_sort() {memset(cnt, 0, sizeof(cnt));for (int i 1; i n; i) cnt[a[i]];// 计算每个数出现了几次for (int i 1; i M; i) cnt[i] cnt[i - 1];//求出每个数出现次数的前缀和for (int i n; i 1; --i) b[cnt[a[i]]--] a[i];//利用出现次数的前缀和,从右至左计算每个数的排名
}动图演示
基数排序
基数排序英语Radix sort是一种非比较型的排序算法最早用于解决卡片排序的问题。 它的工作原理是将待排序的元素拆分为 kkk个关键字比较两个元素时先比较第一关键字如果相同再比较第二关键字……然后先对第 kkk关键字进行稳定排序再对第k−1k-1k−1关键字进行稳定排序再对第 k−2k-2k−2关键字进行稳定排序……最后对第一关键字进行稳定排序这样就完成了对整个待排序序列的稳定排序。 一个基数排序的流程
二分
二分查找英语binary search也称折半搜索英语half-interval search、对数搜索英语logarithmic search是用来在一个有序数组中查找某一元素的算法。
工作原理¶ 以在一个升序数组中查找一个数为例。 它每次考察数组当前部分的中间元素如果中间元素刚好是要找的就结束搜索过程如果中间元素小于所查找的值那么左侧的只会更小不会有所查找的元素只需到右侧查找如果中间元素大于所查找的值同理只需到左侧查找。 时间复杂度¶ 二分查找的最优时间复杂度为O(logn)O(log_{n})O(logn) 。
while(l-r1){int mid(rl)1;if(dfs(mid))rmid;else lmid;}coutrendl;最大值最小化
注意这里的有序是广义的有序如果一个数组中的左侧或者右侧都满足某一种条件而另一侧都不满足这种条件也可以看作是一种有序如果把满足条件看做 不满足看做 至少对于这个条件的这一维度是有序的。换言之二分搜索法可以用来查找满足某种条件的最大最小的值。 要求满足某种条件的最大值的最小可能情况最大值最小化;
首先的想法是从小到大枚举这个作为答案的「最大值」然后去判断是否合法。若答案单调就可以使用二分搜索法来更快地找到答案。因此要想使用二分搜索法来解这种「最大值最小化」的题目需要满足以下三个条件 1.答案在一个固定区间内 2.可能查找一个符合条件的值不是很容易但是要求能比较容易地判断某个值是否是符合条件的 3.可行解对于区间满足一定的单调性。换言之如果 xxx是符合条件的那么有x1x1x1 或者 x−1x-1x−1也符合条件。这样下来就满足了上面提到的单调性 当然最小值最大化是同理的。 二分最大化最小值 River Hopscotch POJ - 3258
STL 的二分查找
C 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound二者均定义于头文件 中。 lower_bound(dp,dpn,x)-dp;//查找x的第一个位置下标upper_bound(dp,dpn,x)-dp;//查找x的第一个位置下标二者均采用二分实现所以调用前必须保证元素有序。
三分法
三分法可以用来查找凸函数的最大小值。
如果 lmid 和 rmid 在最大小值的同一侧由于单调性一定是二者中较大小的那个离最值近一些较远的那个点对应的区间不可能包含最值所以可以舍弃。如果在两侧由于最值在二者中间我们舍弃两侧的一个区间后也不会影响最值所以可以舍弃。
lmid left (right - left 1);
rmid lmid (right - lmid 1); // 对右侧区间取半
if (cal(lmid) cal(rmid))right rmid;
elseleft lmid;#10017 「一本通 1.2 练习 4」传送带三分套三分
最大化平均值01分数规划
二分01分数规划最大化平均值 Dropping tests POJ - 2976
