深圳8月2期XP02编程大师笔记plus
2025-08-13 14:24:01
发布于：广东
98阅读
0回复
0点赞
DAY01
常见测试点类型
AC ✅
WA ❌ 【常见错误原因：逻辑错误】
PE 格式错误 【常见错误原因：空格 或者 换行】
RE 运行错误 【常见错误原因：数组越界（下标使用错误 数组太小） 或者 除0】
TLE 超时错误 【常见错误原因：时间复杂度过大（循环次数太多）】
//时间复杂度O 保持在10^8
MLE 内存超限 【常见错误原因：数组定义太大/过多】
//一维数组大小10^8 二维数组大小10^4
OLE 输出超限 【常见错误原因：输出过多】
CE 编译错误 【常见错误原因：语法错误】
算法特点//待补充
时间复杂度
O(n)只会记录和n有关的时间复杂度
->没有循环，时间复杂度为O(1) 【常数阶时间复杂度】
->一层循环，循环n次，时间复杂度为O(n)
->两层循环，外层循环n次，里层循环m次，时间复杂度为O(n*m)
枚举算法解题步骤
1. 确定枚举对象【答案】
2. 确定枚举范围【答案所有的可能范围】 - for 循环
多个枚举对象 - 循环嵌套
3. 确定枚举条件【什么情况答案合理】
贪心算法【贪婪算法】
在所有可能的情况中，选择一个对结果最优的方法
“每次只选最优的”
前缀和算法：
每次用一个新的pre数组存储原数组a中前一部份的总和
pre[i] = pre[i-1] + a[i];
#include <iostream>
using namespace std;
int a[100005];
long long pre[100005]; //全局数组 pre[0]=0
//其中 pre[i]记录从第一项～第i项的总和 也叫前i项的总和
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]+a[i]; //计算前缀和数组
//从第1天～第i天吃的数量 = 从第1天～第i-1天吃的数量 + 第i天的数量
}
int x;
cin>>x;
cout<<pre[x]<<endl; //从第一天～第x天的总和
return 0;
}
ans=pre[4]-pre[1] 从第2天～第4天
ans=pre[5]-pre[2] 从第3天～第5天
ans=pre[4]-pre[0] 从第1天～第4天
ans=pre[y]-pre[x-1] 从第x天～第y天
差分算法：
适用多次对不同范围内的元素做相同修改
1. 计算差分数组
使用d数组来记录每两项之间的差值
d[i]=a[i]-a[i-1];
2. 修改时同步修改差分数组 l~r范围内进行+c
d[l]=d[l]+c;
d[r+1]=d[r+1]-c;
3. 借助差分数组还原原数组
a[i]=d[i]+a[i-1];
#include <iostream>
using namespace std;
int a[100005],d[100005]; //a为原数组 d为差分数组
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
d[i]=a[i]-a[i-1]; //计算差分数组
}
for(int i=1;i<=m;i++){ //m次更改
int l,r,c;
cin>>l>>r>>c; //同步更改差分数组 下标l～r范围内的元素+c
d[l]=d[l]+c;
d[r+1]=d[r+1]-c;
}
for(int i=1;i<=n;i++){
a[i]=d[i]+a[i-1]; //还原原数组
cout<<a[i]<<" ";
}
return 0;
}
DAY02
默写订正
1.
请写出 原始差分数组处理
+ 下标在l～r范围内所有元素+c的修改处理 (仅处理1次)
+ 还原原数组处理
（其中原数组名称为a，差分数组名称为d，n个元素，n<=100）
for(int i=1;i<=n;i++){
d[i]=a[i]-a[i-1]; //原始差分数组处理 当前项与前一项差值
}
d[l]=d[l]+c; //d[l]原=a[l]-a[l-1]->(a[l]+c)-a[l-1]
d[r+1]=d[r+1]-c; //d[r+1]原=a[r+1]-a[r]->a[r+1]-(a[r]+c)
for(int i=1;i<=n;i++){
a[i]=d[i]+a[i-1]; //还原原数组处理
}
2.
请写出 前缀和数组处理
+ 输出前x项之和
+ 输出第l～第r项之和
（其中原数组名称为a，前缀和数组名称为sum，n个元素，n<=100）
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i]; //前缀和数组处理 前i-1项总和+第i项=前i项总和
}
cout<<sum[x]; //前x项之和
cout<<sum[r]-sum[l-1]; //第l～第r项之和
二分查找【折半查找】，在一组有序（升序/降序）的元素中查找一个元素，每次查找答案范围都会缩短一半，效率较高。
二分查找的步骤(元素按升序排列)
1. 确定答案的初始范围
2. 确定范围的中间位置，找出中间值t
3. 比较中间值t和目标值x的关系
3.1 t==x 查找完成
3.2 t<x 向左缩小答案范围
3.3 t>x 向右缩小答案范围
重复2和3 直到找到答案或范围内没有元素
二分查找前提条件：1.元素有序 2.元素之间可以比较
500个数字 最多查找几次---没有元素
1～500 （1+500）/2=250 比250小
1～249 （1+249）/2=125 比125小
1～124 （1+124）/2=62 比62小
1～61 （1+61）/2=31 比31小
1～30 （1+30）/2=15 比15小
1～14 （1+14）/2=7 比7小
1～6 （1+6）/2=3 比3小
1～2 （1+2）/2=1 比1小
1～0 范围内没有元素 查找结束
n个数字最多查询次数计算方法：不停用n除以2，直到结果为0
找到第一个【大于】n的 2的x次方，x为最大查询次数
500 2^9=512 最多查询9次
1000 2^10=1024 最多查询10次
第一个大于等于x的元素
#include <iostream>
using namespace std;
int a[n的最大值+5];
int main(){
int n,q,x;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=q;i++){ //q次询问
cin >> x;
int l=1,r=n;
int ans=n+1; //暂时帮助存储答案 没有初始n+1
while(l<=r){ //第一个大于等于x的元素
int mid=(l+r)/2;
if(a[mid]==x){
ans=mid;
r=mid-1;
//可能是答案 但是不一定是第一个 继续向左寻找
}else if(a[mid]>x){
r=mid-1;
}else{ //a[mid]<x
l=mid+1;
}
}
cout << ans;
}
return 0;
}
头文件：#include <algorithm>
格式：
lower_bound(数组名称+开始下标,数组名称+结束下标+1,目标元素)-数组名称
作用：在数组中给定范围内查找第一个【大于等于】目标元素的值
如果未能找到会返回一个不在范围内的下标
格式：
upper_bound(数组名称+开始下标,数组名称+结束下标+1,目标元素)-数组名称
作用：在数组中给定范围内查找第一个【大于】目标元素的值
如果未能找到会返回一个不在范围内的下标
int ans1=lower_bound(a+1,a+n+1,x)-a; //第一个大于等于x
int ans2=upper_bound(a+1,a+n+1,x)-a; //第一个大于x
1. 如何确认数组a中有x的存在
ans1!=ans2 存在
ans1==ans2 不存在
2. 如何找到最后一个【小于】x的数字下标
ans1-1
如何找到最后一个【小于等于】x的数字下标
ans2-1
3. 如何确定数组中x出现了几次
ans2-ans1
有帮助，赞一个