Articles
83
Tags
38
Categories
6
Home
Archives
Tags
Categories
Link
Gallery
About
Catalog
  1. 1. 数论
    1. 1.1. 取整
    2. 1.2. 进制转换
      1. 1.2.1. 十进制转m进制
      2. 1.2.2. m进制转十进制
    3. 1.3. 位运算
    4. 1.4. 取模
      1. 1.4.1. 基本性质
      2. 1.4.2. 正负
    5. 1.5. 唯一分解定理
    6. 1.6. 最大公约数
    7. 1.7. 最小公倍数
    8. 1.8. 拓展欧几里得
  2. 2. 数据结构
    1. 2.1. 单调栈
      1. 2.1.1. 例题
    2. 2.2. 单调队列
    3. 2.3. 莫队
    4. 2.4. 堆
    5. 2.5. 二叉搜索树
    6. 2.6. 线段树
    7. 2.7. 树链剖分
      1. 2.7.1. 求LCA
      2. 2.7.2. 用线段树维护区间值
    8. 2.8. 树状数组
    9. 2.9. ST表
    10. 2.10. 对比
  3. 3. 图论
    1. 3.1. 有向无环图&拓扑排序
    2. 3.2. 缩点
      1. 3.2.1. 强联通分量
      2. 3.2.2. tarjan
      3. 3.2.3. Kosaraju算法
    3. 3.3. 二分图
      1. 3.3.1. 定义&性质
      2. 3.3.2. 匈牙利算法
    4. 3.4. 查分约束
    5. 3.5. 最近公共祖先
  4. 4. 贪心
    1. 4.1. 基本思想
    2. 4.2. 贪心问题的特点
  5. 5. 分治
    1. 5.1. 思想
    2. 5.2. 二分答案
    3. 5.3. 三分
  6. 6. 动态规划
    1. 6.1. 一维线性DP
    2. 6.2. 背包问题
      1. 6.2.1. 0-1背包
      2. 6.2.2. 完全背包
      3. 6.2.3. 多重背包
      4. 6.2.4. 分组背包
    3. 6.3. 树形DP
    4. 6.4. 状压DP
    5. 6.5. 数位DP
  7. 7. 对拍
2019清北夏令营
|游记
Post View:

数论

取整

  • x是一个实数

  • floor(x)对x向下取整

  • ceil(x)对x向上取整

    进制转换

    十进制转m进制

    用一个数组存转化得到的数，每次将十进制数 %m,得到m进制的最后一位，然后$ / m$，去掉最后一位

    m进制转十进制

    取$v = 0$,每次取m进制数的最高位,使$v = v \times m + a[i]$

    位运算

  • << 左移，乘2的n次方

  • >> 右移，除2的n次方

  • & 相同位的两个数字都为1，则为1；若有一个不为1，则为0

  • ·|· 相同位只要一个为1即为1

  • ^ 操作的结果是如果某位不同则该位为1, 否则该位为0

  • ~ not运算的定义是把内存中的0和1全部取反

    取模

    基本性质

    取模可以与加减乘交换顺序（注意除不行）

    1. x ≡ y(% p)

    2. x+a ≡ y+a (% p)

    3. x-a ≡ y-a (% p) （减法需要注意把负数华为正数）

    4. xa ≡ ya (% p) (以上假设x≡y (%p))

    5. (a + b)%p = (a%p + b%p)%p

    6. (a - b)%p = (a%p – b%p)%p

    7. (a - b)%p = (a - b + p)%p

    8. ab%p = (a%p)(b%p) %p

      正负

    9. 一个正整数对一个正整数取模得到的是一个非负整数

    10. 一个负数对一个正整数取模得到的是负数或者是0

    11. $a$%$b = a - \lfloor a / b \rfloor * b (a > 0)$

    唯一分解定理

    唯一分解定理(也称基本算数定理)：
    任意一个正整数c，将其分解为若干质数的正整数次幂的乘积，该分解方法唯一
    形如：$c=p1a1p2a2……*pnan$，$p1…pn$均为质数

    最大公约数

    算法公式：

1563675875508

code:

1
int gcd(int a,int b){return b == 0 ? a,gcd(b,a % b);}

时间复杂度为$log$级别。

最小公倍数

$lcm=n \times m / gcd(n,m)$
证明：从质因数分解思考

拓展欧几里得

code： 

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a,int b,int &x,int &y)
{
    if(b == 0)
    {
        x = 1,y = 0;
        return a;
    }
    int g = exgcd(b,a % b,y,x);
    y -= a / b * x;
    return g;
}

数据结构

单调栈

  • 单调栈是指一个栈内部的元素是具有严格单调性的一种数据结构
  • 一般作为工具在预处理数据时使用，或者优化动态规划（决策具有单调性）

    例题

1563349066186

单调队列

  1. 单调队列必须满足从队头到队尾的严格单调性。

  2. 排在队列前面的比排在队列后面的要先进队。
    一般用于优化动态规划等

例题：

1563677659940

code:

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<malloc.h> 
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

struct tree{
	int maxx,minn;
	tree *lson,*rson;
}*root = (tree*)malloc(sizeof(tree));

struct node{
	int a,b;
}ans[1000005];

void build(tree *tre,int l,int r)
{
	if(l == r)
	{
		tre -> maxx = read();
		tre -> minn = tre -> maxx;
		return;
	}
	int mid = (l + r) >> 1;
	tree *son1 = (tree*)malloc(sizeof(tree));
	tree *son2 = (tree*)malloc(sizeof(tree));
	tre -> lson = son1;
	tre -> rson = son2;
	build(tre -> lson,l,mid);
	build(tre -> rson,mid + 1,r);
	tre -> maxx = max(tre -> lson -> maxx,tre -> rson -> maxx);
	tre -> minn = min(tre -> lson -> minn,tre -> rson -> minn);
}

node query(tree *tre,int l,int r,int x,int y)
{
	if(l == r) return (node){tre -> maxx,tre -> minn};
	int mid = (l + r) >> 1;
	node t1,t2;
	t1.a = -INF; t1.b = INF; t2.a = -INF; t2.b = INF;
	if(x <= mid) t1 = query(tre -> lson,l,mid,x,y);
	if(y > mid) t2 = query(tre -> rson,mid + 1,r,x,y);
	return (node){max(t1.a,t2.a),min(t1.b,t2.b)};
}

int main()
{
	int n,k;
	n = read(); k = read();
	build(root,1,n);
	for(int i = 1; i <= n - k + 1; i++) ans[i] = query(root,1,n,i,i + k - 1);
	for(int i = 1; i <= n - k + 1; i++) printf("%d ",ans[i].b); printf("\n");
	for(int i = 1; i <= n - k + 1; i++) printf("%d ",ans[i].a); printf("\n");
	return 0;
}

莫队

$O(nsqrt(n)\times 修改复杂度)$的分治算法，只需要问题满足支持快速单点插入和快速单点删除就行了

例题：

1563677811242

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
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define INF 0x7fffffff

using namespace std;

long long read()
{
	long long x = 0,f = 1; char ch;
	ch = getchar();
	while(ch >'9' || ch < '0'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}

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

long long n,m,a[50005],xsort,p1,p2,t[50005],ans,cnt,g,ll,rr,in[50005],save1[50005],save2[50005];

struct query{
    long long l,r,num;
}q[50005];

long long mysort(query x, query y)
{
    if(x.l / xsort == y.l / xsort) return x.r < y.r;
    return x.l < y.l;
}

/*inline void del(int k)
{
    if(!in[k]) return ;
    in[k] = 0;
	t[a[k]] --;
    printf("del %d :\n before : %d\n",k,ans);
    ans = ans - t[a[k]] * (t[a[k]] + 1) + t[a[k]] * (t[a[k]] - 1);
    printf("after : %d\n",ans);
}

inline void add(int k)
{
	if(k == 0) return ;
	if(in[k]) return ;
	in[k] = 1;
    t[a[k]] ++;
	ans = ans + t[a[k]] * 2;
}*/

long long work(long long x)
{
	return x * x;
}

void add(long long k)
{
	long long u = a[k];
	if(k == 0) return ;
	//if(in[k]) return ;
	//in[k] = 1;
	ans = ans - work(t[u]);
	t[u] ++;
	ans = ans + work(t[u]);
}

void del(long long k)
{
	long long u = a[k];
	if(k == 0) return ;
	//if(in[k] == 0) return ;
	//in[k] = 0;
	ans = ans - work(t[u]);
	t[u] --;
	ans = ans + work(t[u]);
}

int main()
{
	n = read(); m = read();
    for(re int i = 1; i <= n; i ++) a[i] = read();
    for(re int i = 1; i <= m; i++)
    {
        q[i].l = read();
        q[i].r = read();
        q[i].num = i;
    }
    xsort = sqrt(n);
    sort(q + 1, q + m + 1, mysort);
    for(re int i = 1; i <= m; i++)
    {
    	ll =q[i].l; rr = q[i].r;
//        if(ll == rr) {printf("0/1\n"); continue ;}
        while(p1 < ll){del(p1); p1 ++;}
        while(p1 > ll){p1 --; add(p1);}
        while(p2 < rr){p2 ++; add(p2);}
        while(p2 > rr){del(p2); p2 --;}
        cnt = (rr - ll + 1) * (rr - ll);
        save1[q[i].num] = ans - (rr - ll + 1);
        save2[q[i].num] = cnt;
    }
    for(re int i = 1; i <= m; i++)
    {
    	if(save1[i] != 0 && save2[i] != 0) g = gcd(save1[i],save2[i]);
    	else g = 1;
    	if(save1[i] == 0 || save2[i] == 0) {printf("0/1\n"); continue ;}
    	printf("%d/%d\n",save1[i] / g,save2[i] / g);
	}
	return 0;
}

堆

1563677163006

由于我们有priority_queue,所以手写堆就可以歇着了……

二叉搜索树

1563677248370

大概就是这样了

由于这东西对于竞赛没什么用（太好卡了，还是去用平衡树吧……），所以不说什么了。

线段树

1563677348499

额…… 对于线段树自我感觉良好，不说废话了qwq。

树链剖分

大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分”，我们所讲的也是“重链剖分”。

重链剖分可以将树上的任意一条路径划分成不超过O(logn) 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的lca为链的一个端点）。
重链剖分还能保证划分出的每条链上的节点 dfs 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。

1.修改 树上两点之间的路径上 所有点的值。
2.查询 树上两点之间的路径上 节点权值的 和/极值/其它（在序列上可以用数据结构维护，便于合并的信息） 。

1563437996567

1563437839049

求LCA

如果两个节点不在同一条链上，将所在链链首深度大的点跳链。当在同一条链时，深度小的点的位置就是lca。
一次跳过一条链，速度比倍增快。

用线段树维护区间值

考虑到树链剖分后每一个链的元素的dfs序是连续的，所以我们可以用线段树取维护树链剖分后的序列。
例题：
ZJOI2008 树的统计
对一棵有n个节点，节点带权值的静态树，进行三种操作共q 次：

  1. 修改单个节点的值；
  2. 查询u到u的路径上的最大值；
  3. 查询v到v的路径上的权值和。
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
	register int x = 0,f = 1;register char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
	while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

int n,m,r,s,p,x,y,z,o,t,cnt,ans;
int d[200005],siz[200005],fa[200005],dep[200005],son[200005],top[200005],seg[200005],rev[200005],bs[200005];

struct edge{
	int next,to;
}e[300005];

struct tree{
	int sum,lazy;
	tree *lson,*rson;
}*root = (tree*)malloc(sizeof(tree));

void add(int x,int y)
{
	e[++cnt].to = y;
	e[cnt].next = d[x];
	d[x] = cnt;
}

void dfs1(int u,int f)
{
	int a,v;
	siz[u] = 1;
	fa[u] = f;
	dep[u] = dep[f] + 1;
	for(int i = d[u]; i; i = e[i].next)
	{
		int j = e[i].to;
		if(j == f) continue;
		dfs1(j,u);
		siz[u] = siz[u] + siz[j];
		if(siz[j] > siz[son[u]]) son[u] = j;
	}
}

void dfs2(int u,int f)
{
	if(son[u])
	{
		seg[son[u]] = ++t;
		top[son[u]] = top[u];
		rev[t] = son[u];
		dfs2(son[u],u);
	}
	for(int i = d[u]; i; i = e[i].next)
	{
		int j = e[i].to;
		if(!top[j])
		{
			top[j] = j;
			seg[j] = ++t;
			rev[t] = j;
			dfs2(j,u);
		}
	}
}

void build(tree *tre,int l,int r)
{
	tre -> lazy = 0;
	if(l == r)
	{
		tre -> sum = bs[rev[l]];
		return ;
	}
	int mid = (l + r) >> 1;
	tree *son1 = (tree*)malloc(sizeof(tree));
	tree *son2 = (tree*)malloc(sizeof(tree));
	tre -> lson = son1;
	tre -> rson = son2;
	build(tre -> lson,l,mid);
	build(tre -> rson,mid + 1,r);
	tre -> sum = (tre -> lson -> sum + tre -> rson -> sum) % p;
}

void pushdown(tree *tre,int l,int r)
{
	if(l == r || tre -> lazy == 0) return ;
	int mid = (l + r) >> 1;
	tre -> lson -> sum = (tre -> lson ->  sum + 1ll *(mid - l + 1) * tre  -> lazy) % p;
	tre -> rson -> sum = (tre -> rson ->  sum + 1LL *(r - mid) * tre -> lazy) % p;
	tre -> lson -> lazy = (tre -> lson -> lazy + tre -> lazy) % p;
	tre -> rson -> lazy = (tre -> rson -> lazy + tre -> lazy) % p;
	tre -> lazy = 0;
}

void change(tree *tre,int l,int r,int x,int y,int k)
{
	if(l >= x && r <= y)
	{
		tre -> sum = (tre -> sum + 1LL * (r - l + 1) * k) % p;
		tre -> lazy = (tre -> lazy + k) % p;
		return ;
	}
	pushdown(tre,l,r);
	int mid = (l + r) >> 1;
	if(x <= mid) change(tre -> lson,l,mid,x,y,k);
	if(y > mid) change(tre -> rson,mid + 1,r,x,y,k);
	tre -> sum = (tre -> lson -> sum + tre -> rson -> sum) % p;
}


int query(tree *tre,int l,int r,int x,int y)
{
	if(l >= x && r <= y) return tre -> sum;
	pushdown(tre,l,r);
	int mid = (l + r) >> 1,t1 = 0,t2 = 0;
	if(x <= mid) t1 = query(tre -> lson,l,mid,x,y) % p;
	if(y >mid) t2 = query(tre -> rson,mid + 1,r,x,y) % p;
	return (t1 + t2) % p;
}

void myswap()
{
	o = x;
	x = y;
	y = o;
}

int main()
{
	n = read();
	m = read();
	r = read();
	p = read();
	for(int i = 1; i <= n; i++) bs[i] = read();
	for(int i = 1; i < n; i++)
	{
		x = read();
		y = read();
		add(x,y);
		add(y,x);
	}
	dfs1(r,0);
	seg[r] = ++t;
	rev[t] = r;
	top[r] = r;
	dfs2(r,0);
	build(root,1,n);
	for(int i = 1; i <= m; i++)
	{
		s = read();
		ans = 0;
		if(s == 1)
		{
			x = read(); y = read(); z = read();
			while(top[x] != top[y])
			{
				if(dep[top[x]] < dep[top[y]]) myswap();
				change(root,1,n,seg[top[x]],seg[x],z);
				x = fa[top[x]];
			}
			if(seg[x] > seg[y]) myswap();
			change(root,1,n,seg[x],seg[y],z);
		}
		if(s == 2)
		{
			x = read(); y = read();
			while(top[x] != top[y])
			{
				if(dep[top[x]] < dep[top[y]]) myswap();
				ans = (ans + query(root,1,n,seg[top[x]],seg[x])) % p;
				x = fa[top[x]];
			}
			if(seg[x] > seg[y]) myswap();
			ans = (ans + query(root,1,n,seg[x],seg[y])) % p;
			printf("%d\n",ans);
		}
		if(s == 3)
		{
			x = read(); z = read();
			change(root,1,n,seg[x],seg[x] + siz[x] - 1,z);
		}
		if(s == 4)
		{
			x = read();
			ans = query(root,1,n,seg[x],seg[x] + siz[x] - 1) % p;
			printf("%d\n",ans);
		}
	}
    return 0;
}

树状数组

他死了

ST表

倍增做法：
预处理出f[i][j]表示从i开始，连续2^j个中的最小值

对比

线段树：需要区间可合并

树状数组：需要区间可合并，并满足区间减法，不支持区间修改（min,max不满足区间减法）

ST算法：需要区间可合并，不支持修改

  • 线段树的要求最少，但代码最多
  • 线段树适用范围最广，但速度最慢

图论

有向无环图&拓扑排序

不存在环的有向图被称为有向无环图（ Directed Acyclic Graph）
在有向无环图上，我们可以对节点进行排序，生成一个线性序列，使得：如果节点i在该有向无环图上可以沿着有向边到达节点j，那么节点i在线性序列中的位置一定在节点j之前
生成线性序列的过程被称为拓扑排序
有向图 G 可以进行拓扑排序 等价于 有向图G是有向无环图
拓扑排序的简单应用：给出有向无环图G和一个点S，求S到G上其它所有点的路径的方案数
例题 P1347排序

1563460904461

1563460953172

https://www.luogu.org/problemnew/show/P2047
https://www.luogu.org/problemnew/show/P2966

缩点

强联通分量

强连通的定义：有向图 G 强连通是指，G 中任意两个结点连通。
强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图
强连通分量+缩点+DGA上的动态规划是解决一系列有向图问题通用方法

1563461937649

tarjan

1563451573251

如果结点u是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以u为根的子树中。u被称为这个强连通分量的根。这一点我们可以用反证法证明，即如果一个和u在同一个强联通分量中的点不在以遇到的第一个节点u的子树中，那么它一定比u先被搜索到。

1563452048796

code：

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
//https://www.luogu.org/problemnew/show/P3387
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

int read()
{
	int x = 0,f = 1; char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;}
	while(ch >= '0' && ch <= '9'){x = x * 10 + ch - 48; ch = getchar();}
	return x * f;
}

int cnt,cn,n,sc,p[100005],sz[100005],dfncnt,m,scc[100005],sta[100005],dfn[100005],low[100005],dfcnt,s[100005],tp,d[100005],h[100005],di[100005];

struct EDGE{
	int from,to,next;
}edge[500005],e[500005];

void add(int x,int y)
{
	e[++cnt].from = x;
	e[cnt].to = y;
	e[cnt].next = d[x];
	d[x] = cnt;
}

void tarjan(int u){
	low[u] = dfn[u] = ++dfncnt,s[++tp] = u;
//	cout << s[tp] << " stp" << endl;
	for(int i = d[u]; i; i = e[i].next) {
		int v = e[i].to;
		if(!dfn[v]) tarjan(v),low[u] = min(low[u],low[v]);
		else if(!scc[v]) low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u] == low[u]){
		while(s[tp] != u) 
		{
			p[u] += p[s[tp]],scc[s[tp]] = u,sz[u] ++,--tp;

		}
		scc[s[tp]] = u,sz[u] ++, --tp;
	}
}

int dist[100005];

int topo(){
	queue<int> que;
	int tot = 0;
	for(int i = 1; i <= n; i++)
		if(scc[i] == i && !di[i]){
			que.push(i);
			dist[i] = p[i];
		}
	while(!que.empty()){
		int k = que.front(); que.pop();
		for(int i = h[k]; i; i = edge[i].next){
			int v = edge[i].to;
			dist[v] = max(dist[v],dist[k] + p[v]);
			di[v] --;
			if(di[v] == 0) que.push(v);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) ans = max(ans,dist[i]);
	return ans;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++) scanf("%d",&p[i]);
	for(int i = 1; i <= m; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= m; i++){
		int x = scc[e[i].from],y = scc[e[i].to];
		if(x != y){
			edge[++cn].next = h[x];
			edge[cn].to = y;
			edge[cn].from = x;
			h[x] = cn;
			di[y] ++;
		}
	}
	printf("%d\n",topo());
	return 0;
}

Kosaraju算法

另一个比tarjan更好理解的求强联通分量的算法。
Kosaraju 算法依靠两次简单的 DFS 实现。
第一次 DFS，选取任意顶点作为起点，遍历所有为访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。
第二次 DFS，对于反向后的图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点，选取标号最大的，重复上述过程。
两次 DFS 结束后，强连通分量就找出来了
证明： 如果点A在连正向边时可以到达点B，点A在连反向边时也能到达点B，那么我们就可以判断，点A和点B是可以互相到达的。
code：

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
void positive_dfs(int pos){
    DFN++;
    vis[pos]=1;
    for(int i=pre[1][pos];i;i=E[1][i].next)
        if(!vis[E[1][i].to])
            positive_dfs(E[1][i].to);
    stack[N*2+1-(++DFN)]=pos;
}
void negative_dfs(int pos){
    dye[pos]=CN;
    vis[pos]=0;
    size[dye[pos]]++;
    for(int i=pre[2][pos];i;i=E[2][i].next)
        if(vis[E[2][i].to])
            negative_dfs(E[2][i].to);
}
int main(){
        ...... 
    for(int i=1;i<=N;i++)
        if(!vis[i])
            positive_dfs(i);
    for(int i=1;i<=N*2;i++)
        if(stack[i]&&vis[stack[i]]){
            CN++;
            negative_dfs(stack[i]);
        }
        ......
    
}

推荐习题：https://www.luogu.org/problemnew/show/P1262

二分图

定义&性质

  • 节点由两个集合组成，且两个集合内部没有边的无向图
  • 重要性质：二分图不包括奇环。可用来做二分图的判定

    匈牙利算法

    求最大匹配
    每次寻找增广路径，都可以使得匹配数+1
    因此，不断递归寻找可能存在的增广路径，就可以得到二分图的最大匹配

1563498105513

1563497834012

如图，这就是一条增广路，粗边为选中的边。我们可以发现，对于一条增广路，如果我们删掉选中的边，加入未选的边，边数（匹配数）就会加1。

查分约束

差分约束系统：由N个变量X_1, X_2, X_3 …. X_N和M个未知条件组成的N元一次不等式组，其中，每个条件都形如
X_i <= X_j + c_k
我们的问题是：给出一组满足所有条件的解，否则判断出无解

注意到，X_i <= X_j + c_k 与单源最短路中的三角不等式很相似，建立N个节点对应N个变量。对于每组条件，从 j 向i连一条边。同时虚构0号节点并向每一个节点连一条边，如果存在负环则无解。否则有解。

最近公共祖先

考虑到一步一步跳太慢，我们考虑有没有快一点的跳法
设fa[i][j] 表示节点i 的第2^j 个祖先是谁，fa[x][i] 可以预处理得到

考虑如何对朴素算法进行优化：
1。 调整到同一高度
2。 一起同时往上跳

略微占空间，并不是最优的LCA算法

code:

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int n,m,s,x,y,cnt,d[1000005],f[500005][50],dp[500005];

struct edge{
	int to,next;
}e[1000005];

void add(int x,int y)
{
	e[++cnt].to = y;
	e[cnt].next = d[x];
	d[x] = cnt;
}

void dfs(int u,int fa)
{
	dp[u] = dp[fa] + 1;
	f[u][0] = fa;
	for(int i = 1; i <= 23; i++) f[u][i] = f[f[u][i - 1]][i - 1];
	for(int i = d[u]; i; i = e[i].next)
	{
		if(e[i].to == fa) continue;
		dfs(e[i].to,u);
	}
}

int lca(int a,int b)
{
	if(dp[a] > dp[b]) swap(a,b);
	int dis = dp[b] - dp[a];
	for(int i = 22; i >= 0; i--)
	{
		int d = 1 << i;
		if(d <= dis)
		{
			dis -= d;
			b = f[b][i];
		}
	}
	if(a == b) return a;
	for(int i = 22; i >= 0; i--)
	{
		if(f[a][i] == f[b][i]) continue ;
		a = f[a][i];
		b = f[b][i];
	}
	return f[a][0];
}

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1; i < n; i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(s,0);
	for(int i = 1; i <= m; i ++)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

贪心

基本思想

贪心是一种解题策略，更多是一种解题思想

使用贪心方法需要注意局部最优与全局最优的关系（用于区分贪心和动态规划），选择当前状态的局部最优并不一定能推导出问题的全局最优

利用贪心策略解题，需要解决两个问题：
该题是否适合于用贪心策略求解。
如何选择贪心标准，以得到问题的最优解 。

贪心问题的特点

可以通过局部的贪心选择来达到问题的全局最优解，运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择后，原问题将变成一个相似的，但规模更小的问题，之后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。

原问题的最优解包含子问题的最优解，即具有最优子结构的性质，但并不是所有具有最优子结构的问题都可以用贪心策略求解。

分治

思想

分治分治，分而治之，分治算法就是将一个大问题划分为几个更小规模的形式相同的子问题并加以解决，通过解决子问题最后解决总问题。
分治算法在OI中的运用主要在两个方面

  1. 二分查找、三分查找、二分答案

  2. 直接考察分治

二分答案

常见于最小值最大或者最大值最小问题（基本上可以把这看做二分答案的标志）
要求：

  1. 如果答案确定，我们能够快速判断答案是否合法

  2. 答案具有可二分性，即如果答案为i是可行的，答案为i+1即可行
    作用
    牺牲log(n)的复杂度，把求最优化问题变成了一个判断是否可行的问题，有时候能够简化问题。关键在于转化后的问题更好求解。

    三分

    三分的难度要略低于二分(因为扩展出来的形式少)
    三分的用处在于求一个单峰函数的最值
    单峰函数，例如：

1563676962842

code:

1563676984538

动态规划

一维线性DP

比较常见的一种动态规划问题，特点是状态只有一维
例题：

1563495230032

1563495511093

但是时间复杂度是$O(n^2)$。
优化：
记录f[x]为当前时刻dp值为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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define INF 0x7fffffff 

using namespace std;

int n,a[100005],sta[100005],t;

void two_fen(int k)
{
	int l = 1, r = t, mid;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(sta[mid] >= k) l = mid + 1;
		else r = mid - 1; 
	}
	sta[l] = k;
}

void work()
{
	sta[0] = INF; t = 0;
	for(int i = 1; i <= n; i++)
	{
		if(a[i] <= sta[t]) sta[++t] = a[i];
		else two_fen(a[i]);
	}
	//for(int i = 1; i <= t; i++) cout << sta[i] << "  ";cout <<endl;
	printf("%d\n",t);
}

void count()
{
	memset(sta,0,sizeof(sta));
	int j,place,x;
	t = 0;
	for(int i = 1; i <= n; i++)
	{
		place = 0; x = INF;
		for(int j = 1; j <= t; j++)
			if(sta[j] >= a[i] && (sta[j] < sta[place] || place == 0))
				place = j;
		if(place == 0) sta[++t] = a[i];
		else sta[place] = a[i];
	}
	printf("%d\n",t);
}

int main()
{
	while(cin >> a[++n]); 
	n --;
	work();
	count();
	return 0; 
}

1563498505799

设d[i]为长度为n的错排的种类数，考虑构造一个错排序列。
$d[1] = 0$
$d[2] = 1$
$d[n]=(d[n-1] + d[n-2])*(n-1) (n >= 3)$

1563499267952

$f[n] = f[n-1] + f[n-2]*2$

1563499947317

考虑这样几种情况：
运一个人：a[n] ： $t=a[1]+a[n]$
但这样不是最优的
若还剩a[n]和a[n-1]，则一个一个运：
$t=a[1]+a[n-1]+a[1]+a[n]$
但如果让a[n]和a[n-1]一起走，则：
$t=a[1]+a[n]+a[2]+a[2]$
所以我们有两种方案：
第一种
让过河时间最少的人过来送手电筒，然后带着你一起过河。
第二种
让过河时间最少的人过来送手电筒，然后你带着n-1号一起过河，此时手电筒在对岸，接着让过河时间第二少的人过来送手电筒，带着过河时间最少的人一起过河。
所以我们建立一个dp[i]来记录前i个人过河的最短时间。那么转换方程为
$$dp[i] = min(p[i - 1] + a[0] + a[i], dp[i -2] + a[0] + a[i] + 2 * a[1]);$$

背包问题

严格来说，背包问题并不是一个单独的问题，他是一系列比较类似的问题的总称
请注意，并非所有的背包问题都是动态规划问题

0-1背包

有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
对于一个物品，只有两种情况
　　情况一: 第i件不放进去，这时所得价值为:$f[i-1][v]$
　　情况二: 第i件放进去，这时所得价值为：$f[i-1][v-c[i]]+w[i] $
状态转移方程为：$f[i][v] = max(f[i-1][v], f[i-1][v-w[i]]+c[i])$

最终的答案是 $Max(f[N][j] for\ j \ in [0,maxV])$

code:

1
2
3
4
int f[100005];
for(int i = 1; i <= n; i++)
	for(int j = v; j >= w[i]; j--)
		f[i][j] = max(f[i][j],f[i][j - w[i]] + v[i]);

完全背包

N件物品和一个容量为V的背包。第i种物品的价格（即体积，下同）是w[i]，价值是c[i]，每种物品有无限多个。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
完全背包和01背包十分相像， 区别就是完全背包物品有无限件。由之前的选或者不选转变成了选或者不选，选几件。
用f[i][j]表示前i种背包装入容量为j的背包中所可以获得的最大价值
对于一种物品，只有两种情况
　　情况一: 第i件不放进去，这时所得价值为:$f[i-1][v]$
　　情况二: 第i件放进去，这时，我们需要枚举放进去多少件，设为K，所得价值为：$f[i-1][v-Kc[i]]+Kw[i] $
状态转移方程为：$f[i][v] = max(f[i-1][v-Kw[i]]+Kc[i]) 0<=K<=v/w[i]$

最终的答案是 $Max(f[N][j] for \ j \ in [0,maxV])$

code:

1
2
3
for(int i = 1; i <= n; i++)
	for(int j = w[i]; j <= v; j++)
		f[i][j] = max(f[i][j],f[i][j - w[i]] + v[i]);

多重背包

有N件物品和一个容量为V的背包。第i种物品的价格（即体积，下同）是w[i]，价值是c[i]，第i种物品最多有n[i]件可用。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
用f[i][j]表示前i种背包装入容量为j的背包中所可以获得的最大价值

对于一种物品，只有两种情况
　　情况一: 第i件不放进去，这时所得价值为:$f[i-1][v]$
　　情况二: 第i件放进去，这时，我们需要枚举放进去多少件，设为K，所得价值为：$f[i-1][v-Kc[i]]+Kw[i]$
状态转移方程为：$f[i][v] = max(f[i-1][v-Kw[i]]+Kc[i]) 0<=K<=v/w[i]，K<= n[i]$
最终的答案是 $Max(f[N][j] for \ j \ in [0,maxV])$

那么，这样做的时间复杂度是多少呢？
$O(nW\sum k_i)$
轻松TLE没商量。
所以我们要对此进行二进制分解优化，处理后我们可以把多重背包转化成 0-1 背包模型来求解。
为了表述方便，我们用$A_{i,j}$表示第$i$种物品拆分出的第$j$个物品。

我们令$A_{i,j}$ 表示由$2^j$的单个物品组合成的一个更大的物品。如果$k_i+1$不是2的整数次幂，就需要再添加一个物品，该物品由二进制分解后剩余的物品组成。

举个例子：

  • $6=1+2+3$
  • $8=1+2+4+1$
  • $18=1+2+4+8+3$
  • $31=1+2+4+8+16$

显然，通过上述拆分方式，可以表示任意 $\leq k$个物品的等效选择方式。将每种物品按照上述方式拆分后，使用 0-1 背包的方法解决即可。

时间复杂度$O(nW\sum log \ k_i)$

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
index = 0;
for(int i = 1; i <= m; i++) {
    int c = 1, p, h, k;
    cin >> p >> h >> k;
    while(k - c > 0) {
        k -= c;
        list[++index].w = c * p;
        list[index].v = c * h;
        c *= 2;
    }
    list[++index].w = p * k; 
    list[index].v = h * k;
}

分组背包

有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。这N个物品分成了若干个组，每个组里面的商品不可以同时选择。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
code:

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=N;i++){
		for(int j=1;j<=A[i];j++){
			for(int k=0;k<=V;k++){
				dp[i][k] = max(dp[i][k], dp[i-1][k]);
				if(k>=v[i][j]){
					dp[i][k] = max(dp[i][k], dp[i-1][k-v[i][j]]+c[i][j]);
				}
			}
		}
	}

树形DP

这个地方是真的听懵了……
以后再填坑吧……

例题1：1563438728095
树上的动态规划如何写状态函数，怎么转移？
一般来说，绝大多数树上的一个节点i的状态函数都是对于以该点为根的子树的状态的概括。
好处：边界条件清晰（叶节点），无后效性，子树内部的具体情况与外界无关
以本题为例子：
总活跃指数最大（整棵树的活跃指数最大） —- 子树的活跃指数最大是多少？
code:
1563439966943
基环树
思路：先找到环，环以外的部分正常的树dp做，然后考虑断环
推荐习题 https://www.luogu.org/problemnew/show/P2607

状压DP

1563540552255

1563540571497

code:

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int read()
{
	int x = 0,f = 1; char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;}
	while(ch >= '0' && ch <= '9'){x = x * 10 + ch - 48; ch = getchar();}
	return x * f;
}

int n,cnt,kk,zt[2000],l[2000];
long long ans,f[10][20000][100];
void dfs(int j,int p,int s)
{
	if(p >= n)
	{
		zt[++cnt] = j;
		l[cnt] = s;
		return ;
	}
	dfs(j,p + 1,s);
	dfs(j + (1 << p),p + 2,s + 1);
}

int main()
{
	scanf("%d%d",&n,&kk);
	dfs(0,0,0);
	for(int i = 1;i <= cnt; i++) f[1][i][l[i]] = 1;
	for(int i = 2;i <= n; i++)
		for(int j = 1; j <= cnt; j++)
			for(int k = 1; k <= cnt; k++)
			{
				if(zt[j] & zt[k]) continue;
				if((zt[j] << 1) & zt[k]) continue;
				if(zt[j] & (zt[k] << 1)) continue;
				for(int s = kk; s >= l[j]; s--) f[i][j][s] += f[i - 1][k][s - l[j]];
			}
	for(int i = 1; i <= cnt; i++) ans += f[n][i][kk];
	printf("%lld\n",ans);
	return 0;
}

数位DP

问题模型：给定两个很大的正整数 a,b, 求在[a,b]内有多少数字满足性质 xxxxx

1563535090755

我们用f数组记录第i位以j开头的方案总数，然后累加就好了，这里就不详细说了（因为我真的不会……）。
code：

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
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long F[12][10];
int my_abs(int x){return x<0?-x:x;}
long long GetAns(long long x){
	if(x==0)return 1;
	long long ans = 0;
	long long now=0;
	int tmp[12],ct=0;
	long long t = x;
	while(t>0){ct+=1;t=t/10;}
	t = x;
	for(int i=1;i<=ct;i++){
		tmp[i] = t%10;
		t=t/10;
	}
	
	now=1;
	for(int i=1;i<ct;i++){
		for(int j=1;j<=9;j++){
			ans += F[i][j];
		}
		
	}
	
	for(int i=ct;i>=1;i--){
		if(ct==i){
			for(int j=1;j<tmp[i];j++){
				ans = ans + F[i][j];
			}
		} else {
			for(int j=0;j<tmp[i];j++){
				if(my_abs(j-tmp[i+1])<2){
					continue;
				}
				ans = ans + F[i][j];
			}
			if(my_abs(tmp[i]-tmp[i+1])<2){
				break;
			}
		}
	}
	return ans;
}

int main(){
	for(int i=0;i<=9;i++)F[1][i] = 1;
	for(int i=2;i<12;i++){
		for(int j=0;j<=9;j++){
			F[i][j]=0;
			for(int k=0;k<=9;k++){
				if(my_abs(j-k)<2){
					continue;
				}
				F[i][j] += F[i-1][k];
			}
		}
	}
	
	long long L, R;
	cin >> L>>R;
	cout<<GetAns(R+1)-GetAns(L)<<endl;
	return 0;
}

对拍

想要对拍，我们需要这样几个部分：

  • 想要判断对错的代码
  • 暴力代码
  • 一个数据生成器
  • 一个用来对拍的程序

我们以这个题为例

1563669191014

不确认对错的代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;

int main()
{
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	long long a, b;
	cin >> a >> b;
	cout << a * b - a - b << endl;
	return 0;
}

暴力代码：

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
#include <cstdio>
using namespace std;

bool ok(int n, int a, int b)
{
	for (int x = n/a; x >= 0; -- x)
		if ((n - a * x) % b == 0) return true;
	return false;
}

int main()
{
	freopen("a.in", "r", stdin);
	freopen("a_std.out", "w", stdout);
	int a, b;
	scanf("%d%d", &a, &b);
	for (int i = 1000000; i >= 0; -- i) 
		if (! ok(i, a, b)) 
		{
			printf("%d\n", i);
			break;
		}
	
	return 0;
}

数据生成器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;

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

int main()
{
	srand((int)time(0));
	freopen("a.in", "w", stdout);
	int a, b;
	do {
		a = rand() % 50 + 2;
		b = rand() % 50 + 2;
	} while (gcd(a, b) > 1);
	cout << a << " " << b << endl;
	return 0;
}

对拍程序：

1
2
3
4
5
6
7
8
@echo off
:1
gen
a
brute_force
fc a.out a_std.out
if %errorlevel% == 0 goto 
pause
Author: wflight
Link: http://yoursite.com/2019/08/02/2019清北夏令营/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
图论 数论 贪心 动态规划 数据结构 分治 对拍
Donate
  • 微信
  • 支付寶
Recommend
2019国庆清北刷题营
题解 P1268 【树的重量】
题解 P1447 【[NOI2010]能量采集】
题解 P4447 【[AHOI2018初中组]分组】
Comment
繁