从零开始的算法学习

基础算法

排序

快速排序

1. 确定分界点q[l] q[r] q[(l+r)/2]或者随机

2. 调整区间

3. 递归处理左右两段

#include <iostream>
using namespace std;

const int N=1e6+10;

int n;
int q[N];

void  quick_sort(int q[],int l,int r){
    if(l>=r) return;
    int x=q[l],i=l-1,j=r+1;
    while(i<j){
        do i++; while (q[i]<x);
        do j--;while(q[j]>x);
        if (i<j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    quick_sort(q,0,n-1);

    for (int i = 0; i < n; i++) printf("%d ",q[i]);
    return 0;
}

归并排序

1. 确定分界点 mid=(l+r)

2. 递归排序左右两边

3. 归并

#include <iostream>
using namespace std;

const int N=1000010;

int n;
int q[N];
int temp[N];

void merge_sort(int q[],int l,int r){
    if (l>=r) return;

    int mid=(l+r)/2;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r) {
        if (q[i] <= q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while(i<=mid) temp[k++]=q[i++];
    while (j<=r) temp[k++] = q[j++];

    for (int m = 0; m < k; ++m)
        q[l+m]=temp[m];
}

int main(){
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) scanf("%d",&q[i]);

    merge_sort(q,0,n-1);

    for (int i = 0; i < n; ++i) printf("%d ",q[i]);
}

二分

整数二分

int bsearch(int l,int r){
    while(l<r){
        int mid=l+r+1 >>1;
        if (check(mid)) l=mid;  //find right boundary
        else r=mid-1;
    }
    return l;   //l=r
}

int bsearch(int l,int r){
    while(l<r){
        int mid=l+r >>1;
        if (check(mid)) r=mid;  //find left boundary
        else l=mid+1;
    }
    return l;   //l=r
}

浮点数二分

#include <iostream>
using namespace std;

int main(){
    double x;
    cin>>x;

    double l=0,r=x;
    while(r-l>1e-8){
        double mid=(l+r)/2;
        if (mid*mid>=x) r=mid;
        else l=mid;
    }
    cout<<l;
}

三分

while (r - l > eps) {
  mid = (l + r) / 2;
  lmid = mid - eps;
  rmid = mid + eps;
  if (f(lmid) < f(rmid))
    r = mid;
  else
    l = mid;
}

高精度

A+B

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

vector<int> add (vector<int> &A,vector<int>&B){
    vector<int>c;
    int i=0,r=0;
    while(i<A.size()||i<B.size()){
        r+=i<A.size()?A[i]:0;
        r+=i<B.size()?B[i]:0;
        c.push_back(r%10);
        r/=10;
        i++;
    }
    if (r) c.push_back(r);
    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');
    }

    auto C= add(A,B);
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    return 0;
}

A-B

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

bool cmp(string &A,string &B){
    if(A.size()!=B.size()) return A.size()>B.size();
    return A>=B;
}

vector<int> sub (vector<int> &A,vector<int>&B){
    int r=0;
    int i=0;
    vector<int>c;
    while (i<A.size()){
        r=A[i]+r;
        if(i<B.size()) r-=B[i];
        if (r<0){
            c.push_back(r+10);
            r=-1;
        }
        else{
            c.push_back(r);
            r=0;
        }
        i++;
    }
    while (c.back()==0&&c.size()!=1) 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');
    }
    vector<int>C;
    if (cmp(a,b)) C= sub(A,B);
    else{  C= sub(B,A); cout<<"-";}
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    return 0;
}

A*B

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

vector<int> mul (vector<int> &A,vector<int>&B){
    vector<int> c(A.size() + B.size(), 0); // 初始化为0，大小为A.size() + B.size()
    for (int i = 0; i < A.size(); ++i) {
        for (int j = 0; j < B.size(); ++j) {
            c[i + j] += A[i] * B[j]; // i个0 * j个0 = i+j 个0。例如1000*10=10000
        }
    }
    // 处理进位
    for (int i = 0; i < c.size(); ++i) {
        if (c[i] > 9) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }
    // 去除前导0
    while (c.back() == 0 && c.size() > 1) {
        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');
    }
    // 计算结果
    vector<int> C = mul(A, B);
    // 输出结果
    for (int i = C.size() - 1; i >= 0; i--) {
        printf("%d", C[i]);
    }
    return 0;
}

前缀和

差分

一维

#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int b[N];

void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}

int main(){
    int n,m,l,r,c;
    long long temp=0;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(i,i,a[i]);
    }
    for (int i = 0; i < m; ++i) {
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for (int i = 1; i <= n; ++i) {
        temp+=b[i];
        cout<<temp<<" ";
    }
    return 0;
}

二维

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N];
int b[N][N];

void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1]+=c;
    b[x1][y2+1]-=c;
    b[x2+1][y1]-=c;
    b[x2+1][y2+1]+=c;
}
int main(){
    int n,m,q;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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]);
        }
    }
    for (int i = 0; i < q; ++i) {
        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) {
        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;
    }
    return 0;
}