c++竞赛中常见的算法模板汇总

排序

桶排序

简化版桶排序,准备一个较大数组作为用于存放数据的桶,当读入某个值比如9时,让9号桶(b[9])+1,遍历完所有值后,回过头看b数组中的值,如果值为1的,就输出该位置的下标一次,如果值为2的,就输出该位置的下标为2,这是一种以空间换时间的做法,当需要排序的值差值较大且比较稀疏,就会浪费较多的空间.桶排序输出的并不是我们存入的值,而是数组的下标.

#include <iostream>
#include <iomanip>
using namespace std;

int main(){
    int a[11],b[11];
    for(int i=0;i<=10;i++){
        a[i]=b[i]=0;
    }
    for(int i=0;i<=6;i++){
        cin >> a[i];
    }
    for(int i=0;i<=6;i++){
        b[a[i]]++;
    }
    for(int i=0;i<=10;i++){
        for(int j=0;j<b[i];j++){
            cout << i << " ";
        }
    }
}

冒泡排序

顺序比较：

#include <iostream>
using namespace std;
int main() {
    int length,a[] = {5,4,3,2,1,10,9,8,7,6};
    length = sizeof(a)/sizeof(int);
    //n个数字，循环n-1次
    for(int i=0;i<length-1;i++){
        //且每次循环比较的数字可以减少1位
        //因为每轮循环会确定一个数字的位置  
        for(int j=0;j<length-1-i;j++){
            if(a[j]<a[j+1]){
                swap(a[j],a[j+1]);
            }

        }
    }
    for (int i=0;i<length;i++)cout << a[i] << " ";
}

逆序比较：

#include <iostream>
using namespace std;

int main() {
    int length,a[] = {5,4,3,2,1,10,9,8,7,6};
    length = sizeof(a)/sizeof(int);
    for(int i=0;i<length-1;i++){
        for(int j=length-1;j>i;j--){
            if(a[j]>a[j-1]){
                swap(a[j],a[j-1]);
            }

        }
    }
    for (int i=0;i<length;i++)cout << a[i] << " ";
}

选择排序

#include<iostream>
using namespace std;

void selectSort(int arr[],int length){
    int maxpos;
    for(int i=0;i<length;i++){
        maxpos=i;
        for(int j=i+1;j<length;j++){
            if(arr[maxpos]<arr[j])maxpos=j;
        }
        if(maxpos!=i)swap(arr[maxpos],arr[i]);
    }
}

int main(){
    int a[10];
    for(int i=0;i<10;i++)cin>>a[i];
    selectSort(a,10);
    for(int i=0;i<10;i++)cout << a[i] <<endl;
}

快速排序

#include<iostream>
using namespace std;

int a[10];
void quickSort(int left,int right){
    if(left>right)return;
    int i,j;
    i=left;
    j=right;
    while(i!=j){
        while(a[j]<=a[left]&&i<j)j--;
        while(a[i]>=a[left]&&i<j)i++;
        if(i<j)swap(a[i],a[j]);
    }
    swap(a[i],a[left]);
    quickSort(left,i-1);
    quickSort(i+1,right);
    return;
}

int main(){
    for(int i=0;i<10;i++)cin >> a[i];
    quickSort(0,9);
    for(int i=0;i<10;i++)cout << a[i] << " ";
}

模拟

队列模拟

#include<iostream>
#include<queue>
using namespace std;

struct myQueue{
    int data[201];
    int head;
    int tail;
};

int main(){
    myQueue a;
    a.head=0;
    a.tail=0;
    for(int i=0;i<9;i++){
        cin >> a.data[i];
        a.tail++;
    }
    while(a.head<a.tail){
        cout << a.data[a.head] << " ";
        a.head++;
        a.data[a.tail]=a.data[a.head];
        a.tail++;
        a.head++;
    }
}

其他

进制判断

洛谷B3868的题，判断进制较为简洁，摘录如下：

#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int n;
    string s;
    bool a[1000],b[1000],c[1000],d[1000];
    for(int i=0;i<1000;i++)a[i]=b[i]=c[i]=d[i]=1;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> s;
        for (int j = 0; j < s.length(); j++){
            if (s[j] > '1') a[i] = 0;
            if (s[j] > '7') b[i] = 0;
            if (s[j] > '9') c[i] = 0;
            if (s[j] > 'F') d[i] = 0;
        }
    }
    for(int i=0;i<n;i++){
        cout << a[i] << ' ' << b[i] << ' ' << c[i] << ' ' << d[i] << endl;
    }
}