深圳8月2期XP02编程大师笔记plus
2025-08-20 14:29:53
发布于：广东
295阅读
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
Day03
二分答案基础模板
#include <bits/stdc++.h>
using namespace std;
long long n,m,a[1000005];
long long h;
bool check(long long x){
//在当前的答案X给出后，是否能够满足条件呢，检查一下
}
int upper_answer(long long l,long long r){
while(l<=r){
long long mid = (l+r)/2;
if(check(mid)){//符合条件，越大越好往右找，越小越好往左找
h=mid;//记录当前满足条件的答案
//改变区间范围
}else{
//改变区间范围
}
}
return h;
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
h = max(a[i],h);
}
long long l= ,r= ;//锁定答案区间
cout << upper_answer(l,r);
return 0;
}
Day04
十进制
1. 满十进一
2. 每一位上数值只能在0～9
3. 相邻两位之间数值为10倍
二进制 【计算机使用】
1. 满二进一
2. 每一位上数值只能在0～1
3. 相邻两位之间数值为 2 倍
世界上只有10（二进制中2的表示方法）种人
X进制
1. 满 X 进一
2. 每一位上数值只能在0～X-1【每位数值超过9，用字母表示】
3. 相邻两位之间的数值为 X 倍
8进制 ： 0～7
16进制 ：0～15 【10A 11B 12C 13D 14E 15F】
如何表示一个数值的进制
1. 括号法
2. 后缀法 二进制B 八进制O 十进制D 十六进制H
10B 123D
3. 前缀法 二进制0b 八进制前缀0 十进制无前缀 十六进制0x
X进制转十进制
1. 从低位向高位编号（从0开始，依次+1）
2. 用每一位的数值*每一位的权值 累加后的结果为十进制结果
tips：第i位的权值=进制数X的i次方
转换为十进制
43O 八进制 =4*8+3*1=35
1FH 十六进制 =1*16+F(15)*1=31
B2H =11*16+2*1=178
11011B =1*16+1*8+0*4+1*2+1*1=27
十进制转换为X进制
1. 整数部分：除X取余，逆序排列
不停用数值除以X，直到当前商为0停止，每次记录余数结果，逆序作为答案
2. 小数部分：乘X取整，顺序排列
不停用小数部分数值乘X，直到小数部分为0停止，每次记录整数结果，顺序作为答案
0.75*2=1.5 整数部分1 小数部分0.5
0.5*2=1.0 整数部分1 小数部分0.0
255D -> FFH
255/16 = 15...15(F)
15/16 = 0...15
中缀表达式转前缀 和 后缀:
在保证计算优先级的前提下，移动运算符位置
1. 按计算顺序 添加上括号
2. 按照规则将运算符 前移或后移
3. 去掉括号
（（1 + 3）* 2）
转后缀表达式
（（1 3 +）2 *） 1 3 + 2 *
转前缀表达式
（*（+ 1 3） 2） * + 1 3 2
后缀表达式的计算过程
1. 从左往右扫描表达式 （从操作数开始扫描）
2. 遇到运算符，找出紧挨着的左侧两个操作数进行运算，将结果放回去
左操作数 右操作数 运算符
前缀表达式的计算过程
1. 从右往左扫描表达式 （从操作数开始扫描）
2. 遇到运算符，找出紧挨着的右侧两个操作数进行运算，将结果放回去
运算符 左操作数 右操作数
前/后缀表达式转中缀 -> 计算但是用原式子替代
1. 如何区分前缀还是后缀还是中缀 （看运算符的位置）
2. 如何将前缀表达式转换为后缀表达式（前->中->后）
内存 存储单位
1. bit 比特
计算机中最小的数据单位，1bit 表示二进制的一位
2. byte B字节 1B=8bits
计算机中内存和存储的基本单位
1KB=1024B
1MB=1024KB
1GB=1024MB
机器数由两部分组成：符号位+数值位
其中
符号位0表示正数 1表示负数
数值位是绝对值的二进制表示
+3的机器数 //一般默认用8位表示
符号位1位 数值位7位
0 0000011
-3的机器数
符号位1位 数值位7位
1 0000011
原码 == 机器数
+0:0000 0000
-0:1000 0000 在原码中+0和-0不一致
原码在进行加减时，需要判断符号位，很麻烦
在原码的基础上 - 发现反码
1. 正数的反码 == 原码
2. 负数的反码，原码的符号位不变，数值位按位取反【0变1 1变0】
+6的反码 = +6的原码 = +6的机器数
-6的反码
1. 先算-6的原码 1 000 0110
2. 符号位不变 剩下取反 1 111 1001
-5的反码
1. -5的原码 1000 0101
2. 1111 1010
+5的反码=+5的原码 0000 0101
+0:0000 0000
-0:1111 1111
(-5)反 + (+5)反
= 1111 1010 + 0000 0101 = 1111 1111 = -0 错误
补码
1. 正数的补码=正数的原码
2. 负数的补码=反码+1 [满二进一]
-5的补码 = -5的反码+1
= 1111 1010 + 1
= 1111 1011
1. 正数：三码和一 原码=反码=补码
2. 负数：原码 反码=原码取反 补码=反码+1
1111 1101补码 请计算出其真值（原码对应的数值） -> -3
1.判断符号 负数
2.求出反码=补码-1 反码:1111 1101-1=1111 1100
3.求出原码=1000 0011
4.求出真值 绝对值 11B -> 3D
X>>a 将X的补码右移a位
结果 = X除以2的a次方
9>>1 = 9/2 = 4
X<<a 将X的补码左移a位
结果 = X乘2的a次方
9<<1 = 9*2 = 18
排列 - 在n个数中选择m个元素，顺序非常重要
组合 - 在n个数中选择m个元素，顺序不重要
在3个数中{1,2,3}选择2个元素的排列
{1,2} {1,3} {2,3} {2,1} {3,1} {3,2}
在3个数中{1,2,3}选择2个元素的组合
{1,2} {1,3} {2,3}
1. 加法原理
如果完成一件事情有n种选择(n种中选1个就可以解决)
完成这件事情的方案数=n种方案数累加
2. 乘法原理
如果完成一件事情有n个步骤(n个步骤必须都要选择)
完成这件事情的方案数量=n个步骤方案数累乘
DAY05
动态规划算法 -- 分治思想
1.将原问题划分成类似的子问题
2.记录每一个子问题的结果
3.合并得到原问题的解
动态规划算法特点："想清楚了再做"
步骤
1. 明确原问题
2. 划分子问题【状态】
3. 存储每一个子问题的解 --- 一般使用数组
4. 处理特殊情况
5. 找规律【状态转移方程】--- 一般使用for推导
6. 输出原问题的解
完成动态规划习题的步骤
1. 确定原问题
//到达n块石板的方案数量
2. 开始划分,前提条件是什么？
//先到达第n-1块 再到达第n-2块
3. 思考子问题是什么？【状态】--- 题目要什么 问题就是什么
//到达i块石板的方案数量
4. 处理特殊子问题的解
//到达1块 和 2块石板的方案数量
5. 如何推导出原问题【状态转移方程】--- 一般借助for循环实现
//到达i石板的方案数=到达i-1石板的方案数+到达i-2石板的方案数
6. 输出原问题的解
#include <iostream>
using namespace std;
long long dp[50]; // dp[i]到达第i块石板的方案数
int main(){
int n;
cin>>n; //石板数量
dp[1]=dp[2]=1; //特殊情况
for(int i=3;i<=n;i++){ //记录子问题的解
dp[i]=dp[i-2]+dp[i-1]; //状态转移方程式
}
cout<<dp[n]; // dp[n]到达第n块石板的方案数
return 0;
}
#include <iostream>
using namespace std;
long long dp[1005][1005];
int main(){
int n,m;
cin>>n>>m; //n行m列
for(int i=1;i<=n;i++){ //最左侧 n行的第一列值全部为1
dp[i][1]=1;
}
for(int j=1;j<=m;j++){ //最上侧 第一行的m列值全部为1
dp[1][j]=1;
}
for(int i=2;i<=n;i++){ //从第2行～第n行 从第2列～第m列
for(int j=2;j<=m;j++){
//先到达左侧点 或 先到达上侧点
dp[i][j] = (dp[i][j-1]+dp[i-1][j])%11451;
}
}
cout<<dp[n][m]; //到达(n,m)的方案数量
return 0;
}
#include <iostream>
using namespace std;
int a[n的最大值+5]; //a[i]存储第i个关卡的知识点数量
long long dp[n的最大值+5]; //dp[i]从第1个关卡～第i个关卡的知识点数量最大
int main(){
int n;
cin>>n; //关卡数量
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[1]=a[1]; //从第1关～第1关 只有一种可能 只能选第一关
dp[2]=max(a[1],a[2]); //从第1关～第2关 只有2种可能 选第一关 选第二关
for(int i=3;i<=n;i++){
//第一种情况：不选第i关
//从第1关～第i-1关的知识点数量最大 dp[i-1]
//第二种情况：选第i关 不选第i-1关
//从第1关～第i-2关的知识点数量最大+第i关的知识点数量 dp[i-2]+a[i]
dp[i]=max(dp[i-1],dp[i-2]+a[i]);
//dp[5] = max(dp[4] , dp[3]+a[5])
}
cout<<dp[n];
return 0;
}
#include <iostream>
using namespace std;
int a[n的最大值][n的最大值]; //a[i][j]存储(i,j)的数值
long long dp[n的最大值][n的最大值]; //dp[i][j]表示从最后一行到达(i,j)的最小和
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
//原问题：从顶->底 变成 从底->顶 dp[1][1]
//特殊情况 第n行 最底端 最小和=本身
for(int j=1;j<=n;j++){
dp[n][j]=a[n][j];
}
//从第n-1行开始～第1行结束 从第1列～第i列
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+a[i][j];
} //到达(i,j)之前，先到达(i+1,j)或(i+1,j+1)
}
cout<<dp[1][1];
return 0;
}
Day07
//静态数组 1.不能进行容量的改变 2.不能进行删除的修改[覆盖]
动态数组 vector
1. 头文件：#include <vector>
2. 一维定义：vector<数据类型> 数组名称;
二维定义：vector<数据类型> 数组名称[行数量]; //行数量固定 列数量动态
vector< vector<数据类型> > 数组名称; //行列都不固定
tips：动态数组定义后里面没有任何内容，包括下标 不能直接使用v[i]
【放入元素后才会出现对应的下标】
vector<数据类型> 数组名称(数量x); //定义一个长度预先为x的动态数组
3. 放入元素：数组名称.push_back(元素x); //向数组末尾放入一个元素x
tips：动态数组中，元素的下标默认从0开始
4. 遍历数组，借助动态数组长度函数 --- 数组名称.size()
for(int i=0;i<数组名称.size();i++){
cout<<数组名称[i]<<" ";
}
5. sort的使用：sort(数组名称.begin(),数组名称.end());
其中，数组名称.begin()，指向数组中第一个元素
数组名称.end()，指向数组中最后一个元素的后一个
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v;
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
v.push_back(x); //输入一个元素，并放入数组
}
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
return 0;
}
DAY08
深度优先搜索 DFS （Depth First Search）
“一直沿着深度寻找答案，如果不行返回” “不撞南墙 不回头”
应用：走迷宫 排列组合
准备工作
1. 存储地图：二维数组 类型需要根据题目给到的地图调整
2. 明确起点和终点
3. 只要我的下一步可以行走那么一直走下去，如果下一步不能行走退回到上一步
向下走一步 判断下一步是否符合要求 继续向后先走 【递归】
递归函数的作用：站在xy这个位置上向下行走
a.函数结束的条件：到达终点--提前结束 四个方向没有办法行走
b.任务：寻找下一步的具体信息 并且判断是否可以向下行走
文件判题
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
freopen("文件名称.in","r",stdin); //只能修改中文区域
freopen("文件名称.out","w",stdout);
//代码编辑区
fclose(stdin);
fclose(stdout);
return 0;
}
从起点(sx,sy)到终点(ex,ey)的方案数量
1.输入n和m，表示行列数量
2.输入sx,sy,ex,ey，表示起点终点信息
3.输入一个n行m列的地图，其中'.'表示空地，'@'表示障碍物
#include <iostream>
using namespace std;
int n,m,sx,sy,ex,ey;
char mp[15][15];
bool vis[15][15]; //标记当前位置是否到达
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1}; //方向数组
int cnt; //记录方案数
void dfs(int x,int y){ //站在xy上向四周扩展
if(x==ex && y==ey){ //站在终点上
cnt++;
return;
}
for(int i=1;i<=4;i++){ //向四周寻找下一步
int nx=x+dx[i];
int ny=y+dy[i]; //计算下一步信息
if(1<=nx && nx<=n && 1<=ny && ny<=m
&& mp[nx][ny]!='@'
&& vis[nx][ny]==false){ //判断是否到达
vis[nx][ny]=true;
dfs(nx,ny);
vis[nx][ny]=false; //回溯
}
}
}
int main(){
cin>>n>>m>>sx>>sy>>ex>>ey;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
vis[sx][sy]=true; //从起点开始搜索
dfs(sx,sy);
cout<<cnt;
return 0;
}
DAY09
深度优先搜索 （DFS）-递归【栈】
把所有从起点到终点的路径全部走一遍
特点：一定能找出所有的方案
广度优先搜索 （BFS）-【队列】先进先出
一种【层层递进的扩散】算法
特点：第一次到达 路径一定最短
#include <iostream>
#include <queue>
using namespace std;
int main(){
queue<int>q; //定义队列
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
q.push(x); //将元素x放入队列
}
while(q.size()){ //只要还有元素
cout<<q.front()<<endl; //取出队首元素
q.pop(); //删除元素
}
return 0;
}
1. 输入n 输入地图
2. 明确起点和终点 起点左上角 (1,1) 没有终点
3. 开始BFS
3.1 将起点放入队列 【队列是结构体类型的 行 列信息】
3.2 如果队列不为空，每次取出队首，向四周扩展
如果下一步是可以行走的，放入队列
逃离迷宫1
逃离迷宫2/2.5
有帮助，赞一个