XP02-1 Day01 模拟枚举、贪心：
1. 算法的特性：
1.1 有穷性
1.2 确定性
1.3 可行性
1.4 0个或多个输入多个
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 upper_bound(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:
upper_bound使用二分查找算法来寻找序列中第一个大于指定值的元素
该函数将返回一个指向该元素的地址
如果没有找到符合条件的元素,它将返回超出范围的位置
头文件:algorithm
upper_bound(a + 1,a + n + 1,x) - a;
在a + 1 ~ a + n + 1范围内进行二分查找
9 计算x在有序序列中出现次数 = x的上届 - x 的下界
XP02-1 Day03 二分答案：
只要满足单调性、二段性即可使用二分方法。
T1 保护环境(题目链接：https://www.acgo.cn/problemset/info/43051?homeworkId=10850&teamCode=1898611936787804160)
方法1：枚举 枚举锯片高度的所有可能，从大到小检测，找到第一个砍得>=m的高度。
锯片高度的最大值：所有树的高度最大值；
锯片高度的最小值：0。
Check函数：
bool check(long long x) {
long long sum = 0; // 获得木材
for (int i = 1; i <= n; i++) { // 检查
if (a[i] > x) sum += a[i] - x;// 若树的高度<锯子的高度，则锯下来0
}
return sum >= m; // 若sum >= m返回真，否则返回假
}
时间复杂度：O(1015)，超时。
XP02-1 Day04 初赛专题：
1. 进制转化:
1.1 相关概念解释:
数 码: 进制中每一位上数的表示
十 进 制: 每一位可取 0~9 这十个数码,计数的基数为10,超过9须用多位数进行表示
二 进 制: 每一位可取 0~1 这两个数码,计数的基数为10,超过9须用多位数进行表示
八 进 制: 每一位可取 0~7 这八个数码,计数的基数为10,超过9须用多位数进行表示
十六进制: 每一位可取 09,AF 这十六个数码,计数的基数为10,超过9须用多位数进行表示
位 权: 进制中某一位上的"1"所表示的大小
1.2 K进制转十进制:
按位权展开法:将各个数码与它的权值相乘再相加
对于一个k进制数:小数点从右往左看,第i位的权值为k^i(i-1)
e.g. 1011.110(二进制) = 12^3 + 02^2 + 12^1 + 12^0 + 12^-1 + 12^-2 + 0*2^-3
1.3 十进制转K进制(K≠10):
整数部分:除基倒排余法,不断除以K,直到被除数为0,倒读余数即为所求进制下的该数
小数部分:循环乘法:乘K取整,小数部分积为0结束,结果正序排列
什么?!张文武不发笔记了?!他不发我发!(本帖由 @1234567890 赞助发出)
欢迎补充_
求推!
