我系蒟蒻

我系蒟蒻

我系蒟蒻

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(n^2)<O)(n3)<O(2^n)<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;
int n,m,f;
char a[50][50];
bool vis[50][50];
int dx[]={0,0,-1,0,1};
int dy[]={0,-1,0,1,0};
void dfs(int x,int y){
    if(x==n&&y==m){
        f=1;
        return;
    }
    for(int i=1;i<=4;i++){//左上右下
        int xx=dx[i]+x;
        int yy=dy[i]+y;
        if(xx<1||xx>n||yy<1||yy>m) continue;
        if(a[xx][yy]=='#'||vis[xx][yy]==1) continue;
        vis[xx][yy]=1;
        dfs(xx,yy);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    vis[1][1]=1;
    dfs(1,1);
    if(f==0) cout<<"NO";
    else cout<<"YES";
}

图论
图的概念
图是一种由顶点和边组成的数据结构 其中顶点表示图中的对象,边表示这些对象的关联

顶点(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 dp[31][201];
int n,m;	
int w[31],v[251];
int main(){
	
	cin>>m>>n;
	for(int i=1;i<=n;i++) {
        cin>>w[i]>>v[i];
    }
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;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;
}