基础

排序

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void mergesort(int l, int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    int p = l, q = mid + 1, cnt = l;
    while(p <= mid && q <= r){
        if(a[p] < a[q]) t[cnt++] = a[p++];
        else t[cnt++] = a[q++];
    }
    while(p <= mid) t[cnt++] = a[p++];
    while(q <= r) t[cnt++] = a[q++];
    for(int i = l; i <= r; ++i) a[i] = t[i];
}
1
2
3
4
5
6
7
8
9
10
bool dfs(int x) {
	vis[x] = -1;
	for (int y : G[x]) {
		if (vis[y] == -1) return false; // 存在环
		else if (!vis[y] && !dfs(y)) return false;
	}
	vis[x] = 1;
	a[++cnt] = x;
	return true;
}

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int head[N], nxt[N], ver[N], deg[N], tot, cnt;

inline void add(int x, int y) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
    deg[y]++;
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        a[++cnt] = x;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (--deg[y] == 0) q.push(y);
        }
    }
}

数学

素数

  • \(Eratosthenes\)筛法
1
2
3
4
5
6
7
8
9
//O(nloglogn)
void sieve() {
    memset(v, 0, sizeof(v));
    for (int i = 2; i < N; ++i) {
        if (v[i]) continue;
        p[++cnt] = i;
        for (int j = i; j < N / i; ++j) v[i*j] = 1;
    }
}
  • 线性筛法
1
2
3
4
5
6
7
8
9
10
11
//O(n)
void sieve() {
    memset(v, 0, sizeof(v));
    for (int i = 2; i < N; ++i) {
        if (!v[i]) p[++cnt] = i;
        for (int j = 1; j <= cnt && p[j] * i < N; ++j) {
            v[i*p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

欧几里得

1
2
3
4
5
6
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

扩展欧几里得

  在求出\(gcd(a,b)\)的同时求出二元一次不定方程\(ax+by=gcd(a,b)\)的一组整数解

1
2
3
4
5
6
7
void exgcd(int a, int b, int &x, int &y) {
    if (!b) x = 1, y = 0;
    else {
        exgcd(b, a % b, x, y);
        y -= a / b * y;
    }
}

乘法逆元

模板题

  • 拓欧

  若 \(a\cdot x\equiv1{\pmod b}\)，\(a\) 与 \(b\) 互质，则 \(x\) 为 \(a\) 的逆元，记为 \(a^{-1}\)，也称 \(x\) 为 \(a\) 在 \(\mathrm{mod}\ b\) 下的倒数。

  利用拓欧求解 \(a\cdot x\equiv1{\pmod b}\) 转化为求解 \(a\cdot x+b\cdot y = 1\)。

1
2
3
4
5
6
7
void exgcd(int a, int b, int &x, int &y) {
	if (!b) x = 1, y = 0;
	else exgcd(b, a % b, y, x), y -= a / b * x;
}

exgcd(i, p, x, y);
x = (x % p + p) % p;
  • 费马小定理

  若 \(p\) 为素数，\(a\) 为正整数，且 \(a\)、\(p\) 互质，则 \(a^{p-1}\equiv1{\pmod p}\)

  对于 \(a\cdot x\equiv1\pmod p\)，有 \(a\cdot x\equiv a^{p-1}\pmod p\)，即 \(x\equiv a^{p-2}\pmod p\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll qpow(ll a, ll b, ll MOD) {
	ll res = 1;
	for (; b; b >>= 1, (a *= a) %= MOD)
		if (b & 1) (res *= a) %= MOD;
	return res;
}

void write(ll x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 ^ 48);
}

write(qpow(i, p - 2, p)), puts("");
  • 线性方法

  要求一串数字对 \(\mathrm{mod}\ p\) 的逆元，设 \(p=k\cdot i+r\quad(1\lt r\lt i\lt p)\)，则

\[k\cdot i+r\equiv0\pmod p\]

乘 \(i^{-1},r^{-1}\) 移项得

\[i^{-1}\equiv-k\cdot r^{-1}\pmod p\]

\[i^{-1}\equiv-\lfloor\frac{p}{i}\rfloor\cdot(p\ \mathrm{mod}\ i)^{-1} \pmod p\]

1
2
3
inv[1] = 1;
for (int i = 2; i <= n; ++i)
	inv[i] = (p - p / i) * inv[p % i] % p;
  • 阶乘逆元 \(O(n)\)

若 \(inv[i]=\frac{1}{(i+1)!}\)，则 \(inv[i+1]\times(i+1)=inv[i]\)

\[\frac{1}{i!}\times(i-1)!\equiv\frac{1}{i}\pmod p\]

1
2
3
4
5
6
7
8
f[0] = 1;
for (ll i = 1; i <= n; ++i)
	f[i] = (f[i-1] * i) % p;
inv[n] = qpow(f[n], p - 2, p);
for (ll i = n - 1; i >= 1; --i)
	inv[i] = (inv[i+1] * (i + 1)) % p;
for (int i = 1; i <= n; ++i)
	printf("%lld\n", (inv[i] * f[i-1]) % p);

欧拉函数

  我们知道\(\varphi(n)\)表示小于\(n\)且与\(n\)互素的整数个数, 而\(n\)可分解为\(n=\displaystyle\prod_{i=1}^kp_i^{a_i}\), 根据容斥原理我们有

\[\varphi(n)=\sum_{S\subseteq\left\{p_1,p_2,\cdots,p_k\right\}}(-1)^{|S|}\frac{n}{\displaystyle\prod_{p_i\in S}p_i}\]

  展开后可以得到

\[\varphi(n)=n*\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)\]

  1. 若\(n\)是素数 , 有\(\varphi(n)=n−1\)
  2. 若\(gcd(n,m)=1\), 有\(\varphi(mn)=\varphi(m)\varphi(n)\)
  3. 若\(n\)和\(m\)是素数 , 有\(\varphi(nm)=nm−1\)
  4. 若\(p\)是素数 , 有\(\varphi(p^q)=p^q−p^{q−1}\)
  5. \(\displaystyle\sum_{d|m}\varphi(d)=m\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//单个Euler函数值
int phi(int n) {  
	int res = n;  
	for (int i = 2; i * i <= n; ++i) {
		if (n % i == 0) { 
			res -= res / i; 
			while (n % i == 0) n /= i; 
		}
	}
	if (n > 1) res -= res / n; 
	return res;  
}
//O(nlogn)
void euler(int n) {
	for (int i = 1; i <= n; ++i) phi[i] = i;
	for (int i = 2; i <= n; ++i)
		if (phi[i] == i)
			for (int j = i; j <= n; j += i)
				phi[j] = phi[j] / i * (i - 1);
}

数据结构

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = root;
}

void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
}

图论

最短路

\(dijkstra\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n, m, s;
int a[N][N], d[N], pre[N], vis[N];

void dijkstra() {
    for (int i = 1; i <= n; ++i) {
        d[i] = INF; vis[i] = 0; pre[i] = -1;
    }
    d[s] = 0;
    for (int i = 1; i < n; ++i) {
        int x = -1;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && (x == -1 || d[j] < d[x])) x = j;
        vis[x] = 1;
        for (int y = 1; y <= n; ++y)
            if (d[y] > d[x] + a[x][y]) {
                d[y] = d[x] + a[x][y];
                pre[y] = x;
            }
    }
}

\(dijkstra(堆优化)\)

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
struct Edge
{
    int next, to, w;
}e[M];

inline void add(int x, int y, int z)
{
    e[++tot].w = z;
    e[tot].next = head[x];
    e[tot].to = y;
    head[x] = tot;
}

void dijkstra()
{
    d[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].to;
            if (d[y] > d[x] + e[i].w) {
                d[y] = d[x] + e[i].w;
                q.push(make_pair(-d[y], y));
            }
        }
    }
}

\(spfa\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void spfa() {
    queue<int> q;
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    d[1] = 0; v[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        v[x] = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                if (!v[y]) q.push(y), v[y] = 1;
            }
        }
    }
}

最小生成树

\(Kruskal\)算法

  比较适合于稀疏图

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
const int N = 5005;
const int M = 2e5 + 5;
int n, m, f[N];
struct edge
{
    int u, v, w;
    friend bool operator < (edge a, edge b) {
        return a.w < b.w;
    }
}e[M];

int find(int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}

int krusal() {
    sort(e + 1, e + m + 1);
    int cnt = 0, ans = 0;
    for (int i = 1; i <= n; ++i) f[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x = find(e[i].u);
        int y = find(e[i].v);
        if (x != y) {
            ans += e[i].w;
            f[x] = y;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    if (cnt < n - 1) return -1; //不连通
    return ans;
}

\(Prim\)算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 5005;
int n, m, ans;
int a[N][N], d[N], v[N];

void prim() {
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    for (int i = 1; i <= n; ++i) {
        int x = 0;
        for (int j = 1; j <= n; ++j)
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int y = 1; y <= n; ++y)
            if (!v[y]) d[y] = min(d[y], a[x][y]);
    }
}

提高

图论

网络流初步

Edmonds-Karp

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
int n, m, s, t, maxflow, tot = 1;
int ver[M], edge[M], Next[M], head[N], v[N], incf[N], pre[N];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}

bool bfs() {
    memset(v, 0, sizeof(v));
    queue<int> q;
    q.push(s); v[s] = 1;
    incf[s] = INF;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = Next[i])
            if (edge[i]) {
                int y = ver[i];
                if (v[y]) continue;
                incf[y] = min(incf[x], edge[i]);
                pre[y] = i;
                q.push(y);
                v[y] = 1;
                if (y == t) return 1;
            }
    }
    return 0;
}

void EK() {
    while (bfs()) {
        int x = t;
        while (x != s) {
            int i = pre[x];
            edge[i] -= incf[t];
            edge[i^1] += incf[t];
            x = ver[i^1];
        }
        maxflow += incf[t];
    }
}

Dinic

1
2


附录

对拍

\(bat\)语言版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@echo off
set cnt=0
for /l %%i in (1,1,10) do (
  mine.exe < stdin%%i.txt > out%%i.txt
  fc out%%i.txt stdout%%i.txt > diff%%i.txt
  if errorlevel 1 (
    set cnt=1
    echo %%i:UnAccepted!
  )
  if not errorlevel 1 (
    del diff%%i.txt
    echo %%i:Accepted!
  )
)
if %cnt%==0 color a && echo *** Totally Accepted! ***
if %cnt%==1 color c && echo *** Not All Accepted! ***
pause

vim配置

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
syntax enable
syntax on

set nu
set ruler
set cul
set tabstop=4
set shiftwidth=4
set expandtab
set autoindent
set nobackup
set paste
set incsearch
set showcmd
set showmatch
set ignorecase
set cin
colo evening
set mouse=a

nnoremap <F9> :call CompileRun()<CR>
func! CompileRun()
    exec "w"
    if &filetype is 'cpp' || &filetype is 'c' || &filetype is 'cc'
        exec "!g++ -Wall % -0 %<"
        exec "!time ./%<"
    elseif &filetype is 'java'
        exec "!javac\ -d\ .\ %"
        exec "!javac\ %<"
    endif
endfunc


call plug#begin('~/.vim/plugged')

Plug 'itchyny/lightline.vim'
Plug 'SirVer/ultisnips'
Plug 'honza/vim-snippets'
Plug 'preservim/nerdtree'                      " 目录树
Plug 'tiagofumo/vim-nerdtree-syntax-highlight' " 目录树美化
Plug 'vim-airline/vim-airline'                 " 状态栏美化
Plug 'vim-airline/vim-airline-themes'          " 状态栏美化主题
Plug 'scrooloose/syntastic'                    " 语法错误提示
Plug 'suan/vim-instant-markdown'               " markdown 实时预览
Plug 'ryanoasis/vim-devicons'

call plug#end()