基础算法

快排调用

1
2
sort(a, a + n); // 默认从小到大
sort(a, a + n, cmp); // cmp是自定义比较函数

二分

1
2
3
4
5
6
7
l = 0, r = n - 1;

mid = l + r >> 1;
对应 r = mid, l = mid + 1;
mid = l + r + 1 >> 1;
对应 r = mid - 1, l = mid;
// 记忆：mid不加1,则l加1。

前缀和和差分

二维前缀和

1
2
3
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]

二维差分

比较巧妙：

如果q是全0的，那么其差分数组也是全0的，但实际上，q[i] = 0 + q[i]。（所以就相当于对一个元素的小区域实现了加c（即q[i]）的操作）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 实现对数组q的一块矩形区域的每个元素加c的操作，a是q的差分数组
void insert(int x1, int y1, int x2, int y2, int c)
{
    a[x1][y1] += c;
    a[x1][y2 + 1] -= c;
    a[x2 + 1][y1] -= c;
    a[x2 + 1][y2 + 1] += c;
}

// 构造a
for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> q[i][j];
            insert(i, j, i, j, q[i][j]);
        }

一般方法：

a是s的差分数组

1
2
3
4
5
6
for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ )
        a[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];

基本的位操作

看第k位是几

先移到最后一位：n >> k (k是从0开始，比如100中，1是第2位)

看个位是几：n & 1

综合：n >> k & 1

lowbit(x)，返回x的最后1的位置
1
2
3
4
5
6
7
实现：x&(~x+1)   (~x为x取反)

lowbit(n) = n & -n

lowbit(1010)=10

lowbit(1001000) = 1000

数据结构

数组模拟链表

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
// head表示头结点的下标
// e[i]表示节点i的值
// ne[i]表示节点i的next指针是多少
// idx存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}


// 将x这个点插到下标为k的点的后面
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}


// 将下标为k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

// 打印链表
for(int i = head; i != -1; i = ne[i])
    cout << e[i] << ' ';

Trie树

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
const int N = 100010;
// cnt最大长度是N，所有输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。
int son[N][26], cnt[N], idx; // idx下标为0的点，既是根结点，又是空结点
char str[N];

void insert(char str[])
{
    int p = 0; // 
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

主要工作：

  • 将两个集合合并
  • 询问两个元素是否在同一个集合中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int p[N]; //存储每个点的父节点

    // 返回x的祖宗节点
    int find(int x)  // 实现了路径压缩
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);

STL

vector
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
size(); // 元素个数

empty(); // 判空

clear();

A.push_back(t); // 向容器A尾部增加一个元素t

// 遍历
for(auto i = a.begin(); i != a.end(); i++)
    cout << *i << ' ';

// 遍历
for(auto& num : nums)
    cout << num << ' ';

// 对vector快排
sort(a.begin(), a.end());

// 定义一个与nums同样大小，并且初始值赋为0的vector
vector<int> res(nums.size(), 0);
pair

可以存储一个二元组，前后数据类型可以不同

1
2
3
4
5
6
pair<int, string> p;

p.first;
p.second;

typedef pair<int, int> PII;  // 常写在定义全局变量的地方
string
1
2
3
4
5
6
7
8
9
size()/length();
empty();

//支持加
string a = "yxc";
a += "def";

// 求子串
a.substr(1, 2); // 第一个参数是子串的起始位置，第二个参数是子串的长度，当第二个参数很大超出字符串时，就会输出到字符从最后一个字母为止
queue
1
2
3
4
5
6
7
8
9
10
push();
pop();
front();
back();
empty();
size();

// 队列没有clear函数，如果想要清空一个q，就重新构造就行了
queue <int> q;
q = queue<int>();
priority_queue

优先队列

是用堆来实现的，默认是大根堆（大的在队头）

1
2
3
4
5
6
7
8
push();
top(); // 返回堆顶元素
pop(); // 弹出堆顶元素

priority_queue<int> heap;

// 定义小根堆
 priority_queue<int, vector<int>, greater<int>> heap;
stack
1
2
3
4
5
size();
empty();
push();
top();
pop();

常用知识

取整

正数除以2是向下取整：5/2=2

负数是向0取整：-5/2=-2

将字符数字转换为int

1
2
3
char a;
int i;
i = a - '0';

max函数是max(a, b);

万能头文件：#include<bits/stdc++.h>

i++

1
2
3
4
a[4] = {1, 2, 3, 4};
int cnt = 0;
cout << a[cnt++] << endl;
// 结果是1
1
2
3
4
5
a[4] = {1, 2, 3, 4};
int cnt = 0;
a[cnt++] = 100;
cout << a[0] << endl;
// 结果是100

多个判断条件书写时

把可能越界的条件放在后面（这样就是后判断，可能不会判断就不会越界）

如lecctode 第27题 移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0, j = nums.size() - 1;
        while(i <= j)
        {
            // 换成while(nums[i] != val && i <= j)就ac不了
            // 原因是会出现数组访问越界，比如小于0或大于数组长度
            // 所以以后遇到有两个条件的判断时，把可能越界的条件放在后面（比如数组越界等）
            while(i <= j && nums[i] != val)
                i++;
            while(i <= j && nums[j] == val)
                j--;
            if(i < j)
                nums[i++] = nums[j--];
        }
        return i;
    }
};

整型最大最小量的使用

1
2
3
4
5
#include<climits>
// 或头文件
#include<limits.h>

INT_MAX, INT_MIN;

求最大公约数

1
2
3
int gcd(int m, int n) {
    return n ? gcd(n, m % n) : m;
}

求最小公倍数

1
(m*n)/gcd(m, n);

判断质数

1
2
3
4
5
6
7
8
9
bool is_prime(int x)
{
    // 0, 1既不是质数也不是合数
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

Devc++添加c++11

1
2
3
4
int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

时间复杂度

C/C++一秒钟可以算 \(10^8\)次（可以由此判断会不会超时）