算法基础课-基础算法

基础算法

排序

快速排序模板

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];

void quick_sort(int q[],int l,int r)
{
    if(l>=r)  return;
    int i=l-1,j=r+1, x=q[l+r>>1];
    while(i<j)
    {
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
    
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++) printf("%d ",q[i]);
    return 0;
    
}

归并排序模板

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int q[N],temp[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, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    merge_sort(q,0,n-1);
    for(int j=0;j<n;j++) printf("%d ",q[j]);
    return 0;
}

二分模板

//写的 非常好的二分模板

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m,q[N];
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    while(m--)
    {
        int k;scanf("%d",&k);
        //寻找第一个等于K的坐标 我这边让二分的边界定为 左边为<5 右边>=5 则所求为r
        int l=-1,r=n;
        while(l+1!=r)//当l与r没有相接的时候,求边界
        {
            int mid=l+r>>1;
            //下面找第一个>=5的坐标
            if(q[mid]>=k) r=mid;
            else l=mid;
        }
        //此时得到的r是第一个>=5的坐标
        if(q[r]!=k) printf("-1 -1\n");
        else{
            printf("%d ",r);
                //现在找最后一个<=5的数字 我这边让二分的左边为<=5 右边为>5 则所求为ll
                int ll=-1,rr=n;
                while(ll+1!=rr)
                {
                    
                    int mid=ll+rr>>1;
                    if(q[mid]<=k) ll=mid;
                    else rr=mid;
                }
                if(q[ll]!=k) printf("%d\n",r);
                else printf("%d\n",ll);
            }
        
    }
    
}
//非常好的二分博客引用
https://blog.csdn.net/WJPnb1/article/details/126360962?spm=1001.2014.3001.5502

高精度

高精度加法模板

#include<bits/stdc++.h>
using namespace std;
//总结：
//第一步：字符串输入
//第二步：字符串转数字，逆序
//第三步：模板相加；
//第四步：逆序输出

vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size()) t+=A[i];
        if(i<B.size()) t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t) C.push_back(1);
    return C;
}
int main()
{
    string a,b;
    cin>>a>>b;//123456
    vector<int>A,B;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//[6,5,4,3,2,1]
    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--) printf("%d",C[i]);
    return 0;
}

高精度减法模板

#include<bits/stdc++.h>
using namespace std;


//第一步：输入
//第二步：比较
//第三步：相减：注意括号和前缀0要去掉
//第四步：输出
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++)
    {
        if(i<A.size()) t=A[i]-t;
        if(i<B.size()) t-=B[i];
        C.push_back((t+10)%10);//虽然A比B大，但是A的某一位的数字可能比B小，所以这里加上10再模10
        if(t<0) t=1;//用于给A去减掉
        else t=0;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

int main()
{
    string a,b;
    vector<int> A,B;
    cin>>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');
    vector<int>C;
    if(cmp(A,B)) C=sub(A,B);
    else C=sub(B,A),cout << '-';//这里的负号是A-B=-(B-A)；
    for(int i=C.size()-1;i>=0;i--)  printf("%d",C[i]);
    cout<<endl;
    return 0;
    
}

高精度乘法模板

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> add(vector<int> A, vector<int> B) {
    // A: 4 3 2 1
    // B: 6 5
    vector<int> C(max(A.size(), B.size()) + 7, 0);  // 数组C开大一点没事，反正可以去前导零的
    for (int i = 0; i < A.size(); i ++) C[i] += A[i];
    for (int i = 0; i < B.size(); i ++) C[i] += B[i];

    // 处理进位
    for (int i = 0; i + 1 < C.size(); i ++) {
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    // 处理前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();

    reverse(C.begin(), C.end());
    return C;
}

vector<int> mul(vector<int> A, vector<int> B) {
    // A: 4 3 2 1
    // B: 6 5
    vector<int> C(A.size() + B.size() + 7, 0);  // 数组C开大一点没事，反正可以去前导零的
    for (int i = 0; i < A.size(); i ++) {
        for (int j = 0; j < B.size(); j ++) {
            C[i + j] += A[i] * B[j];
        }
    }

    // 处理进位
    for (int i = 0; i + 1 < C.size(); i ++) {
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    // 处理前导零 "0000" 去掉前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();

    reverse(C.begin(), C.end());
    return C;
}

int main() {
    string s1 = "9899", s2 = "100";

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

    vector<int> C = add(A, B);
    cout << s1 << "+" << s2 << "=";
    for (int i = 0; i < C.size(); i ++) cout << C[i];
    cout << endl;

    C = mul(A, B);
    cout << s1 << "*" << s2 << "=";
    for (int i = 0; i < C.size(); i ++) cout << C[i];
    cout << endl;

    return 0;
}

链接：https://www.acwing.com/solution/content/13694/

高精度除法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//int r=0;
vector<int> div(vector<int> &A,int B,int &r){//r传入r的地址，便于直接对余数r进行修改
    vector<int> C;
    for(int i=0;i<A.size();i++){//对A从最高位开始处理
        r=r*10+A[i];//将上次的余数*10在加上当前位的数字，便是该位需要除的被除数
        C.push_back(r/B);//所得即为商在这一位的数字
        r=r%B;//这里的余数是一个等价关系，不懂可以看视频
    }
    //由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，vector只有删除最后一个数字pop_back是常数复杂度，而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移，
    //因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}
int main(){
    string a;
    int B,r=0; //代表余数
    cin>>a>>B;
    vector<int> A;
    for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位，由于在除法的手算过程中，发现从高位进行处理
    //for(int i=0;i<A.size();i++) cout<<A[i];
    //cout<<B;
    auto C = div(A,B,r);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位
    cout<<endl<<r;//输出余数
    cout<<endl;
    return 0;
}

前缀和与差分

前缀和

//前缀和的思想是存sum，然后相减进行计算
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],sum[N];
int main()
{
    int n,m,x;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        sum[i]=x+sum[i-1];
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;
}

一维差分模板

//差分非常高效的减少了运算关系的时间复杂度，二维差分的模板同样可以看y总给的那个矩阵
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],b[N];

void insert(int &l,int &r,int &c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) insert(i,i,a[i]);
    
    while(m--)
    {
        int l,r,c;
        scanf("%d%d%d", &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 ++ ) printf("%d ",b[i]);
    return 0;
}

双指针算法

最长连续不重复子序列

//其实这在后面好像是一道dp题目，双指针算法的核心就是用两个指针来解题
# include <iostream>
using namespace std;

const int N = 100010;
int a[N], s[N];

int main()
{
    int n, r = 0;
    cin >> n;

    for (int i = 0, j = 0; i < n; ++ i)
    {
        cin >> a[i];
        ++ s[a[i]];
        while (s[a[i]] > 1) -- s[a[j++]]; // 先减次数后右移
        r = max(r, i - j + 1) ;
    }
    cout << r;

    return 0;
}

位运算

//这里主要是了解一个lowbit操作
#include<bits/stdc++.h>
using namespace std;


int  lowbit(int &x)//这个代码的关键是这个函数，每次输出x=的最后一位1;
{
    return x&-x;
}
int main()
{
    int n;
    cin>>n;
    while (n -- )
    {
        int x; 
        cin >> x;
        int res=0;
        while(x>0) x-=lowbit(x),res++;//每次减去x的最后一位1;直到没有1，那么res即为所求
        cout << res<<" ";
    }
    
}

区间和

//当空间稀疏性非常大的时候的做法，最后的实现也是前缀和，通过离散化，将空间的利用率降低了
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 300010; //n次插入和m次查询相关数据量的上界
int n, m;
int a[N];//存储坐标插入的值
int s[N];//存储数组a的前缀和
vector<int> alls;  //存储（所有与插入和查询有关的）坐标
vector<pair<int, int>> add, query; //存储插入和询问操作的数据

int find(int x) { //返回的是输入的坐标的离散化下标
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 1; i <= m; i++) {
        int l , r;
        scanf("%d%d", &l, &r);
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
   //排序，去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    //执行前n次插入操作
    for (auto item : add) {
        int x = find(item.first);
        a[x] += item.second;
    }
    //前缀和
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];
    //处理后m次询问操作
    for (auto item : query) {
        int l = find(item.first);
        int r = find(item.second);
        printf("%d\n", s[r] - s[l-1]);
    }

    return 0;
}

区间合并

这里看到一个区间合并，很绝的思路模板
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
PII a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+1,a+n+1);//sort对于二元组的排序规则是先考虑第一个元素，再考虑第二个元素
    int ed=a[1].second,ans=0;
    for(int i=2;i<=n;i++)
    {
        if(ed>=a[i].first)ed=max(ed,a[i].second);
        else ans++,ed=a[i].second;
    }
    cout<<ans+1<<endl;
}