系统为某一程序分配空间所需时间，与空间大小无关，与申请次数有关！

哈希

  • 存储结构（一般只有添加和查找操作，如果要删，在点上打一个标记即可）
    • 拉链法（槽+链表） 
       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

      #include <iostream>
using namespace std;

const int N=100003;
int h[N], e[N], ne[N], idx;

void insert(int x){
    int k = (x % N + N) % N; // 让余数为正
    e[idx] = x;  //新点的真正存储位置
    ne[idx] = h[k];  //新点的next指针指向h[k](指向的点)
    h[k] = idx ++;  //h[k]指向新点
}

bool find(int x){
    int k = (x % N + N) % N; 
    for (int i = h[k]; i != -1; i = ne[i]){
        if (e[i] == x) return true;
    }
    return false;
}

int main(){
    bool flag = true;
    for (int i = 100000;; i++){
        for (int j=2; j*j<=i; j++){
            if (i % j == 0){
                flag = false;
                break;
            }
        }
        if (flag == false) {
            cout << i << endl;
            break;
        }
    }

    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h );

    while(n--){
        char op[2];
        int x;
        int scanf("%s%d", op, &x);

        if (*op == 'I') insert(x);
        else{
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
    • 开放寻址法（一般初始化两倍大小的数组）：插入——从第k个坑位开始，如果有人，则往后，遇到没人的插入；查找——从第k个坑位开始，如果有人，就判断；如果没人，说明查找失败 
       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

      #include <iostream>
using namespace std;

const int N=200003, null = 0x3f3f3f3f;
int h[N];

int find(int x){
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x){
        k ++;
        if (k == N) k = 0;
    }
    return k;
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x);
        if (*op == 'I') h[k] = x;
        else{
            if (h[k] != null) puts("Yes");
            else puts("No");
        }
    }
}
  • 字符串前缀哈希法
    • 预处理出所有前缀的哈希，h[i]=str(0:i-1)的哈希值
    • 讲字符串表示成一个p进制的数 “ABDC"→(1,2,3,4)_p = (p^3+2p^2+3p+4) mod Q
    • 一般不把字母映射成0 $$ \text{L到R这段的哈希值: }h[R]-h[L-1]*p^{R-L+1} $$ O(1)时间求某一段的哈希值

C++ STL

  • vector，变长数组，倍增的思想
    • size(), empty(), clear()
    • front(), back()
    • push_back(), a.pop_back()
    • begin(), end()
  • pair<int, int>
    • first(), second(), 支持比较运算，以first为第一关键字，second为第二关键字
  • string，字符串，substr(), c_str()
    • size(), length(), empty(), clear()
  • queue，队列
    • push(), front(), back(), pop()
    • size(), empty()
  • qriority_queue，优先队列（默认是大根堆）
    • push(), top(), pop(), clear()
    • 定义小根堆 priority_queue<int, vector, greater> heap;
  • stack，栈
    • push(), top(), pop()
    • size(), empty()
  • deque，双端队列（效率很低，比数组慢）
    • size(), empty(), clear();
    • front(), back()
    • push_back(), pop_back()
    • push_front(), pop_front()
    • begin(), end()
  • set, map, multiset, multimap，基于平衡二叉树（红黑树）动态维护有序序列
    • size(), empty(), clear()
    • set/multiset:
      • insert(), find(), count(),
      • erase() — 输入是一个数x, 删除所有x O(k+lgn)；输入是一个迭代器，删除这个迭代器
      • lower_bounder(x) — 返回大于等于x的最小的数的迭代器
      • upper_bound(x) — 返回大于x的最小的数的迭代器
    • mapmultimap
      • insert() — 插入的是pair, erase() — 输入是pair或者迭代器
  • unordered_set, unordered_map, unordered_multiset, unordered_multimap，哈希表
    • 和上面类似，增删改查时间复杂度为O(1)
    • 不支持lower_bounder和upper_bound，以及迭代器的++/- -
  • bitset，压位
    • 可以省8倍空间
    • bitset<10000> s — <>里是长度
    • ~, &, |, ^
    • «, »
    • ==, ! =
    • count() — 返回有多少个1
    • any() — 判断是否至少有一个1, none() — 判断是否全为0
    • set() — 把所有位置成1, set(k, v)
    • reset() — 把所有位置成0
    • flip() — 所有位取反