笔记-C++
算法整合 (cpp)
<制作ing>
基础
O2优化
#pragma GCC optimize(2)
O3优化
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
标准模板
#include<bits/stdc++.h>
using namespace std;
int main(){
return 0;
}
泛型编程
tips: T可替换
template<T>
T jia(T a,T b){
return a + b;
}
STL容器
不涉及迭代器
栈：
// 头文件 : <stack>
// 栈 : 1、先进后出 2、只能从一端进出，另一端封闭
// push : 往栈里添加一个元素 (进栈、入栈、压栈)
// pop : 从栈顶删除一个元素 (出栈、弹栈)
// top : 访问栈顶元素
// empty : 判断栈是否为空，如果为空 1
// size : 获取栈中元素的个数
队列：
// 头文件 : <queue>
// 队列 : 1、先进先出 2、从一端进，另一端出
// 进数据的一端：队尾
// 出数据的一端：队首
// push : 从队尾添加一个元素 (入队)
// pop : 从队首删除一个元素 (出队)
// front : 访问队首元素
// back : 访问队尾元素
// empty : 判断栈是否为空，如果为空 1
// size : 获取栈中元素的个数
优先队列：
// 头文件 : <queue>
// 优先队列 : 具有最高优先级的元素先出的特征
// push : 从队尾添加一个元素 (入队)
// pop : 从队首删除一个元素 (出队)
// top : 访问队首元素
// 不能访问队尾元素
// empty : 判断栈是否为空，如果为空 1
// size : 获取栈中元素的个数
// 1、优先队列存放的数据类型
// 2、优先队列的底层容器
// 3、优先级规则, 不写就默认降序
// greater<int> 升序
// less<int> 降序
priority_queue<int, vector<int>, greater<int> > q;
priority_queue<int, vector<int>, less<int> > p;
涉及迭代器
迭代器方法遍历
//附加(迭代器遍历):
vector<int> vec_1(10,0);
for(auto temp: vec_1){
cout<<temp<<' ';
}
//----------
//set专属遍历输出:
//升序
set<int,less<int>> se_1(10);
//倒序
set<int,greater<int>> se_1(10);
//----------
动态数组
//动态数组常用用法
//日期: 2024/4/27
//初始化:
//----------
// 创建一个新的空的动态数组
vector<int> vec_1;
// 创建一个新的空的初始空间为10的动态数组 -元素默认为0
vector<int> vec_2(10);
// 创建一个新的空的初始空间为10的动态数组 -元素默认为3
vector<int> vec_3(10,3);
// 创建一个新的空的动态数组 -拷贝vec_3的内容
vector<int> vec_4(vec_3);
// 创建一个新的空的动态数组 -拷贝list_1的内容(前五个)
int list[10]={1,2,3,4,5,6,7,8,9};
vector<int> vec_5(list,list+5);
//----------
//访问内容(从0开始):
cout<<vec_5[2];
//操作内容:
//----------
//普通:
//在vec_1的末尾添加一个元素
vec_1.push_back(114514);
//在vec_1的末尾删除一个元素
vec_1.pop_back();
//获取vec_1动态数组的第一个元素
vec_1.front();
//获取vec_1动态数组的最后一个元素
vec_1.back();
//获取vec_1动态数组的长度
vec_1.size();
//判定vec_1是否为空
vec_1.empty();
//清空vec_1
vec_1.clear();
//迭代器需求:
//获取vec_1的第一个元素的迭代器
vec_1.begin();
//获取vec_1的最后一个的后一位的元素的迭代器
vec_1.end();
//删除vec_1指定位置的元素
vec_1.erase(vec_1.begin());
//----------
集合
//集合常用用法
//日期: 2024/4/27
//概念:
//----------
//set: 有序且元素不重复的类型
//multiset: 有重复元素的集合
//----------
//初始化:
//----------
//初始化一个set_1集合
set<int> se_1;
//初始化一个se_2集合内容复制se_1
set<int> se_2(se_1);
//初始化一个se_3集合内容复制list_1(+10可自定义)
int list_1[100] = {1,2,3,4,5,6,7,8,9};
set<int> se_3(list_1,list_1+10)
//----------
//操作:
//----------
//普通:
//给se_1添加内容
se_1.insert(114);
//获取se_1的长度
se_1.size();
//判定se_1是否为空
se_1.empty();
//清空se_1
se_1.clear();
//查找元素在se_1中是否出现过，找到就返回回应的迭代器，否则就返回end()
se_1.find(114);
//删除se_1中指定的内容
se_1.erase(10);
//迭代器需求:
//遍历(其他没有了)
//----------
哈希表
//哈希表常用用法
//日期: 2024/4/27
//概念:
//----------
/*
一键对一值
键是唯一的
值可以重复
键不可修改
值可以修改
*/
//----------
//初始化:
//----------
//定义一个'键'为string类型'值'为int类型的哈希表
map<string,int> ma_1;
//----------
//输出:
//----------
//mode 1
cout<<ma_1["键"];
//mode 2
map<string,int>::iterator it;
it = ma_1.find("2233");
if(it!=end()){
cout<<it->first<<" "<<it->second<<endl;
}
//遍历
for(auto i: ma_1){
cout<<i.first<<" "<<i.second<<endl;
}
//----------
//操作:
//----------
//新建一个键值对(键为"apple"值为1)
ma_1.insert({"apple",32});
//寻找哈希表中键为"boom"的迭代器
ma_1.find("boom");
//统计哈希表中"apple"出现的次数 (由于哈希表键不能重复 所以只会返回0\1)
ma_1.count("2233");
//删除键"2233"
ma_1.erase("2233");
//----------
算法
二分查找
tips: l:左 r:右 t:寻找的数字 a[]:查找的数组
int dichotomy(int l,int r,int t,long long int a[]){
while(l<r){
int mid=(l+r)/2;
if(a[mid] >= t){
r=mid;
}
else{
l=mid+1;
}
}
if(a[r]==t) return r;
return -1;
}
归并排序
/* C++ Code */
//可更改数组大小
int fun_temp[1000005];
void fun(int left_bj,int right_bj,int fun_sz[]){
int fun_mid = (left_bj+right_bj)/2;
if(left_bj==right_bj) return;
fun(left_bj,fun_mid,fun_sz);
fun(fun_mid+1,right_bj,fun_sz);
int temp_l = left_bj,temp_j = fun_mid+1,temp_k = temp_l;
while(temp_l<=fun_mid && temp_j<=right_bj){
if(fun_sz[temp_l] <= fun_sz[temp_j]) fun_temp[temp_k++] = fun_sz[temp_l++];
else{
fun_temp[temp_k++] = fun_sz[temp_j++];
}
}
while(temp_l<=fun_mid){
fun_temp[temp_k++] = fun_sz[temp_l++];
}
while(temp_j<=right_bj){
fun_temp[temp_k++] = fun_sz[temp_j++];
}
for(int i=left_bj;i<=right_bj;i++) fun_sz[i] = fun_temp[i];
}
//引用此函数(推荐)
//left:左边界 right:右边界 mer[]:数组名称(无需"[]")
void merge_s(int left,int right,int mer[],string mode){
fun(left,right,mer);
if(mode=="cover"){
for(int i=left;i<=right;i++) mer[i] = fun_temp[i];
}
else if(mode!="staging"){
cout<<"no mode:merge_s";
return;
}
}
高精度计算
高精度输入
//高精度输入: C++17 Code
//日期: 2024/4/13
//高精度输入(输入数字[控制台] | 输出数组)
//函数返回位数
const int MAX_INT=10005;
int hp_input(int a[]){
char b[MAX_INT];
cin>>b;
int i=0;
while(b[i]>='0' && b[i]<='9'){a[i]=b[i]-'0';i++;}
return strlen(b);
}
高精度乘法
//高精度乘: C++17 Code
//日期: 2024/4/13
//额外引用"高精度输入"(hp_input)
//高精度乘法(输入a[],b[],a_len,b_len | 输出out[])
//函数返回位数
int hp_multiplication(int a[],int b[],int a_len,int b_len,int out[]){
int t_a[MAX_INT],t_b[MAX_INT],t_out[MAX_INT],len=a_len+b_len,t_s=0;
for(int i=0;i<a_len;i++) t_a[a_len-i-1] = a[i];
for(int i=0;i<b_len;i++) t_b[b_len-i-1] = b[i];
for(int i=0;i<a_len;i++) for(int j=0;j<b_len;j++) t_out[i+j] += t_a[i] * t_b[j];
for(int i=0;i<len;i++){t_out[i+1] += t_out[i]/10;t_out[i]%=10;}
if(t_out[len-1]==0 && len>1) len--;
for(int i=len-1;i>=0;i--){out[t_s] = t_out[i]; t_s++;}
return len;
}
//-------------------------------------------------------------------------------------
//实例(A*B Problem): C++17 Code
int main(){
int a[MAX_INT],b[MAX_INT],out[MAX_INT];
int alen = hp_input(a);
int blen = hp_input(b);
int f = hp_multiplication(a,b,alen,blen,out);
for(int i=0;i<f;i++){
cout<<out[i];
}
return 0;
}
高精度除法
//高精度除法(高精度除以低精度): C++17 Code
//日期: 2024/4/13
//额外引用"高精度输入"(hp_input)
//高精度除法(输入a[],b,a_len, | 输出out[])
//函数返回位数
int hp_division(int a[],long long int b,int a_len,int out[]){
int t_out[MAX_INT],a_t[MAX_INT],temp=0,s=0;
long long x=0;
for(int i=0;i<a_len;i++){
a_t[i] = a[i];
}
for(int i=0;i<a_len;i++){
t_out[i] = (a_t[i]+x*10) / b;
x = (a_t[i] + x*10) % b;
}
while(t_out[temp]==0) temp++;
for(int i=temp;i<a_len;i++){
out[s] = t_out[i];
s++;
}
return s;
}
//-------------------------------------------------------------------------------------
//实例(小学除法): C++17 Code
int main(){
int a[MAX_INT],out[MAX_INT];
long long b;
int alen = hp_input(a);
cin>>b;
int num = hp_division(a,b,alen,out);
for(int i=0;i<num;i++){
cout<<out[i];
}
return 0;
}
广度优先搜索模板
//广度优先搜索模板
//实例: 希蒙的上学之路2
//日期: 2024/6/8
//----------------------
//维护格子信息
struct Node{
int x,y,step;
};
//标记数组
bool vis[505][505];//(根据题目修改)
//位移数组
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
// x,y地图长宽 map[a][b](a,b根据题目修改) return输出(所需最短步数)
int bfs(int x,int y,char mp[505][505]){
//st开始点 fi结束点 wa墙 (根据题目修改)
char st='S',fi='T',wa='X';
int st_x=0,st_y=0,fi_x=0,fi_y=0;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
if(mp[i][j] == st){st_x = i; st_y = j; }
if(mp[i][j] == fi){fi_x = i; fi_y = j; }
}
}
queue<Node> q;
Node t={st_x,st_y,1};//第三位的 0 因题目而变
q.push(t);
vis[st_x][st_y] = 1;
while(!q.empty()){
t=q.front();
q.pop();
if(t.x == fi_x && t.y == fi_y){
return t.step;
}
for(int i=0;i<4;i++){
int xx = t.x + dx[i];
int yy = t.y + dy[i];
if(mp[xx][yy]!=wa && xx<=x && xx>=1 && yy>=1 && yy<=y && vis[xx][yy]!=1){
q.push({xx,yy,t.step+1});
vis[xx][yy] = 1;
}
}
}
return -1;
}
//main主函数
int main(){
int n,m;
cin>>n>>m;
char ma[505][505];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ma[i][j];
}
}
cout<<bfs(n,m,ma);
return 0;
}
//----------------------
深度优先搜索模板
崩溃了 不写了 C~!
5 条评论
-
chengjunran LV 6 @ 2024-7-10 19:23:10指母哥倒过来（doge
-
@ 2024-6-28 18:04:58666
-
@ 2024-6-8 17:27:20
66666666666666666666666666666
😄 4🤡 3 -
@ 2024-5-18 15:31:18
666
🤡 2🕊️ 2 -
@ 2024-4-27 17:22:58
666
🤡 2🤣 2👎 2😕 2
- 1
