基础算法二

高精度加法

就是手工模拟一次加法的过程

#include <iostream>
#include <vector>
using namespace std;

vector<int> add (vector<int> &A,vector<int> &B){
    vector<int> C;
    if(A.size()<B.size()) return add(B,A);//确保A是最大的数，能遍历所有的数
     int t=0;//开始进位为0
     for(int i=0;i<A.size();i++){
         t+=A[i];
         if(B.size()>i) t+=B[i];//B该位有数则加上
         C.push_back(t%10);
         t/=10;//进位变为1或者0
     }
    if(t)  C.push_back(t);//算完之后t=1，则加上这个最高位    A-19 B-1  add(A,B)--》00--》001《--C
    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');//Ascall码中字符0-9与数字0-9，相差48刚好一个字符0-'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--) printf("%d",C[i]);//将结果从最高位开始输出
    return 0;
}

高精度减法

就是手工模拟一次减法的过程

#include<iostream>
#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(B.size()>i) t-=B[i];
        C.push_back((t+10)%10);
        if(t<0) t=1;
        else t=0;
    }
    //去掉前导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');
    
    
    //判断A,B的大小 如果A-B，B>A则变成sub(B-A),输出时在前面加"-"
    if(cmp(A,B)){ 
       auto C=sub(A,B);
       for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    }else{ 
       auto C=sub(B,A);
       printf("-");
       for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    }
    
    
    
    return 0;
    
    
    
}

高精度乘低精度

大整数乘以一个小整数

就是一个大整数的每一位都乘以这个小整数，对结果求余（%10）就得到的最低位就是当前位数；对结果除以10就可以得到进位

#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++){//进位未处理或者A未遍历完
        if(A.size()>i) t+=A[i]*b;
        C.push_back(t%10); 
        t/=10;
    }
    
    //处理前导0
    while(C.size()>1&&C.back()==0) C.pop_back();
    
    
    return C;
    
}

int main(){
    string a;
    int b;
    vector<int> A;
    cin>>a>>b;
    
    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--) printf("%d",C[i]);
    
    return 0;
}

高精度除以低精度

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> div(vector<int> &A,int b,int &r){
    vector <int>C;
    for(int i=A.size()-1;i>=0;i--){
        r=r*10+A[i];
        C.push_back(r/b);
        r=r%b;
    }
    reverse(C.begin(),C.end());
    
    while(C.size()>1&&C.back()==0) C.pop_back();
    
    return C;
}



int main(){
    int b;
    string a;
    vector<int>A;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    int r=0;
    auto C=div(A,b,r);
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]); 
    
    cout<<endl<<r<<endl;
    return 0;
}

一维前缀和

把S[0]=0,更方便，所以最好从i=1开始

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]       时间复杂度 O(1)

二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

#include<iostream>
using namespace std;
const int N=1000+10;
int n,m,q,arr[N][N],s[N][N];

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",&arr[i][j]);
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+arr[i][j];
        }
    }
    int x1,x2,y1,y2;
    while(q--){

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int temp=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
        printf("%d\n",temp);
    }

    return 0;
}

一维差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,arr[N],b[N];
void b_insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        b_insert(i,i,arr[i]);
        
    }
    while(m--){
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        b_insert(l,r,c);
    }
    
    for(int i=1;i<=n;i++){
         b[i+1]+=b[i];
        printf("%d ",b[i]);
    }
    
    return 0;
}

二维差分

给以(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



#include<iostream>
using namespace std;
const int N=1000+10;
int n,m,q,arr[N][N],s[N][N];

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",&arr[i][j]);
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+arr[i][j];
        }
    }
    int x1,x2,y1,y2;
    while(q--){

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int temp=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
        printf("%d\n",temp);
    }

    return 0;
}

双指针算法

核心思想：

//将朴素算法 O(n^2) 优化成O(n)
//朴素算法：
for(int i=0;i<n;i++)
	for(int j<=i;j<n;j++){
	}
	
//双指针：
	for(int i=0,j=0;i<n;i++){
	while(j<r&&check(i,j)) j++;
	}

模板

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
 					     = n & (~n+1) 补码

离散化

#include<algorithm>
#include<vector>
#include <iostream>
using namespace std;
const int N=3e5+10;
int a[N],s[N];
vector<pair<int,int>> queryVec,addVec;
vector<int> alls;

//用二分法找到映射坐标的数组下标
int find(int x){
    int l=0;
    int r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    
    return l+1;//注意为了方便前缀和，从1开始算 a[1]----s[1]
    
}



int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    
    //加入添加数据的坐标
    while(n--){
        int x,c;
        scanf("%d%d",&x,&c);
        alls.push_back(x);
        addVec.push_back({x,c});
    }
    
    //加入询问的坐标
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        alls.push_back(l);
        alls.push_back(r);
        queryVec.push_back({l,r});
    }
    
    //排序去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    //处理添加
    for(auto temp:addVec){
        int x=find(temp.first);
        a[x]+=temp.second;
        
    }
    
    //处理前缀和
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
    
    //处理查询
    for(auto temp:queryVec){
        int l=find(temp.first);
        int r=find(temp.second);
        printf("%d\n",s[r]-s[l-1]);
    }
    
    
    return 0;
}

区间合并

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
vector<pair<int,int>> seg;

void merge(vector<pair<int,int>> &seg){
    
    vector<pair<int,int>> res;
    int l=-2e9,r=-2e9;
    
    for(auto temp:seg){
        if(temp.first>r){
            //确保不是开始那个无限远的区间再加入
            if(l!=-2e9) res.push_back({l,r});
            //开始检测新区间
            l=temp.first;
            r=temp.second;
        }else r=max(r,temp.second);
        
        
        
    }
    if(l!=-2e9) res.push_back({l,r});//加上最后一个区间
    seg=res;
    
}

int main(){
    int n;
     scanf("%d",&n);
    while(n--){
        int l,r;
        scanf("%d%d",&l,&r);
        seg.push_back({l,r});
    }
     
    sort(seg.begin(),seg.end());
    
    merge(seg);
    printf("%d",seg.size());
    
    return 0;
}