$dsu\ on\ tree$($disjoint\ set\ union\ \text{on tree}$)算法，也称 __树上并查集__。使用了并查集的按秩合并(启发式合并)的方法，结合 树链剖分 中的 轻重儿子划分 ，对 树上暴力统计 进行了优化。使用这个算法需要满足以下两个条件：

阅读全文

2019-06-09发表2020-05-05更新C++算法 / 笔记 / 数据结构6 分钟读完 (大约862个字)

「数据结构」线段树

线段树($Segment\ Tree$)是一种基于分治思想的__二叉树__形数据结构，可以用于__区间__上的数据维护，它可以维护以下值

阅读全文

2019-06-09发表2020-05-05更新C++算法 / 笔记 / 数据结构4 分钟读完 (大约538个字)

「数据结构」左偏树(可并堆)

左偏树($Leftist\ Tree$)，是一种 __可以合并的堆状结构__，支持以下操作

阅读全文

2019-06-09发表2020-05-05更新C++算法 / 笔记 / 数据结构3 分钟读完 (大约512个字)

「数据结构」树状数组

树状数组($Binary\ Indexed\ Trees$)是一个维护__前缀和__的数据结构，需要支持以下操作

阅读全文

2019-06-09发表2020-05-05更新C++算法 / 笔记 / 数据结构5 分钟读完 (大约719个字)

「数据结构」并查集

并查集($union-find\ \ set$)是一种可以__动态维护__若干个不重叠的__集合__，并支持__合并与查询__的数据结构，支持以下两种基本操作：

阅读全文

2019-05-08发表2021-07-07更新C++算法 / 笔记9 分钟读完 (大约1321个字)

算法笔记-数论

模板地址: GitHub

欧几里得算法(Euclid algorithm)

1
2
3

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

lcm(a, b) = a / gcd(a, b) * b

扩展欧几里得算法(exGCD)

目标: 寻找一对整数$(x, y)$,使$ax+by=gcd(a,b)$

void exgcd(LL a, LL b, LL& d, LL& x, LL& y) {
    if (!b) { d = a; x = 1; y = 0; }  //d为gcd(a, b)
    else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }
}

裴蜀定理

$ax+by=c$且$x,y$全为正整数,则当且仅当$gcd(a, b)|c$

素数相关

Eratosthenes筛法

bool vis[maxn];
int prime[maxn];
void getprime(int n) {
    int m = (int)sqrt(n + 0.5), num = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= m; ++i) if (!vis[i]) {
        prime[++num] = i;
        for (int j = i * i; j <= n; j += i) vis[j] = 1;
    }
}

欧拉线性筛

void getprime(int n) {
    vis[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            int v = i * prime[j];
            if (v > n) break;
            vis[v] = true;
        }
    }
}

素数定理

$$
\pi(x) \sim \frac{x}{\ln x}
$$

$Miller-Rabin$素数测试

原理:费马小定理
若$a^{n-1}\equiv 1\pmod n$,$a$取值越多,可以近似认为$n$为质数
使用二次探测定理改进卡卡迈尔数(合数$n$对于任何正整数$b$,都满足$gcd(b, n)=1\ \ b^{n-1}\equiv 1\pmod n$)的bug

LL Random(LL n) { return (LL)((double)rand() / RAND_MAX * n + 0.5); }
bool Witness(LL a, LL n) {
    LL m = n - 1; int j = 0;
    while (!(m & 1)) { j++; m >>= 1; }
    LL x = pow_mod(a, m, n);
    if (x == 1 || x == n - 1) return false;
    while (j--) { x = x * x % n; if (x == n - 1) return false; }
    return true;
}
bool Miller_Rabin(LL n) {
    if (n < 2) return false; if (n == 2) return true;
    if (!(n & 1)) return false;
    for (int i = 1; i <= 30; ++i) {
        LL a = Random(n - 2) + 1;
        if (Witness(a, n)) return false;
    }
    return true;
}

模算术

$$
(a + b)\bmod n = ((a\bmod n) + (b\bmod n))\bmod n\\
(a - b)\bmod n = ((a\bmod n) - (b\bmod n) + n)\bmod n\\
ab\mod n = (a\bmod n)(b\bmod n)\bmod n
$$

快速乘 $ab\bmod n$

LL mul_mod(LL a, LL b, LL n){
    LL res = 0;
    while (b > 0) {
        if (b & 1) res = (res + a) % n;
        a = (a + a) % n;
        b >>= 1;
    }
    return res;
}

快速幂 $a^p\bmod n$

LL pow_mod(LL a, LL p, LL n) {
    if (p == 0 && n == 1) return 0;
    if (p == 0) return 1;
    LL ans = pow_mod(a, p / 2, n); ans = ans * ans % n;
    if (p % 2 == 1) ans = ans * a % n;
    return ans;
}

使用位运算:

LL pow_mod(LL a, LL p, LL n) {
    a %= n; LL ans = 1;
    for (; p; p >>= 1, a *= a, a %= n) if(p & 1) ans = ans * a % n;
    return ans;
}

欧拉$\varphi$函数

$$\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$$
$\varphi(n)$表示不超过$n$且与$n$互质的整数个数

求值

int euler_phi(int n) {
    int m = (int)sqrt(n + 0.5); int ans = n;
    for (int i = 2; i <= m; ++i) if (n % i == 0) {
        ans = ans / i * (i - 1);
        while (n % i == 0) n /= i;
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

筛欧拉函数表

int phi[maxn];
void phi_table(int n) {
    for (int i = 2; i <= n; ++i) phi[i] = 0; phi[1] = 1;
    for (int i = 2; i <= n; ++i) if (!phi[i])
        for (int j = i; j <= n; j += i) {
            if (!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i - 1);
        }
}

同余式定理

欧拉定理

若$gcd(a, n) = 1$,则$a^{\varphi(n)}\equiv 1\pmod n$

费马小定理

若$p$为质数,则$a^{p-1}\equiv 1\pmod p$

威尔逊定理

若$p$为质数,则$(p-1)!\equiv -1\pmod p$

乘法逆元

$$a\div b\bmod n = a\times b^{-1}\bmod n$$
$b^{-1}$称为$b$在模$n$意义下的逆元

$n$为质数

使用费马小定理, $a^{-1} = a^{n - 2}$

$n$不为质数

递归求解

LL inv(LL a, LL n) {
    LL d, x, y;
    exgcd(a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}

筛逆元表

int inv_table[maxn];
void getinv(int n, int p) {
    inv_table[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv_table[i] = (LL)(p - p / i) * inv_table[p % i] % p;
    }
}

同余方程

$ax\equiv b\pmod n$可以化为$ax+ny=b$使用扩展欧拉定理解决

中国剩余定理(China Remainder Theorem)

求解$x\equiv a_i\pmod {m_i}$满足$m_i$两两互质

LL crt(int n, int* a, int* m) {
    LL M = 1, d, y, x = 0;
    for (int i = 0; i < n; ++i) M *= m[i];
    for (int i = 0; i < n; ++i) {
        LL w = M / m[i];
        exgcd(m[i], w, d, d, y);
        x = (x + y * w * a[i]) % M;
    }
    return (x + M) % M;
}

扩展中国剩余定理(exCRT)

$m_i$不一定两两互质

LL excrt(LL n, LL* a, LL* m) {
    LL x, y, k, M = m[0], ans = a[0];
    for (int i = 1; i < n; ++i) {
        LL A = M, B = m[i], C = (a[i] - ans % B + B) % B, gcd;
        exgcd(A, B, gcd, x, y);
        LL bg = B / gcd;
        if (C % gcd != 0) return -1;
        x = mul_mod(x, C / gcd, bg);
        ans += x * M; M *= bg;
        ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
}

离散对数(BSGS)

求解$a^x\equiv b\pmod n$满足$n$为质数

int log_mod(int a, int b, int n) {
    int m, v, e = 1, i;
    m = (int)sqrt(n + 0.5);
    v = inv(pow_mod(a, m, n), n);
    map<int, int> x;
    x[1] = 0;
    for (i = 1; i < m; ++i) {
        e = mul_mod(e, a, n);
        if (!x.count(e)) x[e] = i;
    }
    for (i = 0; i < m; ++i) {
        if (x.count(b)) return i * m + x[b];
        b = mul_mod(b, v, n);
    }
    return -1;
}

莫比乌斯反演

整除分块

整除分块可以对后面的莫比乌斯反演提供很大的优化
通过枚举可以发现$\lfloor \frac{n}{i} \rfloor$的结果会出现分块现象
例如$n=10$时
$\ \ \ i\ \ \ \ 1\ \ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ …$
$\lfloor \frac{n}{i} \rfloor\ 10\ 5\ 3\ 2\ 2\ 1\ 1\ 1\ 1\ 1\ \ \ 0\ \ \ 0\ \ \ 0\ \ \ …$
~~不难发现~~,每个块的右端点为$r=\lfloor \frac{n}{t}\rfloor (t=\lfloor \frac{n}{i}\rfloor)$

莫比乌斯函数

$$
\mu(n) =
\begin{cases}
1, & n=1 \\
(-1)^r, & n=p_1p_2p_3…p_r(\text{$p_i$为互不相同的质数}) \\
0, & else
\end{cases}
$$
性质:
$$\sum_{d|n}{\mu(d)}=[n=1]$$
$$\sum_{d|n}{\frac{\mu(d)}{d}}=\frac{\varphi(n)}{n}$$
线性筛:

int mu[maxn], vis[maxn];
int primes[maxn], cnt;
void get_mu(int n) {
	memset(vis, 0, sizeof(vis));
	memset(mu, 0, sizeof(mu));
	cnt = 0; mu[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) { primes[cnt++] = i; mu[i] = -1; }
		for (int j = 0; j < cnt && primes[j] * i <= n; ++j) {
			vis[primes[j] * i] = 1;
			if (i % primes[j] == 0)break;
			mu[i * primes[j]] = -mu[i];
		}
	}
}

2019-04-30发表2020-05-05更新C++算法7 分钟读完 (大约1049个字)

Cpp算法-网络流相关

网络流算法相关模板,讲解__以后再说吧__,咕咕咕

阅读全文

2019-04-30发表2020-05-05更新C++算法 / 笔记15 分钟读完 (大约2219个字)

算法笔记-计算几何

啥也不说了,直接上代码,每个函数功能已经以注释方式给出

阅读全文

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约164个字)

Cpp算法-并查集

说明

n, m, q点数、边数、问题数
x, y需要合并的两个数
ufs[]并查集
find(int)查找并查集中一个数的祖先
unionn(int, int)合并两个数所在集合

实现

const int maxn = 10010;
int ufs[maxn];
int n, m, x, y, q;

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

void unionn(int x, int y)
{
    int fx = find(x);
    int fy = find(y);
    if (fx != fy)
    {
        ufs[fx] = fy;
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) ufs[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d %d", &x, &y);
        unionn(x, y);
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i)
    {
        scanf("%d %d", &x, &y);
        if (find(x) == find(y)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

2019-01-10发表2020-05-05更新C++算法2 分钟读完 (大约309个字)

Cpp算法-STL标准库

模板

template <typename T>
/**
 * 写函数/结构体
 */

例

template <typename T>
struct Point
{
    T x, y;
    Point(T x = 0, T y = 0):x(x), y(y) {}
};

template <typename T>
Point<T> operator + (const Point<T>& A, const Point<T>& B)
{
    return Point<T>(A.x + B.x, A.y + B.y);
}

template <typename T>
ostream& operator << (ostream& out, const Point<T>& p)
{
    out << "(" << p.x << "," << p.y << ")";
    return out;
}

vector(不定长数组)

声明

vector<数据类型> 名; 例 vector<int> a;

简单用法

a.size();读取大小

a.resize();改变大小

a.push_back(x);尾部添加元素x

a.pop_back();删除最后一个元素

a.clear();清空

a.empty()询问是否为空(bool类型)

a[]访问元素(可修改)

priority_queue(优先队列/堆)

声明

头文件: #include <queue>

参数: priority_queue<Type, Container, Functional>

Type数据类型 不可省

Container容器(vector,deque)默认vector

Functional比较方式,默认operator <大根堆

使用

与queue类似

小根堆

priority_queue<int, vector<int>, greater<int> > q;使用仿函数greater<>

自定义类型(struct)

struct Node
{
    int x, y;
    Node(int a = 0, int b = 0):x(a), y(b){}
};

重载operator <

bool operator < (Node a, Node b)
{
    if (a.x == b.x) return a.y > b.y;
    return a.x > b.x;
}

priority_queue<Node> q;

x值大的优先级低,排在队前

x相等,y大的优先级低

重写仿函数

struct cmp
{
    bool operator () (Node a, Node b)
    {
        if (a.x == b.x) return a.y > b.y;
        return a.x > b.x;
    }
}

priority_queue<Node, vector<Node>, cmp> q;

2019-01-10发表2020-05-05更新C++算法8 分钟读完 (大约1223个字)

Cpp算法-背包问题

01背包问题

有 $n$ 件物品，和一容积为 $V$ 的背包，第 $i$ 件物品的体积为 $w_i$ ，价值为 $c_i$ 。将第几件物品装入，使体积不超过总体积，且价值和最大，求最大价值。

由题意易知状态转移方程： $F_{i,j} = max(F_{i-1,j}\ , F_{i-1,j-w_i} + c_i)$

$F_{i, j}$ 为前 $i$ 件物品放入容量为 $V$ 的背包中最大价值

时间复杂度 $O(n\times V)$ ，空间复杂度 $O(n\times V)$

框架

注意倒序，保证f[n][V]为结果

for (int i = 1; i <= n; ++i)
{
    for (int j = V; j >= w[i]; --j)
    {
        f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);
    }
}
printf("%d", f[n][V])

空间复杂度优化

降至一维数组

时间复杂度 $O(n\times V)$ ，空间复杂度 $O(V)$

for (int i = 1; i <= n; ++i)
{
    for (int j = V; j >= w[i]; --j)
    {
        f[j] = max(f[j], f[j - w[i]] + c[i]);
    }
}
printf("%d", f[V]);

完全背包问题

有 $n$ 种物品（每种 无限件 ），和一容积为 $V$ 的背包，第 $i$ 种物品的体积为 $w_i$ ，价值为 $c_i$ 。将第几种物品取任意件装入，使体积不超过总体积，且价值和最大，求最大价值。

将01背包第二个循环改为正序即可

状态转移方程：$F_j = max(F_j\ , F_{j-w_i}+c_i)$

框架

for (int i = 1; i <= n; ++i)
{
    for (int j = w[i]; j <= V; ++j)
    {
        f[j] = max(f[j], f[j - w[i]] + c[i]);
    }
}
printf("%d", f[V]);

多重背包问题

有 $N$ 种物品，和一容积为 $V$ 的背包，第 $i$ 种物品有 $n_i$ 件，体积为 $w_i$ ，价值为 $c_i$ 。将第几件物品装入，使体积不超过总体积，且价值和最大，求最大价值。

解法 $I.$ 化为完全背包

状态转移方程：$F_{i,v} = max(F_{i-1,v-k\times w_i} + k\times c_i | 0\leqslant k\leqslant n_i)$

时间复杂度：$O(V\times \sum{n_i})$

框架

for (int i = 1; i <= N; ++i)
{
    for (int j = V; j >= 0; --j)
    {
        for (int k = 0; k <= n[i]; ++k)
        {
            f[i][j] = max(f[i - 1][j], [i - 1][j - k * w[i]] + k * c[i])
        }
    }
}
printf("%d", f[N][V]);

解法 $II.$ 化为01背包

把 $n_i$ 件一种物品化为单独的 $n_i$ 件物品即可

时间复杂度：$O(V\times \sum{n_i})$

框架略

解法 $III.$ 二进制优化

$$
n_i\to 1+2+4+\dots +2^{k-1}+\dots +(n_i-2^k+1)
$$
$$
\sum{n_i}\to \sum{\log_2{n_i}}
$$
时间复杂度：$O(V\times \sum{\log_2{n_i}})$

框架

for (int i = 1; i <= n; ++i)
{
    int w, c, n, t = 1;
    scanf("%d %d %d", &w, &c, &n);
    while(n >= t)
    {
        v[++N] = x * t;
        w[N]   = y * t;
        n -= t;
        t *= 2;
    }
    v[++N] = x * n;
    w[N]   = y * n;
}
for (int i = 1; i <= N; ++i)
    for (int j = V; j >= v[i]; --j)
        f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d", f[V]);

混合三种背包问题

有 $N$ 种物品，和一容积为 $V$ 的背包，第 $i$ 种物品有 $n_i$ 件或无穷件，体积为 $w_i$ ，价值为 $c_i$ 。将第几件物品装入，使体积不超过总体积，且价值和最大，求最大价值。

伪框架

for (int i = 1; i <= N; ++i)
{
    if (第i件是有穷件)
    {
        for (int j = V; j >= 0; --j)
            f[j] = max(f[j], f[j - w[i]] + c[i]);
    }
    else //有无穷件
    {
        for (int j = 0; j <= V; ++j)
            f[j] = max(f[j], f[j - w[i]] + c[i]);
    }
}

二维费用的背包问题

有 $N$ 件物品，容积为 $V,U$ 的两个背包，每件物品有两种费用，选择物品需要付出两种代价，第 $i$ 件代价为 $a_i,b_i$，价值为 $c_i$。将第几件物品装入，使体积不超过总体积，且价值和最大，求最大价值。

改为二维数组即可

状态转移方程：$F_{v,u} = max(F_{v,u}\ , F_{v-a_i,u-b_i} + c_i)$

$F_{v,u}$ 表示前面的物品付出代价分别为 $v,u$ 时的最大价值

框架略

循环顺序

类01背包：v = V..0 u = U..0
类完全背包：v = 0..V u = 0..U
类多重背包：拆分物品

分组的背包问题

有 $K$ 组物品， $V$ 的背包，第 $k$ 组有 $N_k$ 件物品，第 $i$ 件物品的体积为 $w_i$ ，价值为 $c_i$ ，每组中只能选一件物品。将第几件物品装入，使体积不超过总体积，且价值和最大，求最大价值。

框架

for (int k = 1; k <= K; ++k)
{
    for (int v = V; v >= 0; --v)
    {
        for (int i = 1; i <= N[k]; ++i)
            f[v] = max(f[v], f[v - w[i]] + c[i]);
    }
}

背包问题的方案数

状态转移方程：$F_{i,v} = sum(F_{i-1,v}, F_{i-1,v-w_i})\ \ \ (F_{0,0} = 1)$

框架

f[0] = 1;
for (int i = 1; i <= N; ++i)
{
    for (int j = w[i]; j <= V; ++j)
        f[j] += f[j - w[i]];
}
printf("%d", f[V]);

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约158个字)

Cpp算法-堆

说明

heap[]堆

heap_size堆大小

put(int)压入一个数

get()弹出堆顶

普通实现

int heap[maxn];
int heap_size = 0;

void put(int d)
{
    int now, next;
    heap[++heap_size] = d;
    now = heap_size;
    while (now > 1)
    {
        next = now >> 1;
        if (heap[now] <= heap[next]) break;
        swap(heap[now], heap[next]);
        now = next;
    }
    return;
}

int get()
{
    int now, next, res;
    res = heap[1];
    heap[1] = heap[heap_size--];
    now = 1;
    while (now * 2 <= heap_size)
    {
        next = now * 2;
        if (next < heap_size && heap[next + 1] < heap[next]) next++;
        if (heap[now] <= heap[next]) break;
        swap(heap[now], heap[next]);
        now = next;
    }
    return res;
}

STL实现

int heap[maxn];
int heap_size = 0;

void put(int d)
{
    heap[++heap_size] = d;
    push_heap(heap + 1, heap + heap_size + 1);
    //push_heap(heap + 1, heap + heap_size + 1, greater<int>()); 
    return;
}

int get()
{
    pop_heap(heap + 1, heap + heap_size + 1);                   
    //pop_heap(heap + 1, heap + heap_size + 1, greater<int>()); 
    return heap[heap_size--];
}

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约163个字)

Cpp算法-图论-SPFA

说明

n, m, s点数、边数、源点

cnt, head[], edge[], add(int, int, int)链式前向星

dist[]各点到源点路径长

vis[]记录

实现

const int maxn = 10010;
const int maxm = 500010;

int n, m, s, dist[maxn], vis[maxn];

int cnt, head[maxn];
struct Edge
{
    int next, to, dis;
}edge[maxm];
void add(int from, int to, int dis)
{
    edge[++cnt].next = head[from];
    edge[cnt].to     = to;
    edge[cnt].dis    = dis;
    head[from]       = cnt;
}

void SPFA()
{
    queue<int> q;
    for (int i = 1; i <= n; ++i)
    {
        dist[i] = INT_MAX;
    }
    q.push(s);
    dist[s] = 0; vis[s] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop(); vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (dist[v] > dist[u] + edge[i].dis)
            {
                dist[v] = dist[u] + edge[i].dis;
                if (!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return;
}

2019-01-10发表2020-05-05更新C++算法几秒读完 (大约77个字)

Cpp算法-图论-链式前向星

说明

cnt记数

head[]记录边的头

struct Edge{int, int, int}边信息: 开始点、结束点、权值

add_edge(int, int, int)添加边

实现

int cnt, head[maxn];
struct Edge
{
	int next, to, val;
}edge[maxm];
void add_edge(int from, int to, int val)
{
	edge[++cnt].next = head[from];
	edge[cnt].to     = to;
	edge[cnt].val    = val;
	head[from]       = cnt;
}

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约191个字)

Cpp算法-图论-Prim

说明

n, m, _map[][]点数、边数、邻接矩阵

dist[]树根到各点路径长

pre[]生成树路径

实现

const int maxn = 101;
int n, m, dist[maxn], _map[maxn][maxn], pre[maxn];

void make()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			_map[i][j] = INT_MAX;
	for (int i = 1; i <= n; ++i) _map[i][i] = 0;
	for (int i = 1; i <= m; ++i)
	{
		int from, to, w;
		scanf("%d %d %d", &from, &to, &w);
		_map[from][to] = w;
	}
	return;
}

void Prim()
{
	int i, j, k;
	int min;
	bool p[maxn];
	for (int i = 2; i <= n; ++i)
	{
		p[i] = false;
		dist[i] = _map[1][i];
		pre[i] = 1;
	}
	dist[1] = 0;
	p[1] = true;
	for (int i = 1; i <= n - 1; ++i)
	{
		min = INT_MAX;
		k = 0;
		for (int j = 1; j <= n; ++j)
		{
			if (!p[j] && dist[j] < min)
			{
				min = dist[j]
				k = j;
			}
		}
		if (k == 0) return;
		p[k] = true;
		for (int j = 1; j <= n; ++j)
		{
			if (!p[j] && _map[k][j] != INT_MAX && dist[j] > _map[k][j])
			{
				dist[j] = _map[k][j];
				pre[j] = k;
			}
		}
	}
	return;
}

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约169个字)

Cpp算法-图论-Kruskal

说明

ufs[], find(int), unionn(int, int)并查集结构

edge[]链式前向星

cmp(Edge, Edge)边排序方案

实现

const int maxn = 1010;
int ufs[maxn];

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

void unionn(int x, int y)
{
    int a = find(x);
    int b = find(y);
    if (a != b)
    {
        ufs[a] = b;
    }
}

const int maxm = 100010;

struct Edge
{
    int a, b, w;
    bool select;
}edge[maxm];

bool cmp(Edge a, Edge b)
{
    if (a.w != b.w) return a.w < b.w;
    if (a.a != b.a) return a.a < b.a;
    return a.b < b.b; 
}

void kruskal()
{
    for (int i = 1; i <= n; ++i)
    {
        ufs[i] = i;
    }
    int k = 0, x, y;
    sort(edge + 1, edge + 1 + m, cmp);
    for (int i = 1; i <= m; ++i)
    {
        if (k == n - 1) break;
        x = find(edge[i].a);
        y = find(edge[i].b);
        if (x != y)
        {
            unionn(x, y);
            k++;
            edge[i].select = true;
        } 
    }
}

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约116个字)

Cpp算法-字符串算法-KMP

例：洛谷P3375

说明

pre()求前缀数组

kmp()匹配字符串

实现

char s1[1000010], s2[1000010];
int nxt[1000010], l1, l2;

void pre()
{
    nxt[1] = 0;
    int j = 0;
    for (int i = 1; i < l2; ++i)
    {
        while (j > 0 && s2[j + 1] != s2[i + 1]) j = nxt[j];
        if (s2[j + 1] == s2[i + 1]) j++;
        nxt[i + 1] = j;
    }
}

void kmp()
{
    int j = 0;
    for (int i = 0; i < l1; ++i)
    {
        while (j > 0 && s2[j + 1] != s1[i + 1]) j = nxt[j];
        if (s2[j + 1] == s1[i + 1]) j++;
        if (j == l2)
        {
            printf("%d\n", i - l2 + 2);
            j = nxt[j];
        }
    }
}

int main()
{
    cin >> s1 + 1;
    cin >> s2 + 1;
    l1 = strlen(s1 + 1);
    l2 = strlen(s2 + 1);
    pre();
    kmp();
    return 0;
}

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约145个字)

Cpp算法-字符串算法-哈希表

例：洛谷P4305

说明

hash[]哈希表

find(int x)查找哈希表中 $x$ 的位置

push(int x)将 $x$ 插入到哈希表中

check(int x)查找 $x$ 是否在哈希表中

实现

#define p 100003
#define hash(a) a%p

int h[p], t, n, x;

int find(int x)
{
    int y;
    if (x < 0) y = hash(-x);
    else y = hash(x);
    while (h[y] && h[y] != x) y = hash(++y);
    return y;
}

void push(int x)
{
    h[find(x)] = x;
}

bool check(int x)
{
    return h[find(x)] == x;
}

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        memset(h, 0, sizeof(h));
        scanf("%d", &n);
        while (n--)
        {
            scanf("%d", &x);
            if (!check(x))
            {
                printf("%d ", x);
                push(x);
            }
        }
        printf("\n");
    }
    return 0;
}

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约217个字)

Cpp算法-字符串算法-字符串哈希

例：洛谷P3370

单哈希(自然溢出)

typedef unsigned long long ULL;
ULL base = 131, a[10010];
char s[10010];

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = Ans * base + (ULL)s[i];
    return Ans & 0x7fffffff;
}

单哈希(单模数)

typedef unsigned long long ULL;
ULL base = 131, a[10010], mod = 19260817;
char s[10010];

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod;
    return Ans;
}

单哈希(大模数)

typedef unsigned long long ULL;
ULL base = 131, a[10010], mod = 212370440130137957LL;
char s[10010];
int prime = 233317;

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; ++i)
        Ans = (Ans * base + (ULL)s[i]) % mod + prime;
    return Ans;
}

双哈希

typedef unsigned long long ULL;
ULL base = 131, mod1=19260817, mod2=19660813;
char s[10010];
struct data
{
    ULL x,y;
}a[10010];

ULL hash1(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod1;
    return Ans;
}

ULL hash2(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod2;
    return Ans;
}

2019-01-10发表2020-05-05更新C++算法几秒读完 (大约55个字)

Cpp算法-数论-线性筛素数

说明

p[] 最终结果

实现

bool vis[N];
int p[N], cnt;

void get_prime()
{
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i])
            p[++cnt] = i;
        for (int j = 1; j <= cnt; ++j)
        {
            int v = i * p[j];
            if (v >= N) break;
            vis[v] = true;
            if (i % p[j] == 0) continue;
        }
    }
}

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约188个字)

Cpp算法-图论-Floyd

说明

n, m, G[][]点数、边数、邻接矩阵

dist[][]每对顶点间路径长度

pre[][]每对顶点之间路径

make()建图

实现

const int maxn = 110;
int n, m, G[maxn][maxn], dist[maxn][maxn], pre[maxn][maxn];

void make()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            G[i][j] = INT_MAX;
    for (int i = 1; i <= n; ++i) G[i][i] = 0;
    for (int i = 1; i <= m; ++i)
    {
        int from, to, w;
        scanf("%d %d %d", &from, &to, &w);
        G[from][to] = w;
    }
    return;
}

void Floyd()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            dist[i][j] = G[i][j];
            pre[i][j]  = i;
        }
    }
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pre[i][j]  = pre[k][j];
                }
            }
        }
    }
    return;
}

2019-01-10发表2020-05-05更新C++算法2 分钟读完 (大约244个字)

Cpp算法-图论-欧拉回路

邻接矩阵

说明

G[][]邻接矩阵

deg[]度

ans[]欧拉回路

n, e点数、边数

实现

int G[maxn][maxn], deg[maxn], ans[maxn];
int n, e, x, y, ansi, s;

void Euler(int i)
{
	for (int j = 1; j <= n; ++j)
	{
		if (G[i][j])
		{
			G[i][j] = G[j][i] = 0;
			Euler(j);
		}
	}
	ans[++ansi] = i;
}

int main()
{
	scanf("%d %d", &n, &e);
	for (int i = 1; i <= e; ++i)
	{
		scanf("%d %d", &x, &y);
		G[x][y] = G[y][x] = 1;
		deg[x]++;
		deg[y]++;
	}
	s = 1;
	for (int i = 1; i <= n; ++i)
		if (deg[i] % 2 == 1)
			s = i;
	Euler(s);
	for (int i = 1; i <= ansi; ++i)
		printf("%d ", ans[i]);
	printf("\n");
	return 0;
}

链式前向星

说明

n, m点数、边数

head, edge[]链式前向星

ans[], ansi路径、数组大小

vis[]记录

make()建图

实现

int head[maxn];
struct Node
{
	int to, next;
}edge[maxm];

void make()
{
	scanf("%d %d", &n, &m);
	for (int k = 1; k <= m; ++k)
	{
		int i, j;
		scanf("%d %d", &i, &j);
		edge[k].to = i;
		edge[k].next = head[i];
		head[i] = k;
	}
	return;
}

int ans[maxm];
int ansi = 0;
bool vis[2 * maxm];

void dfs(int now)
{
    for (int k = head[now]; k != 0; k = edge[k].next)
	{
        if (!vis[k])
        {
            vis[k] = true;
            vis[k ^ 1] = true;
            dfs(edge[k].to);
            ans[ansi++] = k;
        }
	}
}

2019-01-10发表2020-05-05更新C++算法1 分钟读完 (大约133个字)

Cpp算法-动态规划

待完成

多阶段过程决策的最优化问题

graph LR
    A --5--> B1
    A --3--> B2
    B1 --1--> C1
    B1 --6--> C2
    B1 --3--> C3
    B2 --8--> C2
    B2 --4--> C4
    C1 --5--> D1
    C1 --6--> D2
    C2 --5--> D1
    C3 --8--> D3
    C4 --3--> D3
    D1 --3--> E
    D2 --4--> E
    D3 --3--> E

!!! tldr “题目及注解”
求上图从 $A$ 到 $E$ 的最短距离

$K$: 阶段

$D(X_I, (X+1)_J)$: 从 $X_I$ 到 $(X+1)_J$ 的距离

$F_K(X_I)$: $K$ 阶段下 $X_I$ 到终点 $E$ 的最短距离

倒推:
$$
K=4\qquad F_4(D_1)=3\qquad F_4(D_2)=4\qquad F_4(D_3)=3
$$
$$
K=5\qquad F_3(C_1)=min(D(C_1,D_1)+F_4(D_1),D(C_1,D_2)+F_4(D_2))=min(5+3,6+4)=8
F_3(C_2)
$$

2019-01-10发表2020-05-05更新C++算法2 分钟读完 (大约360个字)

Cpp算法-图论-Dijkstra

说明

n, m点数、边数

G[][]邻接矩阵存图

dist[]路径长度

pre[]路径

make()建图

实现

const int maxn = 10010;
int n, m, G[maxn][maxn], dist[maxn], pre[maxn], s;

void make()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            G[i][j] = INT_MAX;
    for (int i = 1; i <= n; ++i) G[i][i] = 0;
    for (int i = 1; i <= m; ++i)
    {
        int from, to, w;
        scanf("%d %d %d", &from, &to, &w);
        G[from][to] = w;
    }
    return;
}

void Dijkstra()
{
    int k, min;
    bool p[maxn];
    for (int i = 1; i <= n; ++i)
    {
        p[i] = false;
        if (i != s)
        {
            dist[i] = G[s][i];
            pre[i]  = s;
        }
    }
    dist[s] = 0; p[s] = true;
    for (int i = 1; i <= n - 1; ++i)
    {
        min = INT_MAX; k = 0;
        for (int j = 1; j <= n; ++j)
        {
            if (!p[j] && dist[j] < min)
            {
                min = dist[j];
                k = j;
            }
        }
        if (k == 0) return;
        p[k] = true;
        for (int j = 1; j <= n; ++j)
        {
            if (!p[j] && G[k][j] != INT_MAX && dist[j] > dist[k] + G[k][j])
            {
                dist[j] = dist[k] + G[k][j];
                pre[j] = k;
            }
        }
    }
    return;
}

堆优化(链式前向星)

struct Edge
{
    int to, nxt, t;
}edge[maxm << 1];
int head[maxn], cnt;
void add(int a, int b, int t)
{
    edge[++cnt].to  = b;
    edge[cnt].nxt = head[a];
    edge[cnt].t   = t;
    head[a]       = cnt;
}

struct heap
{
    int u, d;
    bool operator < (const heap& a) const
    {
        return d > a.d;
    }
};

void Dijkstra()
{
    priority_queue<heap> q;
    for (int i = 0; i <= n; ++i) dist[i] = INF;
    dist[1] = 0;
    q.push((heap){1, 0});
    while (!q.empty())
    {
        heap top = q.top();
        q.pop();
        int tx = top.u;
        int td = top.d;
        if (td != dist[tx]) continue;
        for (int i = head[tx]; i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (dist[v] > dist[tx] + edge[i].t)
            {
                dist[v] = dist[tx] + edge[i].t;
                dy[v] = i; 
                dx[v] = tx;    //记录路径
                q.push((heap){v, dist[v]});
            }
        }
    }
}

路径

int q = n, p[maxm];
while (q != 1)
{
    p[++tot] = dy[q];
    q = dx[q];
}

2019-01-10发表2020-05-05更新C++算法几秒读完 (大约95个字)

Cpp算法-树状数组

树状数组

模板：洛谷P3374

说明

tree[]树状数组

lowbit(int)神奇的函数

add(int x, int k)第 $x$ 个数加上 $k$

sum(int x)前 $x$ 个数的和

实现

int tree[2000010];

int lowbit(int k)
{
    return k & -k;
}

void add(int x, int k)
{
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

int sum(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

2019-01-10发表2020-05-05更新C++算法5 分钟读完 (大约815个字)

Cpp算法-大整数类

#include<string>
#include<iostream>
#include<iosfwd>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
using namespace std;

const int maxl = 5000;
#define max(a, b) a>b ? a : b
#define min(a, b) a<b ? a : b

class BigInteger
{
	public:
		int len, s[maxl];
		
		BigInteger();
		BigInteger(const char*);
		BigInteger(int);
		bool sign;
		string toStr() const;
		friend istream& operator>>(istream&, BigInteger&);
		friend ostream& operator<<(ostream&, BigInteger&);

		BigInteger operator=(const char*);
		BigInteger operator=(int);
		BigInteger operator=(const string);

		bool operator>(const BigInteger&) const;
		bool operator>=(const BigInteger&) const;
		bool operator>(const BigInteger&) const;
		bool operator>=(const BigInteger&) const;
		bool operator==(const BigInteger&) const;
		bool operator!=(const BigInteger&) const;

		BigInteger operator+(const BigInteger&) const;
		BigInteger operator++();
		BigInteger operator++(int);
		BigInteger operator+=(const BigInteger&);
		BigInteger operator-(const BigInteger&) const;
		BigInteger operator--();
		BigInteger operator--(int);
		BigInteger operator-=(const BigInteger&);
		BigInteger operator*(const BigInteger&) const;
		BigInteger operator*(const int num) const;
		BigInteger operator*=(const BigInteger&);
		BigInteger operator/(const BigInteger&) const;
		BigInteger operator/=(const BigInteger&);

		BigInteger operator%(const BigInteger&) const;
		BigInteger factorial() const;
		BigInteger Sqrt() const;
		BigInteger Pow(const BigInteger&) const;

		void clean();
		~BigInteger;
};


BigInteger::BigInteger()
{
	memset(s, 0, sizeof(s));
	len = 1;
	sign = 1;
}

BigInteger::BigInteger(const char *num)
{
	*this = num;
}

BigInteger::BigInteger(int num)
{
	*this = num;
}

string BigInteger::toStr() const
{
	string res;
	res = "";
	for (int i = 0; i < len; ++i)
		res = (char)(s[i] + '0') + res;
	if (res == "") res = "0";
	if (!sign && res != "0") res = "-" + res;
	return res;
}

istream& operator>>(istream& in, BigInteger& num)
{
	string str;
	in>>str;
	num = str;
	return in;
}

ostream& operator<<(ostream& out, BigInteger& num)
{
	out<<num.toStr();
	return out;
}

BigInteger BigInteger::operator=(const char* num)
{
	memset(s, 0, sizeof(s));
	char a[maxl] = "";
	if (num[0] != "-")
		strcpy(a, num);
	else
		for (int i = 1; i < strlen(num); ++i)
			a[i - 1] = num[i];
	sign = !(num[0] == "-");
	len = strlen(a);
	for (int i = 0; i < strlen(a); ++i)
		s[i] = a[len - i - 1] - 48;
	return *this;
}

BigInteger BigInteger::operator=(int num)
{
	if (num < 0)
		sign = 0, num = -num;
	else
		sign = 1;
	char temp[MAX_L];
	sprintf(temp, "%d", num);
	*this = temp;
	return *this;
}

BigInteger BigInteger::operator=(const string num)
{
	const char* tmp;
	tmp = num.c_str();
	*this = tmp;
	return *this;
}

bool BigInteger::operator<(const BigInteger& num) const
{
	if (sign^num.sign)
		return num.sign;
	if (len != num.len)
		return len < num.len;
	for (int i = len - 1; i >= 0; --i)
		if (s[i] != num.s[i])
			return sign ? (s[i] < num.s[i]) : (s[i] > num.s[i])
	return !sign;
}

bool BigInteger::operator>(const BigInteger& num) const
{
	return num < *this;
}

bool BigInteger::operator<=(const BigInteger& num) const
{
	return !(*this > num);
}

bool BigInteger::operator>=(const BigInteger& num) const
{
	return !(*this < num);
}

bool BigInteger::operator!=(const BigInteger& num) const
{
	return *this > num || *this < num;
}

bool BigInteger::operator==(const BigInteger& num) const
{
	return !(num != *this);
}

BigInteger BigInteger::operator+(const BigInteger& num) const
{
	 if (sign^num.sign)
	 {
		 BigInteger tmp = sign ? num : *this;
		 tmp.sign = 1;
		 return sign ? *this - tmp : num - tmp;
	 }
	 BigInteger result;
	 result.len = 0;
	 int temp = 0;
	 for (int i = 0; temp || i < (max(len, num.len)); i++)
	 {
		 int t = s[i] + num.s[i] + temp;
		 result.s[result.len++] = t % 10;
		 temp = t / 10;
	 }
	 result.sign = sign;
	 return result;
}

BigInteger BigInteger::operator++()
{
	*this = *this + 1;
	return *this;
}

BigInteger BigInteger::operator++(int)
{
	BigInteger old = *this;
	++(*this);
	return old;
}

BigInteger BigInteger::operator+=(const BigInteger& num)
{
	*this = *this + num;
	return *this;
}

BigInteger BigInteger::operator-(const BigInteger& num) const
{
	 BigInteger b = num, a = *this;
	 if (!num.sign && !sign)
	 {
		 b.sign = 1;
		 a.sign = 1;
		 return b - a;
	 }
	 if (!b.sign)
	 {
		 b.sign = 1;
		 return a + b;
	 }
	 if (!a.sign)
	 {
		 a.sign = 1;
		 b = BigInteger(0) - (a + b);
		 return b;
	 }
	 if (a < b)
	 {
		 BigInteger c = (b - a);
		 c.sign = false;
		 return c;
	 }
	 BigInteger result;
	 result.len = 0;
	 for (int i = 0, g = 0; i < a.len; i++)
	 {
		 int x = a.s[i] - g;
		 if (i < b.len) x -= b.s[i];
		 if (x >= 0) g = 0;
		 else
		 {
			 g = 1;
			 x += 10;
		 }
		 result.s[result.len++] = x;
	 }
	 result.clean();
	 return result;
}

BigInteger BigInteger::operator--()
{
	*this = *this - 1;
	return *this;
}

BigInteger BigInteger::operator--(int)
{
	BigInteger old = *this;
	--(*this);
	return old;
}

BigInteger BigInteger::operator-=(const BigInteger& num)
{
	*this = *this - num;
	return *this;
}

BigInteger BigInteger::operator*(const BigInteger& num) const
{
	BigInteger result;
	result.len = len + num.len;
	for (int i = 0; i < len; i++)
		for (int j = 0; j < num.len; j++)
			result.s[i + j] += s[i] * num.s[j];
	for (int i = 0; i < result.len; i++)
	{
		 result.s[i + 1] += result.s[i] / 10;
		 result.s[i] %= 10;
	}
	result.clean();
	result.sign = !(sign^num.sign);
	return result;
}

BigInteger BigInteger::operator*(const int num) const
{
	BigInteger x = num;
	BigInteger z = *this;
	return *this;
}

BigInteger BigInteger::operator/(const BigInteger& num) const
{
	 BigInteger ans;
	 ans.len = len - num.len + 1;
	 if (ans.len < 0)
	 {
		 ans.len = 1;
		 return ans;
	 }
	 BigInteger divisor = *this, divid = num;
	 divisor.sign = divid.sign = 1;
	 int k = ans.len - 1;
	 int j = len - 1;
	 while (k >= 0)
	 {
		 while (divisor.s[j] == 0) j--;
		 if (k > j) k = j;
		 char z[MAX_L];
		 memset(z, 0, sizeof(z));
		 for (int i = j; i >= k; i--)
			 z[j - i] = divisor.s[i] + '0';
			 BigInteger dividend = z;
			 if (dividend < divid) { k--; continue; }
			 int key = 0;
			 while (divid*key <= dividend) key++;
			 key--;
			 ans.s[k] = key;
			 BigInteger temp = divid*key;
			 for (int i = 0; i < k; i++)
				 temp = temp * 10;
				 divisor = divisor - temp;
				 k--;
	 }
	 ans.clean();
	 ans.sign = !(sign^num.sign);
	 return ans;
}

BigInteger BigInteger::operator/=(const BigInteger& num)
{
	*this = *this / num;
	return *this;
}

BigInteger BigInteger::operator%(const BigInteger& num) const
{
	BigInteger a = *this, b = num;
	a.sign = b.sign = 1;
	BigInteger result, temp = a / b*b;
	result = a - temp;
	result.sign = sign;
	return result;
}

BigInteger BigInteger::Pow(const BigInteger& num) const
{
	BigInteger result = 1;
	for (BigInteger i = 0; i < num; i++)
		result = result * (*this);
		return result;
}

BigInteger BigInteger::factorial() const
{
	BigInteger result = 1;
	for (BigInteger i = 1; i <= *this; i++)
		result *= i;
	return result;
}

void BigInteger::clean()
{
	if (len == 0) len++;
	while (len > 1 && s[len - 1] == '\0')
		len--;
}

BigInteger BigInteger::Sqrt() const
{
	if(*this < 0) return - 1;
	if(*this <= 1)return *this;
	BigInteger l = 0, r = *this, mid;
	while(r - l > 1)
	{
		mid = (l + r) / 2;
		if(mid * mid > *this)
			r = mid;
		else
			l = mid;
	}
	return l;
}

BigInteger::~BigInteger()
{

}