一、离散化的含义： 对于数组a[]={1,3,100,2000,500000,......}，把他们一一映射到下标0,1,2,3,4,......的过程叫做离散化 注意： a[]中可能有重复元素 ，需要去重 如何算出x离散化后的值：二分 二、离散化的过程 vector::erase()的用法：从ve
Published on 2022-01-12
一、基础知识 &：与：两个位都为1时，结果才为1 3&5 即 0000 0011 & 0000 0101 = 0000 0001，因此 3&5 的值得1 |：或：两个位都为0时，结果才为0 3|5即 0000 0011 | 0000 0101 = 0000 0111，因此3|5的值得7 ^：异或：两
Published on 2022-01-12
前缀和与差分互为逆运算 一、一维前缀和 设有序列${a}_1,{a}_2,{a}_3......{a}_n$，则该序列的前缀和${S}_i={a}_1+{a}_2+{a}_3+......+{a}_i$ 作用：快速求出${a}_l$到${a}_r$之间所有数的和：${S}_r-{S}_{l-1}$
Published on 2022-01-11
核心思想： 对于一个序列：用两个指针维护一段区间 对于两个序列：用两个指针对两个序列进行有规律地维护（如归并排序） 将时间复杂度O(n^2)的算法优化至O(n) for (int i = 0; i < n; i++) { for (int j = 0; i < m; j++) { //...
Published on 2022-01-11
一、二分的本质 在一个序列中，存在某种性质，使得该序列可以一分为二，使左半边满足这种性质，右半边不满足这种性质，二分可以寻找这种性质的边界 常用于边界问题 二、整数二分的过程 当我们想二分找出 x 点时 找到一个中间值 d=(l+r+1)/2 ，判断这个点的性质是否具有左半边性质（ l+r+1 的原
Published on 2022-01-10
一、高精度加法（正数+正数） 大整数的存储：将个位存在 a[0] ，十位存在 a[1] ，百位存在 a[2] ......，方便进位，因为如果按照正序存储的话，最高位需要进位时，所有数字都需要向右移一位 模拟竖式加法 vector::size()函数的用法：假设有vector<>a，则a.size(
Published on 2022-01-10
一、中心思想：分治 以中间点为界： mid=(l+r)/2 递归排序分界点左边和右边 归并——合二为一 二、核心内容：合二为一 分界点左边从小到大排序：数组 a ，分界点右边从小到大排序：数组 b ，答案数组 ans 指针 i ， j 分别指向
Published on 2022-01-09
一、中心思想：分治 确定分界点 x ： q[l] ， q[r] ， q[(l+r)/2] ，或者任取一点 调整区间，小于等于 x 的放在 x 左边，大于 x 的放在 x 右边 递归将左边和右边分别排好序
Published on 2022-01-09
一、解释 如果递归函数调用自己，则被调用的函数也将调用自己，这将无限循环下去，除非代码中包含终止调用链的内容。通常的方法是将递归调用放在if语句中。例如，void类型的递归函数x()的代码如下： /* void x(参数) { 代码块1 if (递归条件) x(参数) 代码块2 }
Published on 2022-01-09
