基础算法：排序 二分 高精度 前缀和与差分 双指针算法 位运算 离散化 区间合并

快速排序

#include
#include
#include
#include
using namespace std;
const int N = 100000 + 11;
int n;
int q[N];

void quick_sort(int q[],int l,int r){
    if(l>=r)    return ;
    int i = l-1;
    int j = r+1;
    int x = q[(l+r)/2];
    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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

归并排序

#include 
#include 
#include 
#include 
using namespace std;
const int N = 100000 + 11;
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;
    int 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(i=l,j=0;i<=r;i++,j++)   q[i] = temp[j];
}

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]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

整数二分

#include 
#include 
#include 
#include 
using namespace std;
const int N = 100000 + 11;
int n,k,q[N];

int main()
{
    scanf("%d%d", &n,&k);
    for (int i = 0; i < n; i ++ )
        scanf("%d",&q[i]);
    while(k--){
        int x = 0;
        scanf("%d",&x);
        
        int l = 0,r = n-1;
        while(l<r){
            int mid = (l+r)/2;
            if(q[mid]>=x)   r = mid;
            else    l = mid+1;
        }
        
        if(q[l]!=x){
            printf("-1 -1\n");
            continue;
        }else{
            printf("%d ",l);
        }
        
        l = 0,r = n-1;
        while(l<r){
            int mid = (l+r+1)/2;
            if(q[mid]<=x)   l = mid;
            else    r = mid-1;
        }
        
        printf("%d\n",r);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

浮点数二分

#include 
#include 
#include 
#include 
using namespace std;
double n;


int main()
{
    scanf("%lf", &n);
    double l = -10000,r = 10000;
    while((r-l)>=1e-8){
        double mid = (l+r)/2;
        if((mid*mid*mid)>=n)    r = mid;
        else    l = mid;
        // if((mid*mid*mid)<=n)    l = mid;
        // else    r = mid;
    }
    printf("%lf",l);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

高精度加法

#include 
#include 
#include 
#include 
using namespace 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];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    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 = add(A,B);
    for(int i=C.size()-1;i>=0;i--)  
        cout<<C[i];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

高精度减法

#include 
#include 
#include 
#include 
using namespace std;

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;
}

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 (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 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');
    vector<int> C;
    
    if(cmp(A,B)){
        C = sub(A,B);
        for (int i = C.size()-1; i >= 0; i -- )
            cout << C[i];
    }else{
        C = sub(B,A);
        cout << "-";
        for (int i = C.size()-1; i >= 0; i -- )
            cout << C[i];
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

高精度乘法

#include 
#include 
#include 
#include 
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 ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    cin>>a;
    int b;
    cin>>b;
    vector<int> A;
    for(int i=a.size()-1;i>=0;i--)  A.push_back(a[i]-'0');
    vector<int> C = mul(A,b);
    for(int i=C.size()-1;i>=0;i--)
        cout << C[i];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

高精度除法

#include 
#include 
#include 
#include 
using namespace std;

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);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

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

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

一维前缀和

#include 
#include 
#include 
#include 
using namespace std;
const int N = 100000 + 11;
int n,m;
int a[N],s[N];

int main()
{
    scanf("%d%d", &n,&m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ )
        s[i] = s[i-1] + a[i];
    while (m -- ){
        int l,r;
        scanf("%d%d", &l, &r);
        printf("%d\n",s[r] - s[l-1]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二维前缀和

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1000 + 11;
int a[N][N],s[N][N];
int n,m,q;

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]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

一维差分

#include 
#include 
#include 
#include 
using namespace std;
const int N = 100000 + 11;
int n,m;
int a[N],b[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ )
        b[i] = a[i] - a[i-1];
    while (m -- ){
        int l,r,c;
        scanf("%d%d%d", &l, &r, &c);
        b[l] = b[l] + c;
        b[r+1] = b[r+1] - c;
    }
    for (int i = 1; i <= n; i ++ ){
        a[i] = a[i-1] + b[i];
        printf("%d ",a[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

二维差分

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1000+11;

int n,m,q;

int a[N][N],b[N][N];

int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            b[i][j] = a[i][j] - a[i-1][j] -a[i][j-1] + a[i-1][j-1];
    
    while(q--){
        int x1,y1,x2,y2,c;
        cin>>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++)
            a[i][j] = b[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

双指针

#include 

using namespace std;

const int N = 100010;

int n;
int q[N], s[N];

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

    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        s[q[i]] ++ ;
        while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ;
        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

位运算

#include 

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int x, s = 0;
        scanf("%d", &x);

        for (int i = x; i; i -= i & -i) s ++ ;

        printf("%d ", s);
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20