模板

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
  
    int i=l-1,j=r+1,x=q[l+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);
}

归并排序

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

    int mid=l+r>>1;
    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]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];

    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];

    for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}

整数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int bsearch_1(int l,int r)
{
    while (l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }  
    return l;  
}

int bsearch_2(int l,int r)
{
    while (l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}

浮点数二分

1
2
3
4
5
6
while (r-l>eps)
{
    double mid=(l+r)/2;
    if(chack(mid)) r=mid;
    else l=mid;
}

位运算

1
2
3
4
int lowbit(int x)
{
    return x&-x;
}

1010010000返回10000

1110110100返回100

双指针

1
2
3
4
5
6
7
8
9
10
for(int i=0,j=  ; i<n ; i++)
{
    while(cheak(i,j))
    {
        /*

                */
        j++;
    }
}

数组模拟

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int head, e[N], ne[N], idx;

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

void insert(int a)      //插入头结点  
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

void remove()           //删除头结点
{
    head = ne[head];
}

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void init()             //初始化
{
    //0是左端点，1是右端点
    r[0]=1,l[1]=0;
    idx=2;
}

void insert(int a, int x)   //在节点a的右边插入一个数x
{
    e[idx]=x;
    l[idx]=a;
    r[idx]=r[a];
    l[r[a]]=idx;
    r[a]=idx;
    idx++;
}

void remove(int a)          //删除节点a
{
    l[r[a]]=l[a];
    r[l[a]]=r[a];
}

栈

1
2
3
4
5
6
7
8
9
10
void init()
{
    tt=-1;
}

    stk[++tt]=x;            //向栈顶插入一个数

    tt--;                   //从栈顶弹出一个数

    stk[tt];                //栈顶的值

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
while (n--)
    {
        cin>>x;
        while (tt>=0&&stk[tt]>=x)
        {
            tt--;
        }
        if(tt<0) cout<<"-1"<<endl;
        else cout<<stk[tt]<<endl;

        stk[++tt]=x;
    }

队列

1
2
3
4
5
6
7
8
9
10
11
void init()
{
    hh=0;               //hh表示队头
    tt=-1;              //tt表示队尾
}

q[++tt]=x;              //向队尾插入一个数

    hh++;               //从队头弹出一个数

    q[hh];              //队头的值

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(int i=0;i<n;i++)                //递增
{
    if(hh<=tt&&i-k+1>q[hh]) hh++;

    while (hh<=tt&&a[q[tt]]>=a[i]) 
    {
      
        tt--;
    }
    q[++tt]=i;
}


for(int i=0;i<n;i++)                //递减
{
    if(hh<=tt&&i-k+1>q[hh]) hh++;

    while (hh<=tt&&a[i]<=a[q[tt]]) 
    {
      
        tt--;
    }
    q[++tt]=i;
}

KMP 算法

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
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+10;
int ne[N];
int main()
{
    char s[N],p[N];
    cin>>s+1>>p+1;                      //下标都从1开始
    int n=strlen(p+1);                  //注意用法
    int m=strlen(s+1);

    for(int i=2,j=0;i<=n;i++)           //求next数组
    {
        while (j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }

    for(int i=1,j=0;i<=m;i++)           //匹配
    {
        while (j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n)                        //匹配成功
        {
            cout<<i-j+1<<endl;
        }
    }
    return 0;
}

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
int son[N][26];                         //存储每个节点的子节点
int cnt[N];                             //存储以该节点结尾的字符串数量
int idx;

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
15
16
17
18
19
    p[x]=y;                                 //x的父节点是y

int find(int x)                             //查找祖宗节点并压缩
{
  
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

for(int i=1;i<=n;i++)                       //初始化，每个节点都是自己的祖宗节点，该集合元素个数为1
{
    p[i]=i;
    size[i]=1;                              //size只对根节点有意义
}

size[find(b)]+=size[find(a)];               //将x的祖宗节点接到y的祖宗节点上并且计算新 size 
p[find(a)]=find(b);                         //必须先计算再连接！！！

find(x)==find(y);                           //x和y属于同一个集合

带权并查集（增加距离变量）

1
2
3
4
5
6
7
8
9
10
int find(int x)
{
    if(p[x]!=x)
    {
        int t=find(p[x]);
        d[x]+=d[p[x]];      //d[x]在过程中只代表到他父节点的距离（画图/后续连接时只会改变d[px],而d[x]不变，所以得这样写
        p[x]=t;
    }
    return p[x];
}

堆

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
// h[N]存储堆中的值, h[1]是堆顶（最小值），x的左儿子是2x, 右儿子是2x+1
void down(int u)
{
    int t=u;
    if(2*u<=size&&h[2*u]<h[t])      t=2*u;
    if(2*u+1<=size&&h[2*u+1]<h[t])   t=2*u+1;
    if(t!=u) 
    {
        swap(h[u],h[t]);
        down(t);
    }
}


void up(int u)
{
    while (u/2&&h[u]>h[u/2])
    {
        swap(h[u],h[u/2]);
        u=u/2;
    }
}


    for(int i=n/2;i;i--)            //O(n)建堆
    {
        down(i);
    }

第 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
32
33
int h[N];
int hp[N];          //hp[i] 存储堆中下标是 i 的点是第几个插入的?
int ph[N];          //ph[i] 存储第 i 个插入的点在堆中的下标?
int size;
int m;

void head_swap(int i,int j)             //传堆中下标（下同）
{
    swap(h[i],h[j]);
    swap(ph[hp[i]],ph[hp[j]]);
    swap(hp[i],hp[j]);
}

void down(int u)
{
    int t=u;
    if(2*u<=size&&h[2*u]<h[t])      t=2*u;
    if(2*u+1<=size&&h[2*u+1]<h[t])  t=2*u+1;
    if(t!=u)
    {
        head_swap(t,u);
        down(t);
    }
}

void up(int u)
{
    while (u/2&&h[u]<h[u/2])
    {
        head_swap(u,u/2);
        u=u/2;
    }
}

哈希表

一般哈希

1. 拉链法：

每个 h[i] 接着一个单链表

N为一个质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int h[N], e[N], ne[N], idx;

memset(h,-1,sizeof h);             //若h[i]不是-1，则有“拉链”

void insert(int x)                  //插入一个数
{
    int k=(x%N+N)%N;
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx;
    idx++;
}


bool query(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;
}
2. 开放寻址法：

N大概为2倍大小的一个质数

1
2
3
4
5
6
7
8
9
10
11
12
13
const int N=200003;
const int null=0x3f3f3f3f;           //0x3f类比无穷大又不溢出
int h[N];

int find(int x)                     //如果x在哈希表中，返回x的下标，如果x不在哈希表中，返回x应该插入位置的下标
{
    int k=(x%N+N)%N;
    while (h[k]!=null&&h[k]!=x)
    {
        k=(k+1)%N;
    }
    return k;
}

字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef unsigned long long ULL;
const int P=131;                    //P一般为131或者13331
const int N=100003;
ULL h[N],p[N];

ULL match(int l,int r)              //计算子串 str[l ~ r] 的哈希值
{
    return h[r]-h[l-1]*p[r-l+1];    //P进制
}


    p[0]=1;
for(int i=1;i<=n;i++)               //初始化
{
    p[i]=p[i-1]*P;
    h[i]=h[i-1]*P+str[i-1];
}

STL

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反