算法基礎(chǔ)課——基礎(chǔ)算法（模板整理）

這篇具有很好參考價(jià)值的文章主要介紹了算法基礎(chǔ)課——基礎(chǔ)算法（模板整理）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

?快速排序

快速排序

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int s[100000];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }
    sort(s,s+n);
    for(int i=0;i<n;i++)
    {
        cout<<s[i]<<" ";
    }
    cout<<endl;
    return 0;
}

第K個(gè)數(shù)

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    nth_element(a+1,a+k,a+1+n);
    cout<<a[k]<<endl;
    return 0;
}

歸并排序?

歸并排序

#include <iostream>
using namespace std;
const int N = 100010;
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=1,i=l,j=mid+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(int i=l,j=1;i<=r;i++,j++)
    {
        q[i]=tmp[j];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&q[i]);
    }
    merge_sort(q,1,n);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",q[i]);
    }
    return 0;
}

逆序?qū)Φ臄?shù)量

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int q[N],tmp[N];
ll merge_sort(int l,int r)
{
    if(l>=r)
    {
        return 0;
    }
    int mid = (l+r)>>1;
    ll res=merge_sort(l,mid)+merge_sort(mid+1,r);
    //歸并的過(guò)程
    int k=1,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])
        {
            tmp[k++]=q[i++];
        }
        else
        {
            tmp[k++]=q[j++];
            res+=(mid-i+1);
        }
    }
    //掃尾
    while(i<=mid)
    {
        tmp[k++]=q[i++];
    }
    while(j<=r)
    {
        tmp[k++]=q[j++];
    }
    //物歸原主
    for(int i=l,j=1;i<=r;i++,j++)
    {
        q[i]=tmp[j];
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i];
    }
    cout<<merge_sort(1,n)<<endl;
    return 0;
}

二分?

數(shù)的范圍

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    while(m--)
    {
        int x;
        cin>>x;
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(q[mid]>=x)
            {
                r=mid;
            }
            else l=mid+1;
        }
        if(q[l]!=x)
        {
            cout<<"-1 -1"<<endl;
        }
        else
        {
            cout<<l<<" ";
            l=0;r=n-1;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(q[mid]<=x)
                {
                    l=mid;
                }
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

數(shù)的三次方根

#include <iostream>
using namespace std;
int main()
{
    double n;
    cin>>n;
    double l=-10000,r=10000;
    while(r-l>1e-8)
    {
        double mid = (l+r)/2;
        if(mid*mid*mid>=n)
        {
            r=mid;
        }
        else l=mid;
    }
    printf("%.6lf\n",l);
    return 0;
}

高精度

?高精度加法

Python一行就可以解決

print(int(input())+int(input()))

#include <iostream>
#include <string>
#include <vector>
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(t);
    }
    return C;
}
int main()
{
    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];
    }
    return 0;
}

高精度減法

#include <iostream>
#include <string>
#include <vector>
using namespace std;
//判斷是否有A>=B
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;
}
//C=A-B
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()
{
    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');
    }
    if(cmp(A,B))
    {
        auto C = sub(A,B);
        for(int i=C.size()-1;i>=0;i--)
        {
            cout<<C[i];
        }
    }
    else
    {
        auto C = sub(B,A);
        cout<<"-";
        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, int b)
{
    vector<int>C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i++)
    {
        if (i < A.size())
        {
            t += A[i] * b;
        }
        C.push_back(t % 10);
        t /= 10;
    }
    while(C.size()>1&&C.back()==0)
    {
        C.pop_back();
    }
    return C;
}
int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int>A;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    }
    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i--)
    {
        cout << C[i];
    }
    return 0;
}

高精度除法

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

前綴和與差分

前綴和

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

子矩陣的和

#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int main() 
{
    int n, m, q;
    cin >> n >> m >> q;
    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]; // 求前綴和
        }
    while (q--) 
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        // 算子矩陣的和
        printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); 
    }
    return 0;
}

差分

#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    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]<<" ";
    }
    return 0;
}

差分矩陣

#include <iostream>
using namespace std;
const int N = 1010;
int n,m,q;
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()
{
    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,y1,x2,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++)
        {
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

雙指針?biāo)惴?/strong>

最長(zhǎng)連續(xù)不重復(fù)子序列

#include <iostream> using namespace std; const int N = 100010; int n; int a[N],s[N]; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } int res=0; for(int i=1,j=1;i<=n;i++) { s[a[i]]++; while(s[a[i]]>1) { s[a[j]]--; j++; } res=max(res,i-j+1); } cout<<res<<endl; return 0; }

數(shù)組元素的目標(biāo)和

#include <iostream> using namespace std; const int N = 100005; int n,m,x; int a[N],b[N]; int main() { cin>>n>>m>>x; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=m;i++) { cin>>b[i]; } for(int i=1,j=m;i<=n;i++) { while(j>=1&&a[i]+b[j]>x) j--; if(a[i]+b[j]==x) { cout<<i-1<<" "<<j-1<<endl; break; } } return 0; }

判斷子序列

#include <iostream> using namespace std; const int N = 100005; int n,m; int a[N],b[N]; int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; } for(int i=0;i<m;i++) { cin>>b[i]; } int i=0,j=0; while(i<n&&j<m) { if(a[i]==b[j])i++; j++; } if(i==n) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } return 0; }

位運(yùn)算

二進(jìn)制中1的個(gè)數(shù)

#include <iostream> using namespace std; int lowbit(int x) { return x & -x; } int main() { int n; cin>>n; while(n--) { int x; cin>>x; int res=0; while(x) { x-=lowbit(x); res++; } cout<<res<<" "; } return 0; }

離散化

區(qū)間和

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 300010; //n次插入和m次查詢相關(guān)數(shù)據(jù)量的上界 int n, m; int a[N];//存儲(chǔ)坐標(biāo)插入的值 int s[N];//存儲(chǔ)數(shù)組a的前綴和 vector<int> alls; //存儲(chǔ)（所有與插入和查詢有關(guān)的）坐標(biāo) vector<pair<int, int>> add, query; //存儲(chǔ)插入和詢問(wèn)操作的數(shù)據(jù) int find(int x) { //返回的是輸入的坐標(biāo)的離散化下標(biāo) 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()); //執(zhí)行前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次詢問(wèn)操作 for (auto item : query) { int l = find(item.first); int r = find(item.second); printf("%d\n", s[r] - s[l-1]); } return 0; }

區(qū)間和并文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-660497.html

區(qū)間和并

#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef pair<int,int>pii; const int N = 100010; int n; vector<pii>segs; void merge(vector<pii>&segs) { vector<pii>res; sort(segs.begin(),segs.end()); int st=-2e9,ed=-2e9; for(auto seg:segs) { if(ed<seg.first) { if(ed!=-2e9) res.push_back({st,ed}); st=seg.first; ed=seg.second; } else ed=max(ed,seg.second); } if(st!=2e9) res.push_back({st,ed}); cout<<res.size()<<endl; } int main() { cin>>n; for(int i=0;i<n;i++) { int l,r; cin>>l>>r; segs.push_back({l,r}); } merge(segs); return 0; }

到了這里，關(guān)于算法基礎(chǔ)課——基礎(chǔ)算法（模板整理）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！