磊落

Thinking will not overcome fear but action will.

快速排序

快速排序 特点 不稳定排序算法 平均复杂度O(nlog2(n)), 最坏时间复杂度O(n^2) 快排思想–分支思想(不稳定算法) 确定分界点:区间左端点,区间右端点,区间中点,随机选点。 (四选一) 调整区间: 让小于等于分界点的值在分界点的左边,让大于等于分界点的值在分界点右边 递归...

归并排序_逆序对

逆序对 思想 5 4 3 2 1 逆序对是一个数字和后边每一个比它小的数字都构成一个逆序对 在归并过程中分为三类 两个数字在区间左边求逆序对:直接返回merge_sort() 两个数字在区间右边求逆序对: 直接返回merge_sort() 两个数字在区间两边求逆序对: 在归并过程中,右边数组中每加入一个数,...

归并排序

归并排序 特点 稳定排序 时间复杂度:O(nlog2(n)) 递归log2(n)层,每层时间复杂度为O(n) 思想 确定分界点,将给定序列中点作为分界点,划分成两个子序列 mid = (l + r) / 2 递归排序左右区间 left 和 right 归并两个有序数组,注意是有序数组,...

差分

差分 思想 一维差分 一直a1, a2, …, an. 构造b1, b2, …, bn 使得 ai = b1 + b2 + … + bi b数组称为a数组的差分,a成为b的前缀和。 一维差分的用处:假设想对a[L~R]中每个数都加上一个常数C. 即 a[L] + C, a[L+1] + ...

合并果子

合并果子 每次合并权值最小的两个点,要求最后总体体力值最小。 证明 权值最小的两个点,深度最深,且可以互为兄弟。 证明n - 1 个点合并的最小值一定满足 n 个点合并的最小值。 证明 F(n) = F(n - 1) + (a + b) 其中 (a + b) 又是最小的两个点,证毕。 #includ...

双指针算法

双指针算法 思想 双指针算法都是把暴力算法写出来,然后看有没有单调性,如果有单调性就可以把时间复杂度降低 两个指针移动将O(n ^ 2)的算法优化成O(n) 特点 *模板 ``` for (int i = 0; i < n; i++) while (i < j && check(i, j)) j ++; ``` /...

区间覆盖

区间覆盖 将所有区间按照左端点从小到大排序 从前往后依次枚举每个区间,在所有能覆盖start区间中,选择右端点最大的区间 将Start更新成右端点最大值 证明 ans 代表所有可行方案的最小值 cnt代表按照上述方案选法的某一个可行解 所以 ans <= cnt 证明 ans >= ...

区间合并

区间合并 算法例题描述 给定 n 个区间 [li,ri],要求合并所有有交集的区间。 注意如果在端点处相交,也算有交集。 输出合并完成后的区间个数。 例如:[1,3]和[2,6]可以合并为一个区间[1,6]。 输入格式 第一行包含整数n。 接下来n行,每行包含两个整数 l 和 r。 输出格式 共一行,包含...

前缀和

前缀和 思想 原数组 a1, a2, a3, a4, a5, …, an 前缀和 Si = a1 + a2 + a3 + … + ai (i = 1~n) 一维特点 规定:S0 = 0,所有待求数组下标都是从1开始 Si = Si-1 + ai 求[l, r]区间内所有值之和 sum ...

位运算操作

位运算

位运算操作 思想 判读一个二进制数第k位是0还是1 n » k & 1 lowbit操作 返回二进制数最后一位1所代表的数 res = x & (-x) 特点 #include <iostream> #include <algorithm> using namespace std; int l...