基础算法模板

快速排序

时间复杂度O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//l:左端点  r:右端点
void quick_sort(int a[], int l, int r)
{
    if (l >= r) return ;

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

    quick_sort(a, l, j), quick_sort(a, j + 1, r);
}

应用 求第k小的数

时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//返回第k小的数
int quick_sort(int a[], int l, int r, int k)
{
    if (l >= r) return a[r];

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

    int len = j - l + 1;
    if (k <= len) return quick_sort(a, l, j, k);
    else return quick_sort(a, j + 1, r, k - len);
}

归并排序

时间复杂度O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(int a[], int l, int r)
{
    if (l >= r) return ;

    int mid = l + r >> 1;
    merge_sort(a, l, mid), merge_sort(a, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j]) t[k ++ ] = a[i ++ ];
        else t[k ++ ] = a[j ++ ];
    }
    while (i <= mid) t[k ++ ] = a[i ++ ];
    while (j <= r) t[k ++ ] = a[j ++ ];

    for (int i = l, j = 0; i <= r; i ++ , j ++ ) a[i] = t[j];
}

应用 求逆序对的数量

时间复杂度O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int merge_sort(int a[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;
    int res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j]) t[k ++ ] = a[i ++ ];
        else
        {
            res += mid - i + 1;
            t[k ++ ] = a[j ++ ];
        }
    }
    while (i <= mid) t[k ++ ] = a[i ++ ];
    while (j <= r) t[k ++ ] = a[j ++ ];

    for (int i = l, j = 0; i <= r; i ++ , j ++ ) a[i] = t[j];

    return res;
}

前缀和

一维

时间复杂度O(n)

1
2
3
4
5
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

//实现
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];

二维

时间复杂度O(n^2^)

1
2
3
4
5
6
7
8
9
10
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]

//实现
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];

printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);

差分

一维

时间复杂度O(1)

1
2
3
4
5
6
7
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

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

二维

时间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
给以(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 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;
}

二分

整数二分

时间复杂度O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool check(int x) {/* ... */} // 检查x是否满足某种性质

//找满足check的最小的一个数
int l = 0, r = n - 1;
while (l < r)
{
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
}

//找满足check的最大的一个数
l = 0, r = n - 1;
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check(mid)) l = mid;
    else r = mid - 1;
}

实数二分

时间复杂度O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

高精度

高精度加法

时间复杂度O(n)

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
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    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);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

//使用
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 -- ) printf("%d", C[i]);

高精度减法

时间复杂度O(n)

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
// 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, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> A, vector<int> B)
{
    int t = 0;
    vector<int> C;
    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;
    }
    //去掉前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

//使用
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
{
    putchar('-');
    C = sub(B, A);
}
for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);

高精度 * int

时间复杂度O(n)

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
// C = A * b, A >= 0, b >= 0
vector<int> mul_to_int(vector<int> A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        C.push_back(t % 10);
        t /= 10;
    }
    //去掉前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

//使用
int x;
cin >> a >> x;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
vector<int> C = mul_to_int(A, x);
for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);

高精度 * 高精度

时间复杂度O(n^2^)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> mul(vector<int> A, vector<int> B)
{
    vector<int> C(A.size() + B.size() + 10, 0);
    for (int i = 0; i < A.size(); i ++ )
        for (int j = 0; j < B.size(); j ++ )
            C[i + j] += A[i] * B[j];
    int t = 0;
    for (int i = 0; i < C.size(); i ++ )
    {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    //去掉前导零
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

//使用
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]);

高精度 / int

时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// A / b = C ... y, A >= 0, b > 0
vector<int> div(vector<int> A, int b, int &y)
{
    y = 0;
    vector<int> C;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        y =  y * 10 + A[i];
        C.push_back(y / b);
        y %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

//使用
int x = 0, y = 0;
cin >> a >> x;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
vector<int> C = div(A, x, y);
for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
puts("");
cout << y;

离散化

时间复杂度O(nlogn) 查找O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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, ...n
}

位运算

1
2
求n的第k位数字: n >> k & 1
返回n的最后一位1：n & -n

快读快写

慢

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
template<class T>
inline void read(T &x)
{
    int f = 1, c;
    while (c = getchar(), c < 48 || 57 < c)
        if (c == '-')
            f = -1;
    x = c ^ 48;
    while (c = getchar(), 47 < c && c < 58)
        x = (x << 3) + (x << 1) + (c ^ 48);
    x *= f;
}

template <typename T>
inline void print(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'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
56
57
typedef long long ll;
const ll MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? EOF : *p1++)
inline ll rd()
{
    ll x = 0, f = 1;
    char c = gc();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (isdigit(c))
        x = x * 10 + (c ^ 48), c = gc();
    return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
inline void push(const char &c)
{
    if (pp - pbuf == 1 << 20)
        fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
    *pp++ = c;
}
inline void write(ll x)
{
    if (x < 0)
        x = -x, push('-');
    static ll sta[35];
    ll top = 0;
    do
    {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top)
        push(sta[--top] + '0');
}
ll n;
signed main()
{
    n = rd();
    while (n)
    {
        ll m = min(10LL, n);
        ll x, sum = 0;
        for (ll i = 1; i <= m; ++i)
        {
            x = rd();
            sum += x;
        }
        n -= m;
        write(sum), push('\n');
    }
    fwrite(pbuf, 1, pp - pbuf, stdout);
    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
#include <iostream>
#include <ctime>

using namespace std;

//clock()返回当前时间  从第一次调用clock()开始计时
int start = clock();

//应用:算法执行接近1s后直接输出目前的答案
int main()
{
    for (int i = 0; ; i ++ )
    {
        //clock函数很慢, 减少clock函数调用
        //CLOCKS_PER_SEC返回当前系统下1s是多少个单位时间
        if (i % 10000000 == 0 && ((double)clock() - start) / CLOCKS_PER_SEC > 0.95)
        {
            printf("i 1s能自增%d次\n", i);
            printf("运行时间:%.5lfs\n", ((double)clock() - start) / CLOCKS_PER_SEC);
            break;
        }
    }

    return 0;
}