发表更新2 分钟读完 (大约325个字)

Hexo搭建博客

由于mkdocs上有很多不足，例如没有标签，分类，评论，计数等等，故转至使用Hexo搭建博客，以下是我折腾的过程

阅读全文
发表更新几秒读完 (大约41个字)

更新日志

本博客在2019.3.10更改至由Hexo驱动，并在2019.3.12完成更改。
原文章时间均改为2019.1.9，算法模板时间改为2019.1.10。

发表更新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;
}
BiliBili主页

最新文章

归档

标签

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

分类

×