Acwing算法基础课 第一章 基础算法

第一章 基础算法

一、排序

快速排序

void qsort(int a[],int l,int r)
{
    if(l>=r) return;
    int i=l-1,j=r+1,x=a[(l+r)/2];
    while(ix);
        if(i

进阶：快选算法：求第K个小的数(O(2n))

#include
using namespace std;
const int M=100005;
int n,k,a[M];

int qsort(int l,int r,int k) //快速选择算法
{
    if(l>=r) return a[l]; //如果只剩一个数，那么一定是答案
    int i = l-1,j = r+1,x = a[l+r>>1]; //快排模板
    while(ix);
        if(i

归并排序

void merge_sort(int a[],int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)/2;
    merge_sort(a,l,mid),merge_sort(a,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) tmp[k++]=a[i++];
        else tmp[k++]=a[j++];
    }
    while(i<=mid) tmp[k++]=a[i++];
    while(j<=r) tmp[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++) a[i]=tmp[j];
}

二、二分查找

给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。如果数组中不存在该元素，则返回 -1 -1。

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

三、高精度运算

高精度加法

#include
#include
using namespace std;
const int M=100000;
vector add(vector&a,vector&b)
{
    vector C;
    int c=0;
    for(int i=0;i0) C.push_back(1);
    return C;
}
int main()
{
    string A,B;
    vector 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');
    }
    auto c=add(a,b);
    for(int i=c.size()-1;i>=0;i--) cout<

高精度减法

#include
#include
using namespace std;
const int M=1e5+10;
void killzero(vector&A)//去掉前导0，如009->9
{
    while(A.size()>1&&A.back()==0) A.pop_back();
}
bool cmp(vector&A,vector&B)//判断是否A>=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;//注意两数相等时返回TRUE
}
vector sub(vector&A,vector&B)
{
    vectorC;
    for(int i=0,t=0;i=0) C.push_back(t);
        else C.push_back(10+t);
        if(t<0) t=1;//t不是0就是1，小于0说明已发生借位
        else t=0;
    }
    killzero(C);
    return C;
}
int main()
{
    string a,b;
    vectorA,B,C;
    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');
    }
    killzero(A),killzero(B);//去掉前导0
    if(cmp(A,B)) C=sub(A,B);
    else 
    {
        cout<<"-";
        C=sub(B,A);
    }
    for(int i=C.size()-1;i>=0;i--)
    cout<

高精度乘法

#include
#include
using namespace std;
void kill_zero(vector&A)
{
    while(A.size()>1&&A.back()==0) A.pop_back();
}
vector mul(vector&A,int b)
{
    vectorC;
    int t=0;//进位
    for(int i=0;i>a>>b;
   vectorA;
   for(int i=a.size()-1;i>=0;i--)
   A.push_back(a[i]-'0');
   kill_zero(A);
   auto C = mul(A,b);
   kill_zero(C);
   for(int i=C.size()-1;i>=0;i--)
   cout<

高精度除法

#include
#include
#include
#include
using namespace std;
void killzero(vector &A)//去前导0
{
    while(A.size()>1&&A.back()==0) A.pop_back();
}
vectordivide(vectorA,int b,int &t)
{
    vectorC;
    t=0;//余数
    for(int i=A.size()-1;i>=0;i--)
    {
        t=t*10+A[i];
        C.push_back(t/b);
        t=t%b;
    }
    reverse(C.begin(),C.end());//与高精度存储方式同步：从低到高
    killzero(C);
    return C;
}
int main()
{
    string a;
    vectorA;
    int b,t;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)
    A.push_back(a[i]-'0');
    killzero(A);
    auto C = divide(A,b,t);
    for(int i=C.size()-1;i>=0;i--)
    cout<

四、前缀和与差分

一维前缀和

#include
using namespace std;
const int M=100005;
int n,m,l,r,a[M],s[M];
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];//前缀和初始化
    }
    while(m--)
    {
        scanf("%d %d",&l,&r);
        cout<

二维前缀和

#include
using namespace std;
const int M=1005;
int n,m,q,a[M][M],s[M][M];
int main()
{
    scanf("%d %d %d",&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-1][j]+s[i][j-1]-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
using namespace std;
const int M=100005;
int n,m,l,r,c,a[M],b[M];//全局变量默认初始化全0
void insert(int l,int r,int c)//插入函数
{
    b[l]=b[l]+c;
    b[r+1]=b[r+1]-c;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        insert(i,i,a[i]);//输入原数组相当于对a进行插入，对差分b也要进行操作
    }
    while(m--)
    {
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=b[i-1]+b[i];//a相当于b的前缀和数组，通过差分b数组求和计算a数组
    }
    for(int i=1;i<=n;i++) printf("%d ",b[i]);
    return 0;
}

二维差分

#include
using namespace std;
const int M=1005;
int n,m,q,a[M][M],b[M][M];//全局变量默认初始化全0
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];
            insert(i,j,i,j,a[i][j]);//输入原数组相当于对a进行插入，对差分b也要进行操作
        }
    }
    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++)//a相当于b的前缀和数组，通过差分b数组求前缀和还原操作后的a数组
    {
        for(int j=1;j<=m;j++)
        {
            b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];//计算前缀和公式，注意与模板的区别
            cout<cout<

五、位运算

求二进制中1的个数

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

六、离散化

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 cc。接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r][l,r] 之间的所有数的和。

#include
using namespace std;
typedef pair PII;//2个数据合成一组
const int M=3*1e5+10;//因为数据n,m很大
int a[M],s[M],n,m,x,c,l,r;
vectoralls;//存放所有大数据
vectoradd,query;//操作与询问数组
int find(int x)//在alls中进行二分查找映射的数
{
    int l=0,r=alls.size()-1;
    while(l>1;
        if(x<=alls[mid]) r=mid;
        else l=mid+1;
    }
    return r+1;//保证映射在区间[1,n],方便处理前缀和的边界问题
}
int main()
{
    cin>>n>>m;
    for(int i=0;i>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i=0;i>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());//排序并去重
    for(auto item:add)//处理操作
    {
        int x=find(item.first);
        a[x]=a[x]+item.second;
    }
    for(int i=1;i<=alls.size();i++)//前缀和处理
    {
        s[i]=s[i-1]+a[i];
    }
    for(auto item:query)//计算并处理询问
    {
        l=find(item.first),r=find(item.second);
        cout<

七、区间合并

给定 n 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。

例如：[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。

#include
using namespace std;
const int M=1e5+10;
int n;
typedef pair PII;
vectorarea;
void merge(vector&area)
{
    vectorres;
    sort(area.begin(),area.end());
    int st=area[0].first,ed=area[0].second;
    for(int i=1;i>n;
    while(n--)
    {
        int l,r;
        cin>>l>>r;
        area.push_back({l,r});
    }
    merge(area);
    cout<
算法

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

标签

一品网 冀ICP备14022925号-6