发表更新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)$

1
2
3
4
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筛法

1
2
3
4
5
6
7
8
9
10
11
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;
    }
}

欧拉线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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$

1
2
3
4
5
6
7
8
9
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$

1
2
3
4
5
6
7
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;
}

使用位运算:

1
2
3
4
5
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$互质的整数个数

求值

1
2
3
4
5
6
7
8
9
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;
}

筛欧拉函数表

1
2
3
4
5
6
7
8
9
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$不为质数

递归求解

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

筛逆元表

1
2
3
4
5
6
7
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$两两互质

1
2
3
4
5
6
7
8
9
10
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$不一定两两互质

1
2
3
4
5
6
7
8
9
10
11
12
13
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$为质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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}$$
线性筛:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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];
		}
	}
}
发表更新题解5 分钟读完 (大约792个字)

「Luogu P5020 P1621 P4942」小练习-题解

$\mathcal{「P5020」}$ 货币系统

表面上是数论，其实就是个__动态规划__

首先设$A = (n, a) \ \ B = (m, b)$
可以证明$B \subseteq A$
$proof:$
我们设$x\in A$且$x$不能被$A$集合内除它以外的元素组成。
然后我们假设$x \notin B$，那么就说明$B$集合中必然存在一些元素能够组成$x$。
那么这些元素至少存在一个不在集合$A$内并且不能被集合$A$里的元素组成的数（因为如果不存在的话集合$A$内的元素就可以组成$x$了），可以看到这与集合$B$的定义产生了矛盾。
综上所述，$A$集合内不能被其它数组成的数必然存在于$B$集合内
$Q.E.D$

然后动态规划
dp[i]表示$i$面值最多能被几张钱表示
则若其不能被表示dp[i] = -inf
能表示且只有它自己则dp[i] = 1
初始化dp[] = -inf; dp[0] = 0
状态转移方程为dp[j] = max(dp[j], dp[j - a[i]] + 1)

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 <bits/stdc++.h>
using namespace std;

int n, T, ans, a[1010], dp[30010];

int main() {
    scanf("%d", &T);
    while (T--) {
        memset(dp, -0x3f, sizeof(dp));
        memset(a, 0, sizeof(a));
        ans = 0; dp[0] = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = a[i]; j <= 25010; ++j) {
                dp[j] = max(dp[j], dp[j - a[i]] + 1);
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (dp[a[i]] == 1) {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
/* 862ms 944kB */

$\mathcal{「P1621」}$ 集合

使用__并查集和埃氏筛法__(埃拉托斯特尼筛法)即可
具体操作是边筛边合并集合

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;

int ufs[maxn], a, b, p, ans;
bool isprime[maxn];

int find(int x) {
    return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
}

int main() {
    scanf("%d %d %d", &a, &b, &p);
    ans = b - a + 1;               //初始个数为区间内数的个数
    for (int i = a; i <= b; ++i) { //初始化
        ufs[i] = i;
    }
    for (int i = 2; i <= b; ++i) { //埃氏筛
        if (!isprime[i]) {
            if (i >= p) {          //大于p才合并
                for (int j = i * 2; j <= b; j += i) {
                    isprime[j] = true;
                    if (j - i >= a && find(j) != find(j - i)) { //合并
                        ufs[find(j)] = find(j - i);
                        --ans;
                    }
                }
            } else {               //不大于p但要标记
                for (int j = i * 2; j <= b; j += i) {
                    isprime[j] = true;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
/* 38ms 1312kB */

$\mathcal{「P4942」}$ 小凯的数字

类似于$NOIp2017\ D1T1$ 小凯的疑惑,推柿子即可

首先$l(l+1)(l+2)…(r-1)r$可以表示为$l\times 10^? + (l + 1)\times 10^? + … + r\times 10^?$
同时我们知道$10$的若干次方除以$9$的余数__恒为__$1$
所以$l(l+1)(l+2)…(r-1)r$除以$9$的余数就等于$l + (l + 1) + … + (r - 1) + r$的余数
并且$l,l+1,…,r$为等差数列,公差为$1$
运用等差数列求和公式即可求解

$a_1 = l\ d = 1$
$n = r - l + 1$
$S_n = n\times a_1 + n\times (n - 1)\times \frac{d}{2}$
所以
$$
\boxed{Ans = n\times l + n\times (n - 1) \div 2}
$$

另外要边算边取模,除以$2$要变成乘模$9$下的逆元$5$
所以公式如下
ans = (n * (l % 9) % 9 + n * (n - 1) % 9 * 5 % 9) % 9;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int T;
long long l, r, n, ans;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld %lld", &l, &r);
        n = (r - l + 1) % 9;
        ans = (n * (l % 9) % 9 + n * (n - 1) % 9 * 5 % 9) % 9;
        printf("%lld\n", ans);
    }
    return 0;
}
/* 32ms 888kB */

如有疑问,可以在下方评论区留言

发表更新C++算法1 分钟读完 (大约164个字)

Cpp算法-并查集

说明

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

实现

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
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;
}
发表更新C++算法2 分钟读完 (大约309个字)

Cpp算法-STL标准库

模板

1
2
3
4
template <typename T>
/**
 * 写函数/结构体
 */

例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)

1
2
3
4
5
struct Node
{
    int x, y;
    Node(int a = 0, int b = 0):x(a), y(b){}
};
重载operator <
1
2
3
4
5
6
7
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大的优先级低

重写仿函数
1
2
3
4
5
6
7
8
9
10
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;
发表更新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]为结果

1
2
3
4
5
6
7
8
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)$

1
2
3
4
5
6
7
8
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)$

框架

1
2
3
4
5
6
7
8
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})$

框架

1
2
3
4
5
6
7
8
9
10
11
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}})$

框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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$ 。将第几件物品装入，使体积不超过总体积，且价值和最大，求最大价值。

伪框架

1
2
3
4
5
6
7
8
9
10
11
12
13
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$ ，每组中只能选一件物品。将第几件物品装入，使体积不超过总体积，且价值和最大，求最大价值。

框架

1
2
3
4
5
6
7
8
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)$

框架

1
2
3
4
5
6
7
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]);
发表更新C++算法1 分钟读完 (大约158个字)

Cpp算法-堆

说明

heap[]堆

heap_size堆大小

put(int)压入一个数

get()弹出堆顶

普通实现

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
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实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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--];
}
发表更新C++算法1 分钟读完 (大约163个字)

Cpp算法-图论-SPFA

说明

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

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

dist[]各点到源点路径长

vis[]记录

实现

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
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;
}
发表更新C++算法几秒读完 (大约77个字)

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

说明

cnt记数

head[]记录边的头

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

add_edge(int, int, int)添加边

实现

1
2
3
4
5
6
7
8
9
10
11
12
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;
}
发表更新C++算法1 分钟读完 (大约191个字)

Cpp算法-图论-Prim

说明

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

dist[]树根到各点路径长

pre[]生成树路径

实现

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
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;
}
发表更新C++算法1 分钟读完 (大约169个字)

Cpp算法-图论-Kruskal

说明

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

edge[]链式前向星

cmp(Edge, Edge)边排序方案

实现

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
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;
        } 
    }
}
发表更新C++算法1 分钟读完 (大约116个字)

Cpp算法-字符串算法-KMP

例：洛谷P3375

说明

pre()求前缀数组

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
31
32
33
34
35
36
37
38
39
40
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;
}
发表更新C++算法1 分钟读完 (大约145个字)

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

例：洛谷P4305

说明

hash[]哈希表

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

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

check(int x)查找 $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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}
发表更新C++算法1 分钟读完 (大约217个字)

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

例：洛谷P3370

单哈希(自然溢出)

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

单哈希(单模数)

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

单哈希(大模数)

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

双哈希

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
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;
}
发表更新C++算法几秒读完 (大约55个字)

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

说明

p[] 最终结果

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
        }
    }
}
发表更新C++算法1 分钟读完 (大约188个字)

Cpp算法-图论-Floyd

说明

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

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

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

make()建图

实现

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
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;
}
BiliBili主页

最新文章

归档

标签

AtCoder1
CSP-S2
CTF16
Cpp67
Haskell11
Linux1
Luogu5
NOIp33
Python1
Rust2
SPOJ1
Writeup11
bfs1
blog2
bug2
dsu on tree1
git1
github3
hexo1
manim3
markdown3
mkdocs1
python5
图论2
学习1
左偏树1
差分约束1
并查集1
数据结构4
数论3
最大流1
最短路2
杂谈2
树状数组1
游记1
状态压缩1
生活3
笔记29
算法32
线段树1
网络流22
范畴论1
莫队5
计算几何1
费用流10
随笔3
题解36

分类

×