全平台肘击桑境阳，支持者复制红字挂主页 全平台肘击桑境阳，支持者复制红字挂主页 全平台肘击桑境阳，支持者复制红字挂主页 洛谷账号：chengyuhan13579

快速排序

#include<bits/stdc++.h>
using namespace std;
vector<long long> v;
int i,j,temp;
void quicksort(int l,int r){
    if(l>r){
        return;
    }
    temp=v[l];
    i=l;
    j=r;
    while(i!=j){
        while(v[j]>=temp&&i<j){
            j--;
        }
        while(v[i]<=temp&&i<j){
            i++;
        }
        if(i!=j){
            swap(v[i],v[j]);
        }
    }
    swap(v[l],v[j]);
    quicksort(l,j-1);
    quicksort(i+1,r);
}
int main(){
    int n,x,cnt;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        v.push_back(x);
    }
    quicksort(0,n-1);
    for(int i=0;i<n;i++){
        cout<<v[i]<<' ';
    }
    return 0;
}

归并排序

#include<bits/stdc++.h>
using namespace std;
vector<int> s1,s2;
void marge(int l,int m,int r){
     s2.clear();
     int i=l,j=m+1;
     while(i<=m&&j<=r){
         if(s1[i]<s1[j]){
            s2.push_back(s1[i++]);
         }else{
            s2.push_back(s1[j++]);
         }
     }
     while(i<=m){
         s2.push_back(s1[i++]);
     }
     while(j<=r){
         s2.push_back(s1[j++]);
     }
     for(i=l;i<=r;i++){
        s1[i]=s2[i-l];
     }
}
void margesort(int a,int b){
     if(a==b){
       return;
     }
     int m=(a+b)/2;
     margesort(a,m);
     margesort(m+1,b);
     marge(a,m,b);
}
int main(){
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
       cin>>x;
       s1.push_back(x);
    }
    margesort(0,n-1);
    for(int i=0;i<n;i++){
       cout<<s1[i];
    }
    return 0;
}

选择排序

#include<bits/stdc++.h>
using namespace std;
void fun(int a[],int n){
     for(int i=0;i<n;i++){
        int minn=i;
        for(int j=i+1;j<n;j++){
          if(a[j]<a[minn]){
            minn=j;
          }
        }
     swap(a[i],a[minn]);
     }
}
int main(){
    int n,a[305];
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>a[i];
    } 
    fun(a,n);
    for(int i=0;i<n;i++){
      cout<<a[i];
    }
    return 0;
}

插入排序

#include<bits/stdc++.h>
using namespace std;
void insertsort(int a[],int n){
     int x;
     for(int i=1;i<n;i++){
        x=a[i];
        int j=0;
        for(j=i-1;j>=0;j--){
           if(a[j]>x){
             a[j+1]=a[j];
           }else{
             a[j+1]=x;
           }
        }
        if(j<0){
          a[0]=x;
        }
    }
}
int main(){
   int n,v[1005];
   cin>>n;
   for(int i=0;i<n;i++){
      cin>>v[i];
   }
   insertsort(v,n);
   for(int i=0;i<n;i++){
      cout<<v[i];
   }
   return 0;
}

二分查找

#include<bits/stdc++.h>
using namespace std;
int n,x,h;
vector<int> a;
int fun(){
    int l=1,r=n,v;
    while(l<r){
        v=(l+r)/2;
        if(a[v]>=x){
            r=v;
        }else{
            l=v+1;
        }
    }
    if(x==a[l]){
        return l;
    }else{
        return -1;
    }
}
int main(){
   cin>>n;
   for(int i=1;i<=n;i++){
      scanf("%d",&h);
      a.push_back(h);
   }
   cin>>x;
   printf("%d",fun()+1);
}

堆排序

#include<bits/stdc++.h>
using namespace std;
const int N=1e+6;
int n,a[N];
void heapify(int n,int i){
    int largest=i,lson=2*i,rson=2*i+1;
    if(a[largest]<a[lson]&&lson<=n){
        largest=lson;
    }
    if(a[largest]<a[rson]&&rson<=n){
        largest=rson;
    }
    if(a[i]!=a[largest]){
        swap(a[i],a[largest]);
        heapify(n,largest);
    }
}
void heapsort(){
    for(int i=n/2;i>=1;i--){
        heapify(n,i);
    }
    for(int i=n;i>1;i--){
        swap(a[1],a[i]);
        heapify(i-1,1);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    heapsort();
    for(int i=1;i<=n;i++){
        cout<<a[i];
    }
}

以大根堆为例： 1、首先先找到最后一个非叶子结点，假设n个元素。 那么⌊n/2」 2、把完全二叉树自底向上修改成大根堆的形式，每修改一个数据，数组里面对应的数据需要随之变化。 3、当变成大根堆的时候，祖宗结点(a[1])一定是最大的，那么只需要和a[n]交换。总共有n个数，那么只需要n-1次就可以排完

基数排序

#include<bits/stdc++.h>
using namespace std;
const int N=1e+5;
int a[N],t[N];
int buchet[10];
void redixSort(int n){
    int max_val=*(max_element(a,a+n));
    int base=1;
    while(max_val/base>0){
        memset(buchet,0,sizeof(buchet));
        for(int i=0;i<n;i++){
            buchet[a[i]/base%10]++;
        }
        for(int i=1;i<10;i++){
            buchet[i]=buchet[i]+buchet[i-1];
        }
        for(int i=n-1;i>=0;i--){
            int v=a[i]/base%10;
            t[--buchet[v]]=a[i];
        }
        for(int i=0;i<n;i++){
            a[i]=t[i];
        }
        base*=10;
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",a+i);
    }
    redixSort(n);
    for(int i=0;i<n;i++){
        printf("%d",a[i]);
    }
    return 0;
}

高精度减法

#include<bits/stdc++.h>
using namespace std;
const int N=1e+6;
string a1,b1;
bool flag=false;
int a[N],b[N],c[N];
bool panduan(string s1,string s2){
    if(s1.size()!=s2.size()) return s1.size()<s2.size();
    else return s1<s2;
}
int main(){
    cin>>a1>>b1;
    if(panduan(a1,b1)){
        cout<<'-';
        swap(a1,b1);
    }
    for(int i=a1.size()-1,j=0;i>=0;i--,j++){
        a[j]=a1[i]-'0';
    }
    for(int i=b1.size()-1,j=0;i>=0;i--,j++){
        b[j]=b1[i]-'0';
    }
    int len=max(a1.size(),b1.size());
    for(int i=0;i<len;i++){
        c[i]+=a[i]-b[i];
        if(c[i]<0){
            c[i]+=10;
            c[i+1]--;
        }
    }
    for(int i=len-1;i>=0;i--){
        if(c[i]!=0){
            flag=true;
        }
        if(flag){
            cout<<c[i];
        }
    }
    if(flag==false){
        cout<<0;
    }
    return 0;
}

高精度加法

#include<bits/stdc++.h>
using namespace std;
int main(){
    string a1,b1;
    bool flag=0;
    int a[1000]={0},b[1000]{0},c[1000]={0};
    cin>>a1>>b1;
    for(int i=a1.size()-1,j=0;i>=0;i--,j++){
        a[j]=a1[i]-'0';
    }
    for(int i=b1.size()-1,j=0;i>=0;i--,j++){
        b[j]=b1[i]-'0';
    }
    for(int i=0;i<a1.size()||i<b1.size();i++){
        c[i]=a[i]+b[i];
    }
    for(int i=0;i<a1.size()||i<b1.size();i++){
        if(c[i]>=10){
            c[i]-=10;
            c[i+1]++;
        }
    }
    for(int i=max(a1.size()+1,b1.size()+1);i>=0;i--){
        if(c[i]!=0){
            flag=1;
        }
        if(flag){
            cout<<c[i];
        }
    }
}

哈希算法

#include<bits/stdc++.h>
using namespace std;
const int N=1e+5;
int hash1[N],HMAX,cnt[N],b[N];
void hashinit(int x){
    for(int i=1;i<=x;i++){
        hash1[i]=-1;
    }
}
void hashinsert(int x){
    int y=x%HMAX;
    while(1){
        if(hash1[y]==-1){
            hash1[y]=x;
            cnt[y]=1;
            return;
        }else if(hash1[y]==x){
            cnt[y]++;
            return;
        }
        if(++y>HMAX){
            y=1;
        }
    }
}
int hashget(int x){
    int y=x%HMAX;
    while(1){
        if(hash1[y]==-1){
            return 0;
        }else if(hash1[y]==x){
            return cnt[y];
        }
        if(++y>HMAX){
            y=1;
        }
    }
}
int main(){
    int x;
    cin>>HMAX;
    hashinit(HMAX);
    for(int i=1;i<=HMAX;i++){
        cin>>x;
        hashinsert(x);
    }
    //根据题目变化
    return 0;
}

Dijkstra朴素算法

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100;
int graph[MAXN][MAXN];
void initEdegs(int n){
    for(int u=0;u<n;u++){
        for(int v=0;v<n;v++){
            graph[u][v]=INT_MAX;
        }
    }
}
void addEdge(int u,int v,int w){
    graph[u][v]=min(graph[u][v],w);
}
void DijkstraInit(int n,int s,bool visited[],int dist[]){
    for(int i=0;i<n;i++){
        visited[i]=false;
        dist[i]=INT_MAX;
    }
    dist[s]=0;
}
int DijkstraFindMin(int n,bool visited[],int dist[]){
    int u=-1;
    for(int i=0;i<n;i++){
        if(visited[i]) continue;
        if(u==-1||dist[i]<dist[u]){
            u=i;
        }
    }
    return u;
}
void DijkstraUpdate(int n,int u,bool visited[],int dist[]){
    visited[u]=true;
    for(int i=0;i<n;i++){
        if(visited[i]) continue;
        if(graph[u][i]!=INT_MAX){
            dist[i]=min(dist[i],dist[u]+graph[u][i]);
        }
    }
}
void Dijkstra(int n,int s,int dist[]){
    bool visited[MAXN];
    DijkstraInit(n,s,visited,dist);
    while(true){
        int u=DijkstraFindMin(n,visited,dist);
        if(u==-1) return;
        DijkstraUpdate(n,u,visited,dist);
    }
}
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    initEdegs(n);
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        addEdge(u,v,w);
    }
    int dist[MAXN];
    Dijkstra(n,s,dist);
    for(int i=0;i<n;i++){
        if(dist[i]==INT_MAX){
            cout<<"INF ";
        }else{
            cout<<dist[i]<<" ";
        }
    }
    cout<<endl;
    return 0;
}

希尔排序

#include <bits/stdc++.h>
using namespace std;
const long long N=1e+5;
int a[N];
void shell_sort(int n){
    int gap=n/2;
    while(gap>0){
        for(int i=gap;i<n;i++){
            int temp=a[i];
            int j=i;
            while(j>=gap&&temp<a[j-gap]){
                a[j]=a[j-gap];
                j-=gap;
            }
            a[j]=temp;
        }
        gap/=2;
    }
}
int main(){
    int n;
    cin>>n;
    for (int i = 0; i < n; i++){
        cin>>a[i];
    }
    shell_sort(n);
    for (int i=0;i<n;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

手写栈

#include<bits/stdc++.h>
using namespace std;
unsigned long long s[1000005],t;
void init(){
    t=0;
}
void push(unsigned long long x){
    s[++t]=x;
}
void pop(){
    if(t==0){
        puts("Empty");
    }else{
        t--;
    }
}
void query(){
    if(t==0){
        puts("Anguei!");
    }else{
        cout<<s[t]<<endl;
    }
}
int size(){
    return t;
}
int main(){
    
}

手写队列

#include<bits/stdc++.h>
using namespace std;
const int N=114514;
struct CircularQueue{
    int data[N],head=0,tail=0;
    int size(){
        return tail-head+1;
    }
    bool empty(){
        return tail==head;
    }
    int front(){
        return data[head%N];
    }
    int back(){
        return data[tail%N];
    }
    void push(int x){
        if((tail+1)%N!=head%N){
            data[tail++%N]=x;
        }
    }
    void pop(){
        if(!empty()){
          head++;
    }
    
};
int main(){
     
}

单调队列

#include<bits/stdc++.h>
using namespace std;
long long int a[1000005];
int n,k;
deque<int> d,x; 
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    for(int i=1;i<=n;i++){
        if(!x.empty()&&i-x.front()==k){
            x.pop_front();
        }
        while(!x.empty()&&a[x.back()]>a[i]){
            x.pop_back();
        }
        x.push_back(i);
        if(i>=k){
            printf("%lld ",a[x.front()]);
        }
    }
    printf("\n");
    for(int i=1;i<=n;i++){
        if(!d.empty()&&i-d.front()==k){
            d.pop_front();
        }
        while(!d.empty()&&a[d.back()]<a[i]){
            d.pop_back();
        }
        d.push_back(i);
        if(i>=k){
            printf("%lld ",a[d.front()]);
        }
    }
    return 0;
}

广搜模板

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e7;
int graph[MAX][MAX];
bool visited[MAX];
int v,e;
void BFS(int bg){
    queue<int> q;
    q.push(bg);
    visited[bg]=1;
    while (!q.empty()){
        int n=q.front();
        q.pop();
        cout<<n<<' ';
        for (int m=0;m<v;m++){
            if (graph[n][m]==1&&!visited[m]){
                q.push(m);
                visited[m]=1;
            }
        }
    }
}

int main(){
    cin>>v>>e;
    int n,m;
    for(int i=0;i<v;i++){
        visited[i]=0;
        for(int j=0;j<v;j++){
            graph[i][j]=0;
        }
    }
    for(int i = 0; i < e; ++i){
        cin>>n>>m;
        graph[n][m]=1;
        graph[m][n]=1;
    }
    int bg;
    cin>>bg;
    BFS(bg);
    return 0;
}

深搜模板

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
bool visit[N];
void dfs(int root,int n){
	if(root==n){
		//找到一种结果，统计个数或输出路径
		return;
	}
	for(int i=root;i<n;i++){
		if(!visit[i]){//检查i是否用过
			visit[i]=1;//将i标记为用过
			dfs(root+1,n);
			visit[i]=0;//回溯，搜索过i后i就可以用了
		}
	}
}
int main(){
	//根据题目来写
	return 0;
}

快读

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main(){
long long m,n,s2;
bitset<1000000000> s;
    bool flag;
    m=read();
    n=read();
    for(int i=0;i<m;i++){
        s[read()]=1;
    }
}

01背包

#include <bits/stdc++.h>
using namespace std;
const int BAG = 105;
int dp[BAG][BAG];
int weight[BAG];
int value[BAG];
int main () {
    int n,bagweight;
    cin >> n >> bagweight;
    for(int i = 0;i < n;++i)
    {
        cin >> weight[i] >> value[i];
    }
    for(int j = weight[0];j <= bagweight;++j)
    {
        dp[0][j] = value[0];
    }
    for(int i = 1;i < n;++i)
    {
        for(int j = 1;j <= bagweight;++j)
        {
            if(j < weight[i])
            {
                dp[i][j] = dp[i - 1][j];
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
    for(int i = 0;i < n;++i)
    {
        for(int j = 0;j <= bagweight;++j)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}