算法基础课第一讲基础算法总结

• 快速排序，时间复杂度O(nlogn)
  快速排序动态演示图：
  
  快速排序模板：

 void kssort(int a[],int l,int r)
 {
     if(l>=r) return;//边界
     int mid=a[l+r>>1],i=l-1,j=r+1;//mid取l或r时会超时
     //因为当整个数组有序时时间复杂度就变成O(n*n)了，但是取中点就不容易被卡成O(n*n)复杂度
     while(l<r)
     {
         do i++; while(a[i]<mid);
         do j--; while(a[j]>mid);
         if(i<j) swap(a[i],a[j]);
         else break;
     }
     kssort(a,l,j);//排序左半边
     kssort(a,j+1,r);//排序右半边
 }

• 归并排序，时间复杂度O(nlogn)
  归并排序动态演示图：
  
  归并排序模板：

void gbsort(int a[],int l,int r)
{
    if(l>=r) return;//边界
    int mid=(l+r)/2;
    gbsort(a,l,mid); gbsort(a,mid+1,r);//将原数组分成一个一个的数
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[j]<a[i]) b[k++]=a[j++];
        else b[k++]=a[i++];
    }//归并
    while(i<=mid) b[k++]=a[i++];//处理最后一个元素
    while(j<=r) b[k++]=a[j++];//处理最后一个元素
    for(int i=l,j=0;i<=r;i++,j++)
        a[i]=b[j];//将归并后的值赋值回原数组
}

• 二分
  1.整数二分模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;//一定要+1，不然会超时
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

2.浮点数二分模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

• 高精度
  1.高精度加法模板

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);//使A的位数大于等于B(可以省略，但要在循环条件那里加上||i<B.size()
    vector<int> C;//C=A+B
    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);//在C的末尾添加(t%10)
        t /= 10;
    }

    if (t) C.push_back(t);//如果t!=0,就在C的末尾加上t
    return C;
}

2.高精度减法模板

// C = A - B, 满足A >= B, A >= 0, B >= 0
bool cmp(vector<int> &A,vector<int> &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;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);//在C末尾添加((t+10)%10)
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除先导0,(pop_back删除最后一个元素)
    return C;
}

3.高精度乘低精度模板

// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )//循环到t=0并且i大于A的位数
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);//在C末尾添加(t%10)
        t /= 10;//进位
    }
    return C;

4.高精度除低精度

// A / b = C 余 r, A >= 0, b > 0
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);//在C的末尾加上r/b
        r %= b;//更新余数
    }
    reverse(C.begin(), C.end());//反转C数组(便于进行混合运算)
    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除先导0
    return C;
}

• 前缀和和差分
  1.前缀和
  (1)一维前缀和
  公式：S[i] = a[1] + a[2] + … a[i]
  a[l] + … + a[r] = S[r] - S[l - 1]
  一维前缀和模板：

//a数组是原始数组,s数组是前缀
void qzh()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];//计算a数组的前缀和
    }
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",s[y]-s[x-1]);
    }
}

(2)二维前缀和
公式：s[i][j]=a[i-1][j]+a[i][j-1]+a[i][j]-s[i-1][j-1]
a[x1][y1]+…+a[x2][y2]=s[i][j]-s[x1][y2]-s[x2][y1]+s[x1][y1]
二维前缀和模板：

//a数组是原始数组,s数组是前缀和数组
void qzh()
{
    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,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
    }
}

2.差分
(1)一维差分
B[i] = a[i] - a[i - 1]
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
一维差分模板：

//a是原始数组,b是差分数组
void cf()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]+=a[i];
        b[i+1]-=a[i];
    }
    while(m--)
    {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        b[l]+=c;
        b[r+1]-=c;
    }
}

(2)二维差分
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
二维差分模板：

void cf()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            b[i][j]+=a[i][j];
            b[i+1][j]-=a[i][j];
            b[i][j+1]-=a[i][j];
            b[i+1][j+1]+=a[i][j];
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=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];
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }
}

• 双指针算法
  算法思想： 利用问题本身与序列的特性（序列递增性质），使用两个下标i、j对序列进行扫描 （可以同向扫描，也可以反向扫描） ，以较低的复杂度解决问题。(也就是把O(n*n)的时间复杂度化成O(n))
  双指针算法模板：

    for (int i = 0, j = 0; i < n; i ++ )
    {
        while (j < i && check(i, j)) j ++ ;

        // 具体问题的逻辑
    }
    //常见问题分类：
    //  (1) 对于一个序列，用两个指针维护一段区间
    //  (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

• 位运算
  求n的第k位数字: n >> k & 1
  返回n的最后一位1：lowbit(n) = n & -n

void f()
{
    while(n--)
    {
        scanf("%d",&a);
        ans=0;
        while(a)
        {
            a-=a&-a;
            ans++;
        }
        cout<<ans<<" ";
    }
}

• 离散化
  离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
  通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
  离散化模板：

    vector<int> alls; // 存储所有待离散化的值
    sort(alls.begin(), alls.end()); // 将所有值排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

    // 二分求出x对应的离散化的值
    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;//映射成1,2,3...(便于做前缀和)
    }

• 区间和并
  区间和并模板：

// 将所有存在交集的区间合并
    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 (st != -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});

        segs = res;
    }