杭州阳陂湖XP02-1班笔记（都是精华）
2025-07-28 20:54:28
发布于：浙江
XP02的小笔记
天麓/改编
XP02 Day01：
1.算法的特性：
1.有穷性（数的尽）
2.确定性（不会飘忽不定）
3.可行性（可以执行）
4.零个或者多个输入
5.一个或者多个输出
2.时空复杂度：
时间复杂度（TLE）
空间复杂度(MLE)
大O记法简化规则：
①只保留最高阶
②若最高阶系数存在 且不是1，则删去该常数。
O(1)代表常数时间复杂度
时间复杂度由快到慢：常对幂指阶
3. LOG
Log₂ ⁿ=y 2∧y=n
4. 枚举算法
枚举算法是一种将 问题的所有可能结果一一列举，并用条件检验是否成立的解题思维。
枚举做题步骤：
①确定枚举对象
②确定枚举对象的取值范围
如果枚举对象存在等式关系，可以优化掉一层for循环
③条件检验是否成立 写在if语句里面。
5.前缀和数组
pre[i]: 前i项的和 即a[1]+a[2]+...+a[i]
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
//前i项的和=前i-1项的和+a[i]
}
子段和-->前缀和 看竖线左边（可以看“子”的勾往哪边勾）
比如求a[l]+ ...a[r] 的和
l-1 |l......r|
6.差分数组
即pre[r]-pre[l-1]
d[i]:a数组第i项和前一项的和
d[i]=a[i]-a[i-1] //d[1]可以这么推保证a[0]为0哦
for(int i=1;i<=n;i++){
cin>>a[i];
d[i]=a[i]-a[i-1];
}
区间修改a[l]~~~~~ a[r] 每个元素 + c
|l~~~~r| +c 差分数组只修改两项 竖线右边
d[l]+=c;
d[r+1]-=c;
d[]---求前缀和得到修改后的原数组
for(int i=1;i<=n;i++){//
pre[i]=pre[i-1]+d[i];
cout<<pre[i]<<" ";
}
XP02 Day02
二分查找算法
- 概念
二分查找也称折半查找 (Binary Search) ，是在一组有序（升序/降序）的数据中查找一个元素，它是一种效率较高的查找方法。(经典案例：猜数字)
2.二分查找步骤:
假设表中元素是按升序排列
重复做的事情：
得到中间元素位置mid
a[mid] 和 目标元素 x 作比较
① a[mid] == x : 找到目标元素，则查找成功
② a[mid] > x : 往a[mid]左边找，更新右端点
② a[mid] < x : 往a[mid]右边找，更新左端点
结束条件：直到子表不存在为止 即l>r
执行条件：子表存在 即 l<=r
不知道重复操作执行多少次，但知道什么时候结束---> while循环
3.代码实现：
//二分查找 有序序列a[l,r]中查找x
int BinarySearch(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; // l > r 退出循环，未找到
}
升序：12345 非降序：122344445
降序：54321 非升序：544443221
在二分查找法中非降序很常用！！！！！
二分求下界：
1.下界：
找到首个 ≥x 的元素位置，如果不存在，返回 N+1
2.二分求下界步骤:
假设表中元素是按非降序排列
重复做的事情：
得到中间元素位置 mid
a[mid] 和目标元素x 作比较
① a[mid] == x : 保存答案，往a[mid]左边找，更新右端点
② a[mid] > x : 保存答案，往a[mid]左边找，更新右端点
③ a[mid] < x : 往a[mid]右边找，更新左端点
结束条件：直到子表不存在为止 即l>r
执行条件：子表存在 即 l<=r
不知道重复操作执行多少次，但知道什么时候结束--->while循环
3.代码实现：
// 二分求下界：在有序数组a[l..r]中查找首个>=x的位置
int lowerbound(int a[], int l, int r, int x) {
int ans = r + 1; // 默认未找到，返回r+1
while (l <= r) {
int mid = (l + r) / 2; // 取中间位置
if (a[mid] >= x) { // 中间值>=x，可能为答案
ans = mid; // 更新候选答案
r = mid - 1; // 继续向左半区查找更小的下标
} else {
l = mid + 1; // 中间值<x，必须向右半区查找
}
}
return ans; // 返回最终答案
}
二分求上界：
1.上界：
找到首个 >x 的元素位置，如果不存在，返回 N+1
2.二分求上界步骤:
重复做的事情：
得到中间元素位置mid
a[mid]和 目标元素x 作比较
① a[mid] == x : 往a[mid]右边找，更新左端点
② a[mid] < x : 往a[mid]右边找，更新左端点
③ a[mid] > x : 保存答案，往a[mid]左边找，更新右端点
结束条件：直到子表不存在为止 即l>r
执行条件：子表存在 即 l<=r
不知道重复操作执行多少次，但知道什么时候结束--->while循环
3.代码实现：
// 二分求上界：在有序数组a[l..r]中查找首个>x的位置
int upperbound(int l, int r, int x) {
int ans = r + 1; // 默认未找到，返回r+1
while (l <= r) {
int mid = (l + r) / 2; // 取中间位置
if (a[mid] > x) { // 中间值>x，可能为答案
ans = mid; // 更新候选答案
r = mid - 1; // 继续向左半区查找更小的下标
} else {
l = mid + 1; // 中间值<x，必须向右半区查找
}
}
return ans; // 返回最终答案
}
STL二分算法（写法和sort很像）
1.lower_bound()
lower_bound 找到首个 ≥x 的元素位置，如果不存在，返回 N+1
头文件：algorithm
int p1= lower_bound(a + 1, a + n + 1, x) - a;
2.upper_bound()
upper_bound 找到首个 >x 的元素位置，如果不存在，返回 N+1
头文件：algorithm
int p2= upper_bound(a + 1, a + n + 1, x) - a;
二分上下界应用：
计算 x 在有序序列中出现次数= x的上界 – x的下界
二分查找应用
结构体数组也可以使用二分查找
// 结构体：存储每个位置的瓶子数和原始位置编号
struct node {
int c;//瓶子个数
int wz;//原位置
} a[N];
二分查找瓶子个数为x位置 结构体数组 先按照 瓶子个数 从小到大排序
bool cmp(node x,node y){
return x.c<y.c;
}
//结构体数组 a[l,r]中查找 x 位置
int BinarySearch(int l,int r,int x){
while(l<=r){
int mid=(l+r)/2;
if(a[mid].c==x) return mid;//a[mid].c哦
else if(a[mid].c<x) l=mid+1;
else r=mid-1;
}
return -1;
}
问x是否在a数组里面出现 或者 x在a数组里面出现次数
---->a数组排序后 用 x的上界-x的下界可以求出x的个数
XP02 Day03：
只要满足单调性 / 二段性就能使用二分
二分答案解题思路：
确定枚举思路，通过二分答案对枚举思路进行优化
1.确定枚举对象： 一般求什么就枚举什么；
2.确定枚举范围：枚举边界，可能的最小值和最大值；
3.确定 check 函数写法！
通常根据限定内容来写check；check 需要先手动模拟，然后用代码实现模拟过程
4.判断答案是否满足单调性：
能否通过中间位置是否可行，去掉其中一半的可能性，缩小检查范围
5.对枚举答案进行二分：
①答案 越大越好：二分答案求上界；
②答案 越小越好：二分答案求下界；
二分答案求上界 答案越大越好
int upper_answer(int l, int r){
int ans = 0;
while(l <= r) {
int mid = (l+r)/2;
if(check(mid)){//找到符合条件的
ans = mid;//①保存答案
l = mid+1;//②越大越好 往右找，更新左端点
}
else{//往左找 更新右端点
r = mid-1;
}
}
return ans;
}
也可能 midmid为数组下标 是需要对a[mid]a[mid]做检查的哦
二分答案求下界 答案越小越好
int lower_answer(int l, int r){
int ans = 0;
while(l <= r) {
int mid = (l+r)/2;
if(check(mid)){//找到符合条件的
ans = mid;//①保存答案
r = mid-1;//②越小越好 往左找，更新右端点
}
else{//往右找 更新左端点
l = mid+1;
}
}
return ans;
}
也可能 midmid为数组下标 是需要对a[mid]a[mid]做检查的哦
注意：
数据类型不确定会不会超过int类型 就使用long long 类型
int 最大值: 231231 -1 即 2147483647
XP02 Day04：
一.进制转换：
1.进制：
十进制：逢10进1
数码：0~9
如：123
二进制：逢2进1
数码：0~1
如：1010
八进制：逢8进1
数码：0~7
如：72
十六进制：逢16进1
数码： 0 1 2 3 4 5 6 7 8 9 A B C D E F
如：AB
2.进制转换：
K进制 转10进制
①先标单位
②每个位置上数字*单位 累加求和
按权展开，累加求和
例题：
1011.110(2) 转10进制
答案：十进制为11.75 可以练习一下
10进制 转K进制
整数部分:除k取余，直到商为0，余数逆序排列;
小数部分:乘k取整，直到小数部分为0，每次取的整数顺序排列。
例题：
42.125(10) 转2进制
答案：2进制为101010.001 可以练习一下
二.前中后缀表达式：
1.概念
中缀表达式是指运算符在操作数中间：a + b
前缀表达式 (波兰式) 是一种没有括号的一种算术表达式，且运算符在操作数的前面： + a b
后缀表达式 (逆波兰式) 是一种没有括号的一种算术表达式，且运算符在操作数的后面： a b +
中缀--->前缀
a + b * c - ( d + e )
①对所有的运算按优先级增补括号 ((a + (b * c)) - (d + e))
②从内到外将运算符移动到两操作数之前：
( - ( + a ( * b c) ) ( + d e) )
③去掉括号：- + a * b c + d e
转换完成
中缀--->后缀
a + b * c - ( d + e )
①对所有的运算按优先级增补括号 ((a + (b * c)) - (d + e))
②从内到外将运算符移动到两操作数之后： ((a (b c ) +) (d e +) - )
③去掉括号：a b c * + d e + -
转换完成
后缀表达式求值：3 5 2 * +
运算规则：
1.从左往右扫描表达式；（操作数在哪边从哪边开始扫描）
2.遇到运算符，运算符放在左边的两个数中间进行运算(运算符左边第一个数字为右操作数，运算符左边第二个数字为左操作数)，并将计算结果作为下次计算的操作数。
后缀表达式转中缀表达式
①从左往右扫描表达式遇到运算符忍住不计算列式子+括号
②去除不影响运算优先级的括号
前缀表达式求值：+ 3 * 5 2
1.从右往左扫描表达式；（操作数在哪边从哪边开始扫描）
2.遇到运算符，运算符放在右边的两个数中间进行运算(运算符右边第一个数字为左操作数，运算符右边第二个数字为右操作数)，并将计算结果作为下次计算的操作数。
前缀表达式转中缀表达式
①从右往左扫描表达式 遇到运算符忍住不计算列式子+括号
②去除不影响运算优先级的括号
前缀转后缀： ①前缀转中缀；②中缀转后缀。
三. 原码、反码、补码
计算机中是以补码的方式存储
原码：
十进制转二进制
最高位 符号位 0 正数 1 负数
10001101
反码：
原码符号位不变 其余位取反
补码：
反码+1
四. 位运算：
1.按位与 &：
将两个二进制数低位对齐，不足高位补零。对两个数字按位进行比较
同1才1否则为0
按位或 |：
将两个二进制数低位对齐，不足高位补零。对两个数字按位进行比较，同0才0否则为1
按位非 ~：
将一个二进制数每一位取反，0 变 1， 1 变 0。
~x=-(x+1)
按位异或 ^：
消消乐 两位 相同时为0，不同时为1。
按位右移 >>:
运算规则， >> a 就将二进制数右移 a 位，高位补零，低位丢弃
按位左移 <<
运算规则: << a 就将二进制数左移 a 位，高位丢弃，低位补零
排列组合
加法原理 -- 每一类方法都可以独立完成任务
做一件事，完成它可以有 n 类办法。第一类办法有 m1m1种方法，第二类办法有 m2m2种方法 ... 在第 n 类办法有 mnmn种方法，那么完成这件事共有 N=m1m1+...+mnmn 种不同的方法。
乘法原理 -- n个步骤都做了才可以完成任务
做一件事，完成它需要分成 n 个步骤。第一步有 m1m1种方法，第二步有 m2m2种方法 ... 在第 n 步办法有 mnmn 种方法，那么完成这件事共有 N=m1m1... * mnmn 种不同的方法。
排列：--顺序重要
从 n 个不同元素中，任取 m(m≤n) 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。
AnmAnm:
站在位置角度思考： n∗(n−1)∗(n−2)∗ (n−m+1)n∗(n−1)∗(n−2)∗ (n−m+1)
Anm=n!(n−m)!Anm=(n−m)!n!
组合：--顺序不重要
从 n 个不同元素中，任取 m(m≤n) 个元素组合
助记： 排列数 /"膨胀系数"
一个组合有m人 "膨胀系数" 为m!m!
排列组合方法
- 特殊优先
- 捆绑法与插空法
- 排除法
- 隔板法
XP02 Day05:动态规划基础
一.概念：
动态规划（DynamicProgrammingDynamicProgramming）是一种多阶段决策问题的方法。它通过将原问题分解为若干个子问题，并这些子问题只解决一次，将结果保存起来，避免重复计算，提高了算法效率。
动态规划能解决的问题类型：方案数问题、最优解问题等
二.解题步骤：
1.思考问题 -> 创建dp数组 (95%的问题 -> 问题问什么，dp数组就是什么含义)
2.求状态转移方程：
如果你是小码君，一觉醒来你出现在了某个位置
小码君脑容量有限，只能想起来最后一步怎么走的/最后一步做的什么选择
根据最后一步怎么走的/最后一步做的什么选择 把大问题转换为已经求得的小问题。
3.初始值：
问题足够小可以直接解决/不能用状态转移方程来推。
coding
三.分类
1.方案数问题：
所有类 方案数都要
2.最优解问题：
所有类 取一个最优的
注意dp数组初始值：
极小值问题 dp数组初始值大的大
极大值问题 dp数组初始值小的小
3.经典例题：
XP02 Day06:栈 队列 递归
一. 栈
1.概念：
栈（stack）又名堆栈，是限定仅在表尾进行插入和删除操作的线性结构，特点为：先进后出（FILO）。
2.数组模拟栈--了解
int st[1010];
int top=0;
//入栈
void push(int x) {
st[++top]=x;
}
//出栈
void pop(){
top--;
}
//判空
bool empty(){
return top==0;
}
//获取栈顶元素
char Top() {
return st[top];
}
//求栈里面的元素
int size(){
return top;
}
标准模板库(Standard Template Library，STL)就是一些常用数据结构（栈、队列等）和算法（sort、swap等）的模板的集合。有了STL，不必再写太多的标准数据结构和算法，且可获得非常高的性能。
3.栈的 STL 模板
使用stack应先添加头文件"stack"
格式： stack<类型名> 栈名;
栈(stack)常用函数:
① push(x)：将x入栈(无返回值)
② pop()：弹出栈顶元素(无返回值)
③ top()：获得栈顶元素(有返回值)
④ empty()：检测栈是否为空，返回true为空，false为非空(有返回值)
⑤ size()：返回栈中元素个数(有返回值)
//无返回值直接调用，有返回值调用后保存/输出。
注意：栈无法直接遍历
例如：
#include<iostream>
#include<stack>//头文件
using namespace std;
stack<string>st;
int main(){
string x="xiaoming",y="xiaoma";
st.push(x);//小明进栈
st.push(y);//小码进栈
//注意： pop 操作/top操作一定要先判断栈非空
if(!st.empty()) st.pop();//栈顶元素 小码弹出栈
if(!st.empty()) cout<<st.top()<<endl;//栈顶元素 小明输出
cout<<st.size()<<endl;//栈里面只有小明 长度为1
if(st.empty()){//栈空 返回真
cout<<"Yes";
}else{
cout<<"No";//小明在栈里面 ，栈非空输出No
}
return 0;
}
4.栈的使用场景：看到先进后出/后进先出 时想到栈
二. 队列
1.概念：
队列（queue）是只允许在一端进行插入，而在另一端进行删除的线性结构。特点为：先进先出 (FIFO)。
2.数组模拟队列--省略
3. 队列的 STL 模板 (循环队列)
队列(queue)的定义：
使用queue应先添加头文件"queue"。
格式：queue<类型名> 队列名;
队列(queue)常用函数：
① push(x)：将x入队(无返回值)
② pop()：令队首元素出队(无返回值)
③ front()：获得队首元素(有返回值)
④ back()：获得队尾元素(有返回值)
⑤ empty()：检测队列是否为空，返回true为空，false非空(有返回值)
⑥ size()：返回队列元素个数(有返回值)
//无返回值直接调用，有返回值调用后保存/输出。
例如：
#include<iostream>
#include<queue>//头文件
using namespace std;
queue<string>q;//建了一个队列
int main(){
string x="xiaoming",y="xiaoma",z="xiaohong";
q.push(x);// xiaoming入队
q.push(y);// xiaoma入队
q.push(z);// xiaohong入队
//xiaoming xiaoma xiaohong
cout<<q.front()<<" "<<q.back()<<endl;//队首为 xiaoming，队尾为 xiaohong
cout<<q.size()<<endl;//3
//注意：对于队列元素检查/弹出队首一定要先保证队列非空
while(!q.empty()){//队列非空
cout<<q.front()<<" ";//输出队首
q.pop();//弹出队首
}
cout<<endl;
//现在队列为空
if(q.empty()) cout<<"Yes";
else cout<<"No";
return 0;
}
4.队列的使用场景：看到先进先出 时想到队列
三. 递归
1.递归函数的概念：
在程序设计领域，递归是指函数（或方法）直接或间接调用自身的一种操作
递归必须要有一个终止条件，这又称作递归边界（递归出口），否则将无限死循环下去了！
2.递归适用场景：
当一个大问题无法直接得到答案，你看到大问题可以变成小问题，大问题和小问题解决方法相同，问题足够小可以直接解决--->想到递归
①问题足够小可以直接解决-->递归边界
②大问题可以变成小问题-->递归公式
因为解决方法一样，可以先写一个解决方法的函数框架
void fun( ){
//递归边界
____________
//递归公式 即大问题如何转化为小问题
____________
}
3.经典例题：
①斐波那契数列
斐波那契数列的第 n 项 我无法一口说出答案，但是可以变成稍小的问题：第n-1项 + 第n-2项；
第n-1项 可以变成第第n-2项 + 第n-3项； 大问题和稍小问题处理方法一样，问题足够小 第1项第2项可以直接说出答案1---->使用递归
先写递归函数的框架：给它对应项数n，它返回给我第n项的值 返回值为int类型。
int F (int n){
//递归边界:问题足够小可以直接解决
if(n1||n2) return 1;
//递归公式:大问题变成稍小问题，稍小问题如何处理：调用F函数，参数变小了。
else return F(n-1)+F(n-2);
}
主函数里面：
cout<<F(n);
②辗转相除法求2个数字的最大公约数
Gcd(a,b) 即a和b的最大公约数
问Gcd(a,b) 我无法一口说出答案，但是
根据被除数和除数的最大公约数 等价于 除数和余数的最大公约数即 Gcd(a,b)等价于Gcd(b,a%b)
我可以把大问题变成稍小问题, 大问题和稍小问题处理方法一样，问题足够小即除数为0
因为 0和任何正整数x的最大公约数为x 即Gcd(x,0)为x 可以 直接说出答案x---->使用递归
int Gcd(int a,int b){//a为被除数 b为除数
//递归边界
if(b0){//除数为0 终止条件
return a; //被除数为最大公约数
}
//递归公式
return Gcd(b,a%b);
}
或者 递归边界：
if(a%b0){//余数为0
return b; //除数为最大公约数
}
两个数字的最小公倍数= 两个数字的乘积 / 两个数字的最大公约数
注意：递归是双向过程，①大问题---->小问题 到达递归边界后触底反弹，②小问题--->大问题。
递归前输出为 大问题---->小问题时输出
递归后输出为 到达递归边界后小问题---->大问题时输出
比如 十进制转二进制
void f(int n){
//递归边界
if(n==0) return;
//递归公式
f(n/2);
cout<<n%2;//放在递归后面 递归回来的路上输出 可以完成逆序输出
}
XP02 Day07:图论
树：是一种非线性结构，能够很好的描述分支和层次特性的书籍集合
树结点的度：结点拥有子树的数量为结点的度，一棵树的度定义为树的所有结点中，度的最大值
前驱和后继：除根节点外，其余结点都有一个唯一前驱，称之为父亲。每个结点都可以有 0 个或者多个后继结点，称之为孩子。如果有些节点有一个共同的父亲结点，那么他们互相称之为兄弟节点
祖先节点：沿根节点到某一结点路径上的有所结点都是这个结点的祖先结点。
树中结点的层次：树中根节点位于第一层，根节点的孩子位于第二层，以此类推。树中最大层次称为树的深度或高度。注意：部分题目里面根节点位于第 0 层。
除了根节点没有父节点外，其余结点都有一个根节点，而且一个拥有 n 个结点的树，有且仅有 n-1 条边。
树的存储
双亲表示法：
struct node{
int data,parent;
};
node tree[5];
tree[i].parent 表示编号为 i 的树结点的父亲
孩子表示法：
struct node{
int data;
vector<int>child;
};
node tree[5];
tree[i].child 存储结点 i 的孩子的位置信息
动态数组vector
vector<类型名 >动态数组名
vector<int>v;
v.push_back(x);
访问下表范围 0~v.size()-1，v.size() 为动态数组 v 中的元素个数
二叉树
二叉树是一种度数最大为 2 的树形结构，即二叉树的每个结点最多有两个子节点，每个结点严格区分左右子结点，它的两棵子树称为左子树，右子树。
性质一
在二叉树第 i 层上最多有 2i−12i−1 个结点。
性质二
深度为 k 的二叉树至多有 2k−12k−1 个结点。
性质三
任意一颗二叉树，若其叶子结点的数量为 n0n0 ,度为 2 的节点数量为 n2n2 ，那么：n0=n2+1n0=n2+1。
如果一颗二叉树，除了叶子节点外其他结点度均为 2 ，且每层的结点总数达到最大，这种特殊形态的二叉树，称之为满二叉树。
如果一颗深度为 k 的二叉树，除了第 k 层外，且每层的结点总数达到最大，第 k 层从左到右节点是连续的，这种特殊形态的二叉树，称之为完全二叉树。
性质四
具有n个节点的完全二叉树的深度是⌊log2(n)⌋+1⌊log2(n)⌋+1 。
性质五
将一棵具有n个节点的完全二叉树，自顶向下，同一层自左向右连续给节点编号 1,2,3,...n。
1.若节点编号为 1，则节点 i 为根，无父节点
2.若 i > 1，则 i 的父节点编号为 i/2。
3.针对编号 i ，左孩子是 2∗i2∗i，右孩子是 2∗i−12∗i−1。
二叉树的存储，以性质 5 为基础。
图
图是一种由顶点和边组成的数据结构，其中顶点表示图中的对象，边表示这些对象之间的关系。
无向图：由没有方向的边组成的图，也称之为无向网络或者无向图。
有向图：由有方向的边组成的图，也称之为有向网络或者有向图。
带权图：边上带有权值的图。
权值：可以理解为通过这条边的长度，时间。
自环：一条边的两端，连接的是同一个顶点。
重边：顶点之间存在多条边链接
简单图：一种不存在自环和重边的图
多重图：一种存在自环和重边的图
度：指的是与一个顶点相连的边的数量，在无向图中度就是它的边的连接数。在有向图中，一个顶点的入度指的是，指向该顶点的边的数量，出度指的是该顶点出发的边的数量。
路径：指的是从一个顶点到另一个顶点的连续边构成的序列。
路径长度：指的是一个路径中，经过的边的数量，或路径权值和。
简单路径：指的是一个顶点到另一个顶点的连续边的序列，不存在重复边和顶点。
环路：指一个路径的起点和终点是同一个顶点，且路径上的其它点可重复。
简单环路：指一个路径的起点和终点是同一个顶点，且路径上的其它点均布重复。
如果一个图不包含任何简单环路，称之为无换图。
连通性：若图中任意两个顶点之间都存在路径，则称该图是连通图。
通过来时的笔记与自己的改编和成 版权费用已交
有帮助，赞一个