备忘录（供我自用）
2026-08-17 18:25:46
发布于：广东
60阅读
0回复
0点赞
纯模板，望以后忘c++的我可以理解这份备忘录
框架
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
return 0;
}
排序
void mp(){
for(ll i=1;i<=n-1;i++){
if(a[i]>a[i+1]) swap(a[i+1],a[i]);
}
}
void xp(){
for(ll i=1;i<=n-1;i++){
ll k=i;
for(ll j=i+1;j<=n;j++){
if(a[j]<a[k]) k=j;
}
swap(a[i],a[k]);
}
}
void cp(){
for(ll i=2;i<=n;i++){
ll x=a[i];
ll j=i-1;
while(j>=1&&a[j]>x) a[j+1]=a[j],j--;
a[j+1]=x;
}
}
void tp(){
ll cnt=0;
for(ll i=1;i<=1000;i++){
if(a[i]!=0) cnt++;
}
cout<<cnt<<endl;
for(ll i=1;i<=1000;i++){
if(a[i]!=0) cout<<i<<" ";
}
}
void mg(ll l,ll r){//归并排序
if(l>=r) return ;
ll mid=l+r>>1;
mg(l,mid);
mg(mid+1,r);
ll i=l,j=mid+1,cnt=0;
while(i<=mid&&j<=r){
if(a[i]<=a[j]) b[++cnt]=a[i++];
else b[++cnt]=a[j++];
}
while(i<=mid) b[++cnt]=a[i++];
while(j<=r) b[++cnt]=a[j++];
for(ll i=1;i<=cnt;i++) a[l+i-1]=b[i];
}
void ks(ll l,ll r){//快速排序
if(l>=r) return ;
ll p=l+rand()%(r-l+1);
swap(a[l],a[p]);
ll i=l,j=r,k=a[l];
while(i<j){
while(i<j&&a[j]>=k) j--;
a[i]=a[j];
while(i<j&&a[i]<=k) i++;
a[j]=a[i];
}
a[i]=k;
ks(l,i-1);
ks(i+1,r);
}
二分查找
int a[N];
int er(int l,int r,int x){
while(l<=r){
int mid=(l+r)/2;
if(a[mid]==x) return mid;
else if(a[mid]>x) r=mid-1;
else l=mid+1;
}
return -1;
}
调用：er(1,n,t);
二分答案
ll er(ll l,ll r){
ll ans=0;
while(l<=r){
ll mid=l+r>>1;
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
return ans;
}
前缀和
int a[N],pre[N];
int n;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
int l,r;
cin>>l>>r;
cout<<pre[r]-pre[l-1]<<endl;
深搜
暴力dfs（枚举类，容易理解最好骗分）
模板
void dfs(ll x){
if(x==n+1){
check();
return ;
}
vis[i]=0;
dfs(x+1);
vis[i]=1;
dfs(x+1);
}
//全排列
void dfs(ll x){
if(x==n+1){
for(ll i=1;i<=n;i++) printf("%5d",ans[i]);
cout<<"\n";
return ;
}
for(ll i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
ans[x]=i;
dfs(x+1);
vis[i]=0;
}
}
}
图上连通块
ll n,m,cnt;
bool a[N][N],vis[N];
void dfs(ll x){
for(ll i=1;i<=n;i++){
if(!vis[i]&&a[x][i]){
vis[i]=true;
dfs(i);
}
}
}
int main(){
cin>>n>>m;
for(ll i=1;i<=m;i++){
ll u,v;cin>>u>>v;
a[u][v]=a[v][u]=true;
}
for(ll i=1;i<=n;i++){
if(!vis[i]){
cnt++;
vis[i]=true;
dfs(i);
}
}
cout<<cnt;
return 0;
}
广搜（我爹）
why呢？因为我在做深搜广搜结合时全用广搜骗出四道题的分，比我做出深搜还高[捂脸笑]
//迷宫
char a[10][10];
bool vis[10][10];
ll d[4][2]={0,1,1,0,0,-1,-1,0};
struct node{ll x,y,step;};
void bfs(){
queue<node> q;
q.push({1,1,0});
vis[1][1]=1;
while(!q.empty()){
node h=q.front();
q.pop();
if(h.x==5&&h.y==5){
cout<<h.step;
return ;
}
for(ll i=0;i<4;i++){
ll tx=h.x+d[i][0];
ll ty=h.y+d[i][1];
ll ts=h.step+1;
if(tx>=1&&tx<=5&&ty>=1&&ty<=5&&a[tx][ty]=='0'&&vis[tx][ty]==0){
vis[tx][ty]=1;
q.push({tx,ty,ts});
}
}
}
cout<<-1;
}
//连通块
ll n,m,vis[N][N],ans;
char a[N][N];
ll d[8][2]={0,1,1,0,0,-1,-1,0,1,-1,-1,1,1,1,-1,-1};
struct node{ll x,y;};
void bfs(ll x,ll y){
queue<node> q;
vis[x][y]=1;
q.push({x,y});
while(!q.empty()){
node h=q.front();
q.pop();
for(ll i=0;i<8;i++){
ll tx=h.x+d[i][0],ty=h.y+d[i][1];
if(tx<=n&&tx>=1&&ty<=m&&ty>=1&&!vis[tx][ty]&&a[tx][ty]=='连通字符'){
vis[tx][ty]=1;
q.push({tx,ty});
}
}
}
return ;
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
if(!vis[i][j]&&a[i][j]=='连通字符'){
ans++;
bfs(i,j);
}
}
}
//最短路径
ll n,m,ans,vis[N];
struct node{
ll x,step;
};
void bfs(){
queue<node> q;
q.push({n,0});
vis[n]=1;
while(!q.empty()){
node h=q.front();
q.pop();
if(h.x==m){
ans=h.step;
return ;
}
ll k=h.x*2;//传送门方式
if(k<=N&&!vis[k]){
vis[k]=1;
q.push({k,h.step+1});
}
k=h.x+1;//一步方式
if(k<=N&&!vis[k]){
vis[k]=1;
q.push({k,h.step+1});
}
k=h.x-1;//退一步方式
if(k>=1&&!vis[k]){
vis[k]=1;
q.push({k,h.step+1});
}
//上述方式可替换，公式如下
k=h.x;//替换数值
if(k设置边界&&!vis[k]){
vis[k]=1;
q.push({k,h.step+1});
}
}
}
//01bfs
void bfs(){
deque<node> q;
q.push_back({sx,sy});
dst[sx][sy]=0;
while(!q.empty()){
node h=q.front();
q.pop_front();
for(ll i=0;i<4;i++){
ll tx=h.x+d[i][0],ty=h.y+d[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
if(选择1){
if(dst[tx][ty]>dst[h.x][h.y]+1){
dst[tx][ty]=dst[h.x][h.y]+1;
q.push_back({tx,ty});
}
}else{//选择2
if(dst[tx][ty]>dst[h.x][h.y]){
dst[tx][ty]=dst[h.x][h.y];
q.push_front({tx,ty});
}
}
}
}
}
}
//图上最短路
void bfs(){
deque<ll> q;
q.push_back(1);
dst[1]=0;
while(!q.empty()){
ll h=q.front();
q.pop_front();
for(ll i=0;i<ve[h].size();i++){
ll k=ve[h][i];
if(dst[k]>dst[h]+1){
dst[k]=dst[h]+1;
q.push(k);
}
}
}
}
图上最短路
Dijkstra 注：Dijkstra贪心思想，找最小点
void dij(ll n,ll s){
for(ll i=0;i<=n;i++) dis[i]=1e9;
dis[s]=0;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;
q.push({dis[s],s});
while(!q.empty()){
ll u=q.top().second;
q.pop();
if(!vis[u]){
vis[u]=1;
for(ll j=0;j<g[u].size();j++){
ll v=g[u][j].v,w=g[u][j].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
}
或
struct node{ll x,y;};
struct Node{
ll x,dst;
bool operator<(const Node&other) const{
return dst>other.dst;
}
};
vector<node> ve[N];
void dij(){
priority_queue<Node> q;
q.push({s,0});
dst[s]=0;
while(!q.empty()){
Node h=q.top();q.pop();
if(vis[h.x]) continue;
vis[h.x]=true;
for(ll i=0;i<ve[h.x].size();i++){
ll k=ve[h.x][i].x;
if(dst[k]>dst[h.x]+ve[h.x][i].y){
dst[k]=dst[h.x]+ve[h.x][i].y;
q.push({k,dst[k]});
}
}
}
}
时间复杂度：mlogn
Bellman-Ford（暴力的Dijkstra，容易理解，但会被坑）
//未优化
struct node{ll y,z;};
vector<node> v[N];
void bmf(){
for(ll i=1;i<=n;i++) dis[i]=1e9;
dis[s]=0;
for(ll i=1;i<N;i++){
for(ll j=0;j<v[i].size();j++){
ll y=v[i][j].y,z=v[i][j].z;
if(dis[y]>dis[i]+z) dis[y]=dis[i]+z;
}
}
}
//优化后（SPFA）（似了[捂脸笑]
void bmf(){
for(ll i=1;i<=n;i++) dis[i]=1e9;
dis[s]=0,vis[s]=1;
queue<ll> q;
q.push(s);
while(!q.empty()){
ll h=q.front();q.pop();vis[h]=0;
for(ll j=0;j<v[h].size();j++){
ll x=h,y=v[h][j].y,z=v[h][j].z;
if(!vis[x]&&dis[y]>dis[x]+z) dis[y]=dis[x]+z,q.push(y);
}
}
}
时间复杂度：nm
Floyd
void fld(){//直接输入dis数组，dis在开始就初始化了
for(ll k=1;k<=n;k++){
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
STL容器
//栈
stack<ll> s;
//队列
queue<ll> q;
//优先队列(堆)
priority_queue<ll(存的类型),一个实现优先队列的容器，如vector<ll>,greater<ll>(从小到大)/less<ll>(从大到小)> q;
//排序的
set<ll> s;
//映射(字典)
map<ll,ll> m;
//结构体的变种
pair<ll,ll> p;(不如结构体，拉完了）
重载运算符
struct node{
string xh;
ll n;
bool operator<(const node & b)const{
return n<b.n;(从小到大)
bool operator<(const node & b)const{
return n>b.n;(从大到小)
};
这里空空如也
有帮助，赞一个