基本算法

快速排序

分治思想 双指针运算

一，选取基准（一般是以中间为基准）

二，选取做边界 i 和有边界 j ，不断与所选的基准值进行比较，直到找到比基准值大或小的值，进行二者的交换

三，递归同上处理基准值的左右区间

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int n;
void quick_sort(int q[],int l,int r)
{
    if(l >= r ) return ;
    int i = l - 1  ,j = r + 1 , mid = q[l+r >> 1];
    while(i < j)
    {
        do i ++; while(q[i] < mid );
        do j --; while(q[j] > mid );
        if(i < j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
int main(void)
{
    cin >> n;
    for(int i = 0 ; i < n ; i++) cin >> q[i];
    quick_sort(q,0,n-1);
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
}

归并排序

分治思想 区间划分

一，不断进行区间的划分缩小，直到划分成最小区间（长度为一）

二，进行递归处理，定义出一个临时数组用来存放区间左右两侧的比较大小后的结果

三，把临时数组的值赋予到原数组中，即把原两个数组合二为一

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
    if(l >= r) return ;
    int mid = l + r >> 1;
    merge_sort(q,l,mid),merge_sort(q,mid + 1,r);
    int k = 0;
    int i = l,j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(q[i] >= q[j]) tmp[k++] = q[j ++];
        else tmp[k++] = q[i++];
    }
    while(i <= mid)  tmp[k++] = q[i++] ;
    while(j <= r)    tmp[k++] = q[j++] ;
    for(int i = l,j = 0 ; i <= r; i ++ , j ++)
    {
        q[i] = tmp[j];
    }
    return ;
}
int main(void)
{
    cin >> n;
    for(int i = 0 ; i < n ; i++) cin >> q[i];
    merge_sort(q,0,n-1);
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
}

二分

双指针运算

一，先取到两个可以包含所求区间的左右边界的变量

二，定义出两个变量的中值

三，进行中值的可行性检查，以此来进行缩小区间

tips：区间划分时，if 后跟 l 时 ，需要进行 mid + 1 ；

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int n,qq;
int main(void)
{
    cin >> n >> qq;
    for(int i = 0 ; i < n ; i ++) scanf("%d",&q[i]);
    int k;
    while(qq --)
    {
        cin >> k;
        // 左边的第一个
        int l = 0 , r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(q[mid] >= k) r = mid;
            else l = mid + 1 ;
        }
        if(q[l] != k)cout << "-1 -1" << endl;
        else{
            cout << l << " ";
            l = 0, r = n - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(q[mid] <= k )l = mid;
                else r = mid - 1;
            }
            cout << r << endl;
        }
    }
    return 0;
}

高精度

为了防止出错误，一般都会加上去除前导 0 操作

高精度加法

一，利用字符串输入近两个长数字串，并利用 vector 来进行存储 转换后的字符串（倒序存储）

二，进行两个 vector 大小的判断，从而保证选取最大的数据范围

三，在 add 函数中定义出一个变量 t 用于上一次加法之后多余的十位数

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>add(vector<int> a,vector<int> b)
{
    vector<int> c;
    if(a.size() < b.size()) return add(b,a);
    int t = 0;
    for(int i = 0 ; i  < a.size(); i ++)
    {
        t += a[i];
        if(i < b.size()) t += b[i];
        c.push_back(t%10);
        t /=10;
    }
    if (t) c.push_back(t);
    return c;
}
int main(void)
{
    string a,b;
    cin >> a >> b;
    vector <int>A,B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    auto C = add(A, B);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;
    return 0;
}

高精度减法

一，由于长度和大小不同，为了防止出现负号的情况，需要用 cmp 函数比较一下

二，用 t 来表示上一次计算的借位

三，每次会进行 (t+10) % 10 操作 防止推入负数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(vector<int> a,vector <int> b)
{
    if(a.size() != b.size()) return a.size() > b.size();
    for(int i = a.size() - 1 ;i >= 0  ; i --)
    {
        if(a[i] != b[i])
            return a[i] > b[i];
    }
    return true;
}
vector<int> sub(vector<int> a,vector <int> b)
{
    vector <int> c;
    int t = 0;
    for(int i = 0 ; i < a.size() ; i ++)
    {
        t = a[i] - t;
        if(i < b.size()) t -= b[i];
        c.push_back((t+10) % 10);
        if(t < 0) t = 1;
        else t = 0;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
int main(void)
{
    string a,b;
    cin >> a>> b;
    vector<int> A,B,C;
    for(int i = a.size() - 1 ; i >= 0 ; i --) A.push_back(a[i] - '0');
    for(int i = b.size() - 1 ; i >= 0 ; i --) B.push_back(b[i] - '0');
    if(cmp(A,B)) C = sub(A,B);
    else{
        C = sub(B,A);
        cout << "-";
    }
    for(int i = C.size() - 1 ; i >= 0 ; i --) cout << C[i]  ;
    cout << endl;
    return 0;
}

高精度乘法

一，当 t 不为 0 的时候，需要继续进行操作

二，去除前导 0

三，需要判断是否再 a 的 size 内

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> mul(vector<int> a,int b)
{
    vector <int> c;
    int t = 0;
    for(int i = 0 ; i < a.size() || t; i ++)
    {
        if(i < a.size())t = t + a[i] * b;
        c.push_back(t % 10);
        t = t / 10;
    }
    while(c.size() > 1&& c.back() == 0) c.pop_back();
    return c;
}
int main(void)
{
    string a;
    int b;
    cin >> a;
    cin >> b;
    vector<int> A,C;
    for(int i = a.size() - 1 ; i >= 0 ; i --) A.push_back(a[i] - '0');
    // for(int i = b.size() - 1 ; i >= 0 ; i --) B.push_back(b[i] - '0');
    C = mul(A,b);
    for(int i = C.size() - 1 ; i >= 0 ; i--) cout << C[i];
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B) {
    vector<int> C(A.size() + B.size(), 0); // 初始化为 0，且999*99最多 5 位

    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    int t = 0;
    for (int i = 0; i < C.size(); i++) { // i = C.size() - 1时 t 一定小于 10
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0
    return C;
}

int main() {
    string a, b;
    cin >> a >> b; // a = "1222323", b = "2323423423"

    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--)
        B.push_back(b[i] - '0');

    auto C = mul(A, B);

    for (int i = C.size() - 1; i >= 0; i--)
        cout << C[i];

    return 0;
}

高精度除法

一，需要从高位数开始进行运算

二，每次都是取余操作

三，结束后需要 reverse 一下，可以更好匹配前面的值

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> divv(vector<int> a,int b,int & r)
{
    vector<int> c;
    for(int i = a.size() - 1 ; i >= 0 ; i --)
    {
        r = r * 10 + a[i];
        c.push_back(r / b);
        r = r % b;
    }
    reverse(c.begin(),c.end());
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
int main(void)
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A,c;
    for(int i = a.size() - 1 ; i >= 0 ; i -- ) A.push_back(a[i] - '0');
    int r = 0;
    c = divv(A,b,r);
    for(int i = c.size() - 1 ; i >= 0 ; i --) cout << c[i];
    cout << endl;
    cout << r << endl;
    return 0;
}

离散化

前缀和和差分

前缀和和差分操作都需要数组下标从 1 开始

一维前缀和

可以利用原数组自加来取到前缀和数组

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 +10;
int a[N];
int s[N];
int n,m;
int main(void)
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i];
    for(int i = 1 ; i <= n ; i++) a[i] += a[i-1];
    while(m --)
    {
        int l,r;
        cin >> l >> r;
        cout << a[r] - a[l-1] << endl;
    }
    return 0;
}

二维前缀和

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N][N];
int s[N][N];
int n,m,q;
int main(void)
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n ;i ++)
        for(int j = 1 ; j <= m ;j ++)
            cin >> a[i][j];
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    while(q--)
    {
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1-1] - s[x1 - 1][y2] + s[x1-1][y1-1] << endl;
    } 
    return 0;
}

一维差分

差分数组就是前缀和数组的逆数组，他的前 n 项和就是前缀和数组

可以直接用插入的方式来求出差分数组，一般用于区间的加减

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l] = b[l] + c;
    b[r+1] = b[r+1] - c;
}
int main(void)
{
    int n,m;
    cin>> n >> m;
    for(int i = 1;i<=n;i++)
        cin>>a[i];
    for(int i = 1;i<=n;i++)
        insert(i,i,a[i]);
    while(m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l,r,c);
    }
    for(int i = 1;i<=n;i++) b[i] += b[i-1];
    for(int i = 1;i<=n;i++) cout<<b[i]<<" ";
}

二维差分

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1] += c;
    b[x2 +1][y1] -= c;
    b[x1][y2+1] -=c;
    b[x2+1][y2+1] +=c;
}
int main(void)
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i = 1;i<=n;i++)
        for(int j =1;j<=m;j++)
            cin>>a[i][j];
    for(int i = 1;i<=n;i++)
        for(int j =1;j<=m;j++)
            insert(i,j,i,j,a[i][j]);
    while(q--)
    {
        int x1,x2,y1,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    for(int i =1;i<=n;i++)
        for(int j =1 ;j<=m;j++)
        b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
       for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }
}

双指针

一，双指针一般用于处理线性即具有单调性的操作

二，一般模板如下

#include <iostream>
using namespace std;
const int N = 1e5 +10;
int q[N];
int flag[N];
int main(void)
{
    int n;
    cin>>n;
    int ans = 0;
    for(int i = 0;i<n;i++) cin>>q[i];
    for(int i = 0,j = 0;i<n;i++)
    {
        flag[q[i]]++;
        while(j<=i && flag[q[i]]>1)
        {
            flag[q[j]]--;
            j++;
        }
        ans = max(ans,i-j+1);
    }
    cout<<ans<<endl;
    return 0;
}

位运算

(lowbit) O(nlogn)O(nlogn) 使用lowbit操作，进行，每次lowbit操作截取一个数字最后一个1后面的所有位，每次减去lowbit得到的数字，直到数字减到0，就得到了最终1的个数，

lowbit原理 根据计算机负数表示的特点，如一个数字原码是10001000，他的负数表示形势是补码，就是反码+1，反码是01110111，加一则是01111000，二者按位与得到了1000，就是我们想要的lowbit操作

#include <iostream>
using namespace std;
const int N = 1e6 +10;
int q[N];
int n;
int main(void)
{
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        int res = 0;
        while(x > 0) x = x - (x&-x),res ++;
        cout << res <<" ";
    }           
    return 0;
}

区间合`=