备忘录（供我自用）
2026-07-13 17:42:37
发布于：广东
30阅读
0回复
0点赞
框架
#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<<" ";
}
}
二分查找
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);
二分答案
int er(int l,int r,int x){
int ans=n+1;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]>=x){
ans=mid;
r=mid-1;
}
else l=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});
}
}
}
//图上最短路
忘了等我之后翻出来改
图上最短路
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});
}
}
}
}
}
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);
}
}
}
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]);
}
}
}
}
这里空空如也
有帮助，赞一个