AcWing算法基础课笔记 1.基础算法

目录

AcWing算法基础课笔记 1.基础算法

二分排序

基本思想

基于分治的思想

1. 确定哨兵 x x x：可以取左边界，中间值，右边界，甚至是任意值；
2. 分区间：让小于 x x x的值全都归到 x x x的左边，大于 x x x的值全都归到 x x x的右边；
3. 递归处理左右两端直到整个序列有序

代码

这是严蔚敏版数据结构快排的代码，也是我我一直用的代码，不是y神的模板。

去打洛谷题会报TLE

#include<iostream>usingnamespace std;constint N =100010;int Array[N];//分区间intpartition(int* array,int low,int high){int value = array[low];while(low < high){while(low < high && array[high]>= value) high--;
        array[low]= array[high];while(low < high && array[low]<= value) low++;
        array[high]= array[low];}
    array[low]= value;return low;}//递归处理voidquicksort(int* array,int low,int high){if(low < high){int newvalue =partition(array, low, high);quicksort(array, low, newvalue);quicksort(array, newvalue+1, high);}}intmain(){int n;
    cin >> n;for(int i =0; i < n; i++) cin >> Array[i];quicksort(Array,0, n-1);for(int i =0; i < n; i++) cout << Array[i]<<" ";return0;}

归并排序

基本思路

基于分治的思想

1. 确定分界点 m i d = ( l o w + h i g h ) / 2 mid = (low + high) / 2 mid=(low+high)/2
2. 递归分解左右部分，直到不可再分
3. 回溯归并

详细的思路讲解见归并排序详解：20分钟理解归并排序 ，讲的真的很好很好

代码

#include<iostream>usingnamespace std;constint N =100010;int Array[N],tmp[N];voidmergesort(int* array,int low,int high){if(low >= high)return;//数组没有元素或者只有一个元素时，直接返回int mid =(low + high)/2;//递归分解左右部分，直到不可再分mergesort(array, low, mid);mergesort(array, mid +1, high);int k =0, i = low, j = mid +1;//归并：合二为一while(i <= mid && j <= high){//对每个分组进行排序if(array[i]<= array[j]) tmp[k++]= array[i++];else tmp[k++]= array[j++];}//将剩下来的数组元素直接加到数组后面while(i <= mid) tmp[k++]= array[i++];while(j <= high) tmp[k++]= array[j++];for(int i = low, j =0; i <= high; i++, j++) array[i]= tmp[j];}intmain(){int n;
    cin >> n;for(int i =0; i < n; i++) cin >> Array[i];mergesort(Array,0, n-1);for(int i =0; i < n; i++) cout << Array[i]<<" ";return0;}

高精度计算

高精度计算即大整数的加减乘除，C++中没有表示大整数的类型，最长的long long也只有64位

而大整数指的是数字长度

    ≤
   
   
    1
   
   
    
     0
    
    
     6
    
   
  
  
   \leq 10^6
  
 
≤106，注意是长度，不是数值。而小整数指的是数值

 
  
   
    ≤
   
   
    1
   
   
    
     0
    
    
     9
    
   
  
  
   \leq 10^9
  
 
≤109

而在实际做题或者应用中，通常是这四种：

• 两个大整数相加
• 两个大整数相减
• 一个大整数乘以一个小整数
• 一个大整数除以一个小整数

大整数的存储：对于大整数通常用数组存储，从低位到高位存储比较方便。

加法

#include<iostream>#include<algorithm>#include<vector>usingnamespace 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];//每一位A[i]+B[i]+t
        C.emplace_back(t %10);//存储的是模10的值
        t = t /10;//重新计算进位用于下一位的计算}if(t) C.emplace_back(t);//如果最后仍然有进位return C;}intmain(){
    string a,b;
    vector<int> A,B;
    cin >> a >> b;for(int i = a.size()-1; i >=0; i--) A.emplace_back(a[i]-'0');for(int i = b.size()-1; i >=0; i--) B.emplace_back(b[i]-'0');
    vector<int> C =add(A, B);for(int i = C.size()-1; i >=0; i--) cout << C[i];return0;}

减法

减法跟加法一样，需要额外考虑的是A与B谁大，并调用对应的减法函数并加上负号即可

#include<iostream>#include<algorithm>#include<vector>usingnamespace std;//判断A是否大于Bboolcmp(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];//位数相等}returntrue;//两者相等}//此时的算法是在确定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 < B.size(); i++){if(i < A.size()) t = A[i]- t;//计算每一位需要A[i]-B[i]-tif(i < B.size()) t -= B[i];      
        C.emplace_back((t +10)%10);//如果求出来的值大于0，就是自身，如果小于零，就要借位+10，而这两种情况都可以用+10再模10进行一步运算if(t <0) t =1;//如果t小于零，就说明借位了，需要赋值1，用于下一位的计算else t =0;}while(C.size()>1&& C.back()==0) C.pop_back();//去除前导零，例如11-11=00，需要把前面的0去掉同时保证如果答案就是0的时候则不去return C;}intmain(){
    string a,b;
    vector<int> A,B;
    cin >> a >> b;for(int i = a.size()-1; i >=0; i--) A.emplace_back(a[i]-'0');for(int i = b.size()-1; i >=0; i--) B.emplace_back(b[i]-'0');if(cmp(A, B)){
        vector<int> C =sub(A, B);//如果A>B，就用A-Bfor(int i = C.size()-1; i >=0; i--) cout << C[i];}else{
        vector<int> C =sub(B, A);//如果A<B，就用B-A，然后加-号即可
        cout <<"-";for(int i = C.size()-1; i >=0; i--) cout << C[i];}return0;}

乘法

跟加法差不多，不难，需要注意的是对

    t
   
  
  
   t
  
 
t 的额外处理

#include<iostream>#include<algorithm>#include<vector>usingnamespace std;

vector<int>mul(vector<int>& A,int b){
    vector<int> C;int t =0;//应该压入数组的每一位数值for(int i =0; i < A.size()|| t; i++){//确保把T处理完if(i < A.size()) t += A[i]* b;   
        C.emplace_back(t %10);
        t = t /10;//t不像加法，可能一次除不到位}return C;}intmain(){
    string a;
    vector<int> A;int b;
    cin >> a >> b;for(int i = a.size()-1; i >=0; i--) A.emplace_back(a[i]-'0');
    vector<int> C =mul(A, b);for(int i = C.size()-1; i >=0; i--) cout << C[i];return0;}

除法

除法要求商和余数，且商和其他三个运算不同，因为除法是从最高位开始计算的，所以要搞清对于每一位应该是从小到大进行操作还是从大到小

#include<iostream>#include<algorithm>#include<vector>usingnamespace std;

vector<int>div(vector<int>& A,int b,int& t){
    vector<int> C;
    t =0;//应该压入数组的每一位数值for(int i = A.size()-1; i >=0; i--){//和加减乘不同，除法要从最高位开始
        t = t *10+ A[i];//算出每一步的被除数：当前位的数值*10+下一位
        C.emplace_back(t / b);//入数组的是被除数除以除数
        t = t % b;//可能有余数，用于下一步的计算}reverse(C.begin(), C.end());//由于最后是反着输出的，所以逆序一下while(C.size()>1&& C.back()==0) C.pop_back();//跟减法一样，去除前导0return C;}intmain(){
    string a;
    vector<int> A;int b;
    cin >> a >> b;for(int i = a.size()-1; i >=0; i--) A.emplace_back(a[i]-'0');int t;
    vector<int> C =div(A, b, t);for(int i = C.size()-1; i >=0; i--) cout << C[i];
    cout <<" "<< t;return0;}

前缀和

一维

#include<iostream>usingnamespace std;constint N =100010;int Array[N],s[N];intmain(){int n,m;
    cin >> n >> m;for(int i =1; i <= n; i++){
        cin >> Array[i];
        s[i]= s[i-1]+ Array[i];//计算从下标1开始的前缀和}while(m--){int low, high;
        cin >> low >> high;
        cout << s[high]- s[low-1]<< endl;//计算任意下标范围内的元素之和}return0;}

二维

画个图就能理解

#include<iostream>usingnamespace std;constint N =1010;int Array[N][N],s[N][N];intmain(){int n,m,q;
    cin >> n >> m >> q;for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){
            cin >> Array[i][j];
            s[i][j]= s[i-1][j]+ s[i][j-1]- s[i-1][j-1]+ Array[i][j];//计算前缀和}}while(m--){int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2]- s[x2][y1-1]- s[x1-1][y2]+ s[x1-1][y1-1]<< endl;//求范围和}return0;}