以前一直没有总结的习惯。

快速幂

//a的b次方
int qsmi(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans*=a //b--可写可不写
        b>>=1;
        a*=a;

    }
    return ans;
}

欧几里得

int gcd(int a, int b)
{
    return b?(b,a%b):a;
}
int gcd(int a ,int b)
{
    int temp;
    while(b)
    {
        temp=a%b;
        a=b;
        b=temp
    }
    return a;
}

子矩阵前缀和

生成前缀和矩阵
a[i]为原矩阵，s[i]为子矩阵

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&a[i][j]);
        s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
    }

求任意子矩阵的和
(x1,y1)为子矩阵左上角坐标，(x2,y2)为子矩阵右下角坐标

    ans=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]

素数

试除法判断一个数是否为素数

bool isprime(int a)
{
    if(a<2)return false;
    for(int i=2;i<=a/i;i++)
    {
        if(a%i==0)return false;
    }
    return true;

}

埃氏筛法 筛选1~n之间的素数(欧拉筛不好记)，实际上时间差不了超级多

bool isprime[N];//是否为素数
void sieve(){
     //我们初始化都标记为素数。再筛不是素数的
    for(int i=0;i<=maxn;i++)isprime[i]=true;

    isprime[0]=isprime[1]=false;//1,0不是素数
    for(int i=2;i<=maxn;i++){//从2开始往后筛，因为2是目前最小的素数，那么素数的倍速一定不是素数
        if(isprime[i]){
            for(int j=i+i;j<=maxn;j+=i){
                isprime[j]=false;
            }
        }
    }
}

整数二分模板

男左女右，所以左边要＋1，而有加必有减

//查找左边界 SearchLeft 简写SL  查找满足条件的最小那个数
int SL(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid; 
        else l = mid + 1; 
    }   
    return l;
}
//查找右边界 SearchRight 简写SR 查找满足条件最大的那个数
int SR(int l, int r) 
{
    while (l < r)
    {                   
        int mid = l + r + 1 >> 1; //
        if (check(mid)) l = mid; //男左，上边需要加1
        else r = mid - 1;  //有加必有减
    }
    return r; 
}

floyd算法求带权图的最短路

#include <iostream>
using namespace std;

const int N = 210, M = 2e+10, INF = 1e9;

int n, m, k, x, y, z;
int d[N][N];

void floyd() {
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;

    while(m--) {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);//x到y的权重
        //注意保存最小的边
    }
    floyd();
    while(k--) {
        cin >> x >> y;
        if(d[x][y] > INF/2) puts("impossible");
        //由于有负权边存在所以约大过INF/2也很合理
        else cout << d[x][y] << endl;
    }
    return 0;
}

unique函数用法

直接去重

 int a[6] = {1, 3, 3, 3, 2, 7};

    unique(a, a + 6);
    // cout << m;
    for (int x : a)
        cout << x << " ";

输出

1 3 2 7 2 7

输出去重后数组的元素数量

    int a[8] = {1, 3, 3, 3, 3, 2, 5, 7};

    int m = unique(a, a + 8) - a;
    cout << m;

输出

5

next_permutation(a,a+n) 下一个全排列、以及prev_permutation(a,a+n);

string.find()

找到字串的下标，第二个参数是从哪里开始找

string a="abcdabacde";
    string f="ab";
    int index=a.find(f);

    while(index!=-1)
    {
        cout<<index<<" ";
        index=a.find(f,index+1);

    }

输出

0 4

rfind也是同理

stoi() 字符串转int

string s = "1234";
int a = stoi(s);
cout << a << "\n"; // 1234

to_string() int或者double 转字符串