算法入门（新手-不喜勿喷）
2026-07-22 19:56:55
发布于：四川
加快输出
只有C++14(GCC 9)及以上才能用
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}
头文件如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
return 0;
}
找头,找末
int findfirst(int l,int r,int x){
int mid=(l+r)/2;
if(l==r) return l;
if(arr[mid]>=x) r=mid;
else l=mid+1;
return findfirst(l,r,x);
}
int findlast(int l,int r,int x){
int mid=(r+l+1)/2;
if(l==r) return l;
if(arr[mid]<=x) l=mid;
else r=mid-1;
return findlast(l,r,x);
}
一位前缀和
输入
s[i]=s[i-1]+a[i];
输出
s[r]-s[l-1];
二维前缀和
输入
s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
输出
s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
三维前缀和
输入
s[i][j][k] = a[i][j][k]
+ s[i-1][j][k] + s[i][j-1][k] + s[i][j][k-1]
- s[i-1][j-1][k] - s[i-1][j][k-1] - s[i][j-1][k-1]
+ s[i-1][j-1][k-1];
输出
ans = s[x2][y2][z2]
- s[x1-1][y2][z2] - s[x2][y1-1][z2] - s[x2][y2][z1-1]
+ s[x1-1][y1-1][z2] + s[x1-1][y2][z1-1] + s[x2][y1-1][z1-1]
- s[x1-1][y1-1][z1-1];
埃氏筛法
#include <bits/stdc++.h>
using namespace std;
const long long N=1e8;
bool vis[N];
void init(){
vis[0]=vis[1]=1;
int s=0;
int t=sqrt(N);
for(long long i=2;i<=t;i++){
if(!vis[i]){
for(long long j=i*i;j<=N;j+=i){
vis[j]=1;
}
}
}
/*for(int i=1;i<=N;i++){
if(!vis[i]) s++;
}
cout<<s;
*/
}
int main(){
init();
return 0;
}
欧拉筛
#include <bits/stdc++.h>
using namespace std;
const long long N=1e8;
long long arr[N],tot;
bool vis[N];
void init(){
vis[1]=vis[0]=1;
for(long long i=2;i<N;i++){
if(!vis[i]){
arr[tot]=i;tot++;
}
for(long long j=0;j<tot&&arr[j]*i<N;j++){
vis[arr[j]*i]=1;
if(i%arr[j]==0) break;
}
}
//cout<<tot;
}
int main(){
init();
return 0;
}
输出质数
#include <bits/stdc++.h>
using namespace std;
const long long N=1e8;
long long arr[N],tot;
bool vis[N];
void init(){
vis[1]=vis[0]=1;
for(long long i=2;i<N;i++){
if(!vis[i]){
arr[tot]=i;tot++;
}
for(long long j=0;j<tot&&arr[j]*i<N;j++){
vis[arr[j]*i]=1;
if(i%arr[j]==0) break;
}
}
cout<<tot<<endl;
}
int main(){
init();
for(int i=1;i<=N;i++){
cout<<i<<" "<<vis[i]<<endl;
}
return 0;
}
STL
队列
先进先出
queue<类型> 变量名
变量名.front() 得到队首值
变量名.empty() 队列为空，得到true
变量名.pop() 出队
变量名.push() 入队
变量名.size() 队列长度
栈
先进后出
stack<类型> 变量名
变量名.top() 得到栈顶值
变量名.empty() 栈为空，得到true
变量名.pop() 出栈
变量名.push() 入栈
变量名.size() 栈长度
深度优先搜索(dfs)
排列（n个数组合m个+去重）
#include <bits/stdc++.h>
using namespace std;
int n,m,arr[105],vis[105],cnt;
void dfs(int s){
if(s>m){
for(int i=1;i<s;i++){
cout<<arr[i]<<' ';
}
cout<<endl;
cnt++;
return ;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
arr[s]=i;
vis[i]=1;
dfs(s+1);
vis[i]=0;
}
}
}
int main(){
cin>>n>>m;
dfs(1);
cout<<cnt;
return 0;
}
数的计算
深度优先搜索
#include <bits/stdc++.h>
using namespace std;
int n,arr[1005];
void dfs(int s,int k){
for(int i=s-1;i>=1;i--){
cout<<arr[i];
}
cout<<endl;
for(int i=1;i<=k/2;i++){
arr[s]=i;
dfs(s+1,i);
}
}
int main(){
cin>>n;
arr[1]=n;
dfs(2,n);
return 0;
}
8皇后
#include <bits/stdc++.h>
using namespace std;
int cnt,arr[105][105],l[105],x1[105],x2[105];
void dfs(int s){
if(s==9){
if(cnt<=5){
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
if(arr[i][j]==1){
cout<<"★ ";
}else{
cout<<"□ ";
}
}
cout<<endl;
}
cout<<"\n------------\n";
}
cnt++;
return ;
}
for(int i=1;i<=8;i++){
if(!(l[i]||x1[s+i]||x2[s-i+7])){
l[i]=1;
x1[s+i]=1;
x2[s-i+7]=1;
arr[s][i]=1;
dfs(s+1);
l[i]=0;
x1[s+i]=0;
x2[s-i+7]=0;
arr[s][i]=0;
}
}
}
int main(){
dfs(1);
cout<<cnt;
return 0;
}
深度优先搜索(dfs)
组合+深度去重(几个数相加等于n，输出n=几+几)
#include <bits/stdc++.h>
using namespace std;
int n,arr[10005],cnt;
void dfs(int s,int sum){
arr[0]=1;
if(sumn){
if(s2) return ;
cout<<n<<"=";
for(int i=1;i<s-1;i++){
cout<<arr[i]<<'+';
}
cout<<arr[s-1];
cnt++;
cout<<endl;
}else if(sum>n){
return ;
}
for(int i=arr[s-1];i<=n;i++){
arr[s]=i;
dfs(s+1,sum+arr[s]);
}
}
int main(){
cin>>n;
dfs(1,0);
cout<<cnt;
return 0;
}
深度优先搜索(dfs)
迷宫问题输出路线+路线数量
#include <bits/stdc++.h>
using namespace std;
int n,m,arr[105][105],run[][2]={-1, 0,
1, 0,
0,-1,
0, 1};
int cnt;
void dfs(int x,int y){
//cout << x << " " << y << endl;
if(xn&&ym){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(arr[i][j]==2) cout<<"★ ";
else if(arr[i][j]==0) cout<<"■ ";
else cout<<" ";
}
cout<<endl;
}
cout<<"\n------------------\n";
cnt++;
return ;
}
for(int i=0;i<=3;i++){
int tx=x+run[i][0],
ty=y+run[i][1];
if(tx>0&&ty>0&&tx<=n&&ty<=m&&arr[tx][ty]==1){
arr[tx][ty]=2;
dfs(tx,ty);
arr[tx][ty]=1;
}
}
}
int main(){
//迷宫（深度优先搜索）
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>arr[i][j];
}
}
cout<<endl;
arr[1][1]=2;
dfs(1,1);
cout<<cnt;
return 0;
}
洪水填充算法
深度优先搜索
#include <bits/stdc++.h>
using namespace std;
int n,m,ans,run[][2]={-1, 0,
1, 0,
0,-1,
0, 1};
int vis[105][105];
char arr[105][105];
void dfs(int x,int y){
for(int i=0;i<=3;i++){
int tx=x+run[i][0];
int ty=y+run[i][1];
if(tx>0&&ty>0&&tx<=m&&ty<=n&&arr[tx][ty]=='.'&&vis[tx][ty]==0){
ans++;
vis[tx][ty]=1;
dfs(tx,ty);
}
}
}
int main(){
cin>>n>>m;
int n1,m1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>arr[i][j];
if(arr[i][j]=='@'){
n1=i;
m1=j;
}
}
}
dfs(n1,m1);
/*for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cout<<vis[i][j];
}
cout<<endl;
}*/
cout<<ans+1;
return 0;
}
这里空空如也
有帮助，赞一个