x02笔记(X02补充)
2024-02-19 14:46:47
发布于：浙江
自定义栈：
int stl[1000],top;//top--->指针
入栈
void push(int x){
stl[top]=x;
}
判断空栈
bool empty(){
return top!=0;
}
获取长度
int size(){
return top;
}
队列
先进先出(FIFO)
int front(){
return q[head];
}
int back(){DAWW
return q[top-1];
}
reverse(a.begin(),a.endl())；
//反转字符串
16:32 2023/8/15
反转代码
revers(ans.begin(),ans.end())
ASCLL码
int('A')int('Z')=6590;
int('a')int('b')=97122;
int('0')=48
一个合格的算法的特点
1，有穷性：不会死循环。
2，确定性：构成明确。
3，可行性：可实现功能。
4，有输入输出：没有输出的算法是无意义的。
时间复杂度
O(1)<O(log(n))<O(n)<O(nlon(n)<O(n2)<O)(n3)<O(2n)<O(n!)<O(nn)
set 排序 O（log（n））
map 排序 O（n）
冒泡 最好 O（n） 最坏/平均 O（n^2）
sort O（nlog（n)）
STL容器
vecor<数据类型> 名字[长度]
push_back(内容) 在末尾插入
pop_back () 删除尾数据
begin/end 迭代器
empty 判空
set<数据类型> 名字[长度]
insert(内容) 在末尾插入
pop_back () 删除尾数据
begin/end 迭代器
empty 判空
栈
先进后出，栈顶插入，栈顶删除
|—|
| 1 |<-栈顶
|—|
| 2 |
|—|
| 3 |<-栈底
|__|
stack<数据类型> 栈名；
push() 向栈压入成员
pop() 从栈顶取出一个成员
top() 返回栈顶，但不删除
empty()判空
size() 返回元素数量
队列
queue <数据类型> 队列名称
push() 向队列压入成员
pop() 从队首取出一个成员
front() 返回队首顶，但不删除
empty()判空
size() 返回元素数量
back() 返回队未，但不删除
printf常用
"%-md"左对齐m位
"%md"左对齐m位（空格补全）
"%0md"左对齐m位（ 0 补全）
"%.mf"保留小数点后m位
进制转换
n转十
整数
倒取余运算
小数
正取余运算
十转n
位值原理展开
常用
2进制→10进制
2,4,6,8转换法
例子
二进制 1 0 1 0 .1
↑ ↑ ↑ ↑ ↑
权值 8 4 2 1 0.5
原码，反码，补码
正数的原码·补码和反码一样
负数的反码：符号位不动，其他相反
负数的补码：反码+1
例子
正数
0 0000
1 0001
2 0010
负数
-0 0000
-1 1 1 1 1
-2 1 1 10
位运算（二进制）
按位与：全一才一，否则为零
0&0=0
0&1=0
1&1=1
7 & 10
7: 0 1 1 1
10：1 0 1 1
3： 0 0 1 1
7&10=3
按位或：全0才0，否则为1
0|0=0
0|1=0
1|1=1
7 & 10
7: 0 1 1 1
10：1 0 1 1
15：1 1 1 1
7|10=15
按位非：取反 一变零 零变一
~0=1
~1=0
~ 10
10：1 0 1 1
4：0 1 0 0
~10=4
异或 相同为0 不同为1
0^0=0
1^0=1
1^1=0
5^9
5: 0 1 0 1
9: 1 0 0 1
12:1 1 0 0
左移右移
左移<<
右移>>
n左移m位=n*2^m
n右移m位=n/2^m
操作系统
Windows
Linux
DOS 磁盘操作系统
pow(n,m)→a^m
pow(n,0.5)→pow(n)
贪心
在当前问题中选最优解，不考虑全局
二分法
#include<bits/stdc++.h>
using namespace std;
int BinaryseartSearch[105],le=0,ri,mi,tmp,search1,longs=0;
int main(){
cin>>tmp;
for(int i=0;i<tmp;i++){
cin>>BinaryseartSearch[i];
}
cin>>search1;
ri=tmp-1;
while (le<=ri){
longs=ri+le;
mi=longs/2;
if(BinaryseartSearch[mi]>search1){
ri=mi-1;
}
else if(BinaryseartSearch[mi]<search1){
le=mi+1;
}
else if (BinaryseartSearch[mi]==search1){
cout<<mi+1;
return 0;
}
}
cout<<"-1";
return 0;
}
int v=lower_bound(a,a+n,x)-a; 大于
int v=upper_bound(a,a+n,x)-a; 大于等于
归并排序
将待排序序列划分为若干个有序子序列
将有序子序列合并为一个有序序列
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
int n,m,k,T;
int a[N];
int temp[N];
void init(int l1,int r1, int l2 , int r2){
int l = l1, r = l2, cnt = 0;
while(l <= r1 && r <= r2){
if(a[l] < a[r]) temp[cnt++] = a[l++];
else temp[cnt++] = a[r++];
}
while(l <= r1) temp[cnt++] = a[l++];
while(r <= r2) temp[cnt++] = a[r++];
for(int i=0;i<cnt;i++){
a[l1+i] = temp[i];
}
}
void solve(int l,int r){
if(l >= r) return;
int mid = l + r >> 1;
solve(l,mid);
solve(mid+1,r);
init(l, mid, mid+1, r);
}
int main(){
cin >> n;
for(int i=1;i <= n;i++){
cin >> a[i];
}
solve(1,n);
for(int i=1;i<=n;i++){
cout << a[i]<< " ";
}
return 0;
}
快排模板
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
int n,m,k,T;
int a[N];
int temp[N];
void init(int l1,int r1, int l2 , int r2){
int l = l1, r = l2, cnt = 0;
while(l <= r1 && r <= r2){
if(a[l] < a[r]) temp[cnt++] = a[l++];
else temp[cnt++] = a[r++];
}
while(l <= r1) temp[cnt++] = a[l++];
while(r <= r2) temp[cnt++] = a[r++];
for(int i=0;i<cnt;i++){
a[l1+i] = temp[i];
}
}
void solve(int l,int r){
if(l >= r) return;
int mid = l + r >> 1;
solve(l,mid);
solve(mid+1,r);
init(l, mid, mid+1, r);
}
int main(){
cin >> n;
for(int i=1;i <= n;i++){
cin >> a[i];
}
solve(1,n);
for(int i=1;i<=n;i++){
cout << a[i]<< " ";
}
return 0;
}
容斥原理
|A∪B|= =|A|+|B|-|A∩B|
|A∪B∪C|==|A|+|B|+|C|-|A∩B|-|C∩B|-|A∩C|+|A∩C∩B|
树/二叉树
根节点
|
父节点
/ \
兄弟节点 兄弟节点
/ \ / \
叶子节点 叶子节点 叶子节点 叶子节点
具有相同父节点的节点互称为兄弟节点
节点的度：节点的子节点个数
树的度：最大的节点的度
度为0的节点为叶子节点(最下面的)
所有节点层次的最大值称为树的深度
存储方式
父亲表示法
存父节点的下标
孩子表示法
存子节点的下标
二叉树：每个节点最多有2个子节点 Binary Tree 简称BT
右子树 根节点 左子树
|
父节点
/ | \
（右孩子）兄弟节点 |兄弟节点（左孩子）
/ \ | / \
叶子节点 叶子节点 |叶子节点 叶子节点
二叉树的第i层上最多有2^(i-1)个节点，第一层最多1个节点，第一层最多2个节点
深度为k的二叉树最多共有2^k-1个节点
任意一棵二叉树若其叶子节点（度为1节点）的数量为n0，度为2节点的数量为n2，则：n0=n2+2
具有n个节点（n≥0）的完全二叉树的深度为|log（n）|，||表示向下取整
1
/ \
2 3
/ \ /
4 5 6
3.1其左孩子编号为2i(2i≤n)
3.1其左孩子编号为2i+1(2i+1≤n)
树的遍历
1
/ \
2 3
/ \ / \
4 5 6 7
先序遍历；根左右;输出1,2,4,5,3,6,7
1
/
2 3
/ \ /
4 5 6 7
中序遍历；左根右;输出4,2,5,1,6,3,7
1
/
2 3
/ \ /
4 5 6 7
后序遍历；左右根;输4,5,2,6,7,3,1
满二叉树：每个节点都有2个子节点，深度为k的满二叉树共有2^k-1个节点
完全二叉树：除最后一层，前面的是满二叉树，最后一层向左靠拢
完全二叉树
右子树 根节点 左子树
|
父节点
/ | \
（右孩子）兄弟节点 |兄弟节点（左孩子）
/ \ | /
叶子节点 叶子节点 |叶子节点
深搜模板
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;//数组大小
bool vis[N];//标记数组，记录每个点是否被访问过
vector<int> v[N];//邻接表存图
void dfs(int x){
vis[x]=true;//标记当前节点已经被访问
for(int i=0;i<v[x].size();i++){//遍历当前节点的所有邻居
int y=v[x][i];
if(!vis[y]){//如果邻居节点没有被访问过
dfs(y);//继续向下搜索
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);//存图
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(!vis[i]){//如果当前节点没有被访问过
dfs(i);//从当前节点开始搜索
}
}
return 0;
}
图论
图的概念
图是一种由顶点和边组成的数据结构 其中顶点表示图中的对象,边表示这些对象的关联
顶点(Vertex):即结点
边(Edge):即表示关系
无向图(Undirected Graph)
有向图(Directted Graph)
带权图（Weighted Graph）
权值（Weighted） 花费的时间，距离等等
简单图：一种无向图或有向图，其中不存在自环和重边
多重图：一种无向图或有向图，其中存在自环或重边
完全图：每个已知结点之间都有边 无向完全图有n*(n-1)/2条边 有向完全图有n*(n-1)条边
稀疏图：图中边较少
稠密图：图中边较多
度:指与一个顶点相连的边的数量,在无向图中一个顶点的度就是它的边的连接数,在有向图中入度是一个顶点是指指向该顶点的
边的数量,出度是一个顶点是指指从该顶点出发的边的数量
路径:指从一个顶点到另一个顶点的连续序列
路径长度:指一个路径中,经过的边的数量
简单路径:指从一个路径中不存在重复的边
环路:指一路径的起点和终点在一个节点,且路径上的每个顶点可重复
简单环路:指环路上没有重复的路径和节点
若某图没有任何环路,就叫做无环图
连通性:若某图中任意顶点之间都存在路径:则称为连通图
图的存储
1,邻接矩阵
1---3
|
2---0
x/y 0 1 2 3
0 0 0 1 0
1 0 0 0 1
2 1 0 0 1
3 0 1 1 0
无向图的邻接矩阵具有斜对称性,且主对角线一定为0
有向图
1-->3
↓
2<--0
x/y 0 1 2 3
0 0 0 1 0
1 0 0 0 1
2 0 0 0 1
3 0 0 0 0
邻接表
1-->3
↓
2<--0
victore
v[0]=2
v[1]=3
v[2]=none
v[3]=2
最短路
Dijkstre 迪迦哥斯拉，Di健康身体热 算法；Dijkstre算法是典型的最短路径算法,用于计算一个节点到另一个节点的最短路径.
弗洛里德(Floyd)算法通过不断将每一个点当中转点进行松弛，来获取任意两个点之间的最短路线。
A起点
/ \
/ \
中转点K------J终点
动态规划(DP)是指把元问题分解成多个相对简单的问题
动态规划算法通常用于求解某种最优性质的问题
排序法 最坏时间 平均时间复杂度 稳定性
冒泡排序 O(n²) O(n²) 稳定
选择排序 O(n²) O(n²) 不稳定
希尔排序 O(nⁿ)¹<ⁿ<² O(n²) 稳定
快速排序 O(n㏒n) O(n㏒n) 稳定
快速排序 O(n²) O(n㏒n) 不稳定
堆排序 O(n㏒n) O(n㏒n) 不稳定
01背包
1.确定状态:dp[i][j]表示将前i件物品放入一个容量为j的背包可以获得的最大价值
2.问题分解:要包含前i件物品:dp[i-1][j-w[i]],不包含第i件物品dp[i-1][j]
3.确定决策,建立状态转移方程:当 j<w[i] 背包容不下第i件物品:dp[i][j]=dp[i-1][j],
当 j≥w[i] 背包容d下第i件物品:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
const int N=35;
const int M=210;
int dp[N][M];
int n,m;
int w[N],c[N];
cin>>n>>m;
for(int i=1;i<=n;i++) {cin>>w[i]>>c[i]}
for(int i=0;i<=n;i++){
for(int j=1;j<=n;j++){
if(j-w[i]>=0){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[n][m];
return 0;
}
完全背包于01背包：完全背包给了n种物品01背包给了n个物品
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
const int N=35;
const int M=210;
int dp[N][M];
int n,m;
int w[N],c[N];
cin>>n>>m;
for(int i=1;i<=n;i++) {cin>>w[i]>>c[i]}
for(int i=0;i<=n;i++){
for(int j=1;j<=n;j++){
if(j-w[i]>=0){
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[n][m];
return 0;
}
有帮助，赞一个