XP02-1 Day01 模拟枚举、贪心:
1. 算法的特性:
1.1 有穷性
1.2 确定性
1.3 可行性
1.4 0个或多个输入ruo
1.5 1个或多个输出
2. 执行次数称为语句频度,记为T(n)
3. 大O记法简化规则:
3.1 O(1)代表所有常数时间复杂度
3.2 修改后的时间频度函数T(n)
3.3 若最高阶系数存在且不是1,则删去该系数
4. 求时间复杂度:
4.1 构建一个有常数项,有非常数项的表达式
4.2 删掉常数项
4.3 保留最高阶
4.4 删掉最高阶的系数
5. 1s的运行次数约为10^8次(超过该上限后,代码会TLE!!!)
6. 前缀和数组:
前缀和是一个常见的算法技巧,用于快速计算数组中某个区间内元素的和
例如用pre[i]表示a数组中前i个数之和:
a = {3,4,1,3,2};
pre = {3,7,8,11,13};
pre[L-1] + sum(L,R) = pre[R]
sum(L,R) = pre[R] - pre[L-1]
pre[i] = pre[i-1] + a[i]
7.差分数组:
差分是一种数学运算方法,一维差分是指数列中相邻两项之间的差值
例如用d[i]表示a数组中第i个数与第i-1个数的差:
a = {3,4,1,3,2};
d = {3,1,-3,2,-1};
d[i] = a[i] - a[i-1]
d[i] + a[i - 1] = d[i]
将原数组a的第i~j项增加n时,差分数组d的第i项+n,第j+1项-n
XP02-1 Day02 二分查找:
1. 二分查找定义:
二分查找(Binary Search)是一种在有序数组中查找特定元素的算法,
通过分治策略将搜索范围逐步缩小至目标值。
其核心思想是将数组分为两半,i 比较中间元素与目标值的大小,f
根据比较结果选择继续在左半部分或右半部分查找,
每次操作都将搜索范围减半。
2. 二分查找步骤(通过不断缩小搜索范围,直到找到目标元素或搜索范围为空)
(1)初始化左右边界left和right;
(2)计算中间位置mid = (left + right) / 2;
(3)当左边界小于等于右边界时,执行以下操作:
(a)中间元素等于目标元素,则查找成功;
(b)如果中间元素小于目标元素,则更新左边界为mid+1
(c)如果中间元素大于目标元素,则更新右边界为mid-1e
3. 二分查找时间复杂度:
求n个有序的数,二分查找的复杂度:
看n除以多少次2为0
即看n除以___次2为1 + 1
为log n向下取整 + 1
时间复杂度1次可以忽略,所以二分查找的时间复杂度 = O(log n)
4. 代码实现二分查找:
int BinarySearch(int a[],int l,int r,int x){
while(l <= r){
int mid = (l + r) / 2;
if(x == a[mid]) return mid;
else if(a[mid] > x) r = mid - 1;
else if(a[mid] < x) l = mid + 1;
}
return -1;
}
5. 二分求下界:
5.1 下界:
在一个非降序列a[N]中查找x
(1)x存在 ==> 返回x首次出现的i
(2)x不存在 == > 则返回插入x后仍保持有序的起始位置
5.2 步骤:
假设表中元素是非降序排列
重复做:
(1) 得到中间元素mid
(2)将a[mid]与目标x比较:
a[mid] == x: 保存答案,往a[mid]左边找,更新右端点
a[mid] > x: 保存答案,往a[mid]左边找,更新右端点
a[mid] < x:往a[mid]右边找,更新左端点
5.3 实现:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int lowerbound(int a[],int l,int r,int x){
int ans = r + 1;
while(l <= r){
int mid = (l + r) / 2;
if(x <= a[mid]){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
6. 二分求下界:
6.1 下界:
在一个非降序列a[N]中查找x
(1)x存在 ==> 返回x最后一次出现位置的下一个位置j
(2)x不存在 == > 则返回插入x后仍保持有序的起始位置
6.2 步骤:
假设表中元素是非降序排列
重复做:
(1) 得到中间元素mid
(2)将a[mid]与目标x比较:
a[mid] == x: 往a[mid]右边找,更新左端点
a[mid] > x: 保存答案,往a[mid]左边找,更新右端点
a[mid] < x:往a[mid]右边找,更新左端点
6.3 实现:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int upperbound(int a[],int l,int r,int x){
int ans = r + 1;
while(l <= r){
int mid = (l + r) / 2;
if(x < a[mid]){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
7. 若求上下界时,无满足条件数据,则返回N+1
8. STL二分算法:
8.1 lower_bound:
lower_bound使用二分查找算法来寻找序列中第一个大于或等于指定值的元素
该函数将返回一个指向该元素的地址
如果没有找到符合条件的元素,它将返回超出范围的位置
头文件:algorithm
lower_bound(a + 1,a + n + 1,x) - a;
tips:地址不建议直接输出如果要得到下标志、可以与首地址做差
8.2 upper_bound:
lower_bound使用二分查找算法来寻找序列中第一个大于指定值的元素
该函数将返回一个指向该元素的地址
如果没有找到符合条件的元素,它将返回超出范围的位置
头文件:algorithm
lower_bound(a + 1,a + n + 1,x) - a;
在a + 1 ~ a + n + 1范围内进行二分查找
9 计算x在有序序列中出现次数 = x的上届 - x 的下界
什么?!张文武不发笔记了?!他不发我发!
欢迎补充_
求推!