课程

y总模板

常用代码模板2——数据结构

常用代码模板3——搜索与图论

小技巧

快速去重

1
2
3
4
5
6
先进行升序排序
// 使用 unique 去重并将结果压缩到前面
auto last = std::unique(vec.begin(), vec.end());

// 截取去重后的部分
vec.erase(last, vec.end());

读入技巧

1
2
3
getline(cin,line);
sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&hh1,&mm1,&ss1,&hh2,&mm2,&ss2,&dd);
//line.c_str() 是 C++ 中的一个方法,用于将 std::string 类型的字符串转换为 C 风格字符串(即以 \0 结尾的字符数组)
1
2
3
4
5
6
7
8
9
#include<string>
#include <sstream>
getline(cin,str);
while(cnt--)
{
getline(cin,str);
stringstream ssin(str);
while(ssin>>a[n]) n++;
}

排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
//用j的情况下应当保证x取不到左边界,用i要保证取不到右边界,
}

作者:yxc
链接:https://www.acwing.com/blog/content/277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];

while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

作者:yxc
链接:https://www.acwing.com/blog/content/277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

二分

有单调性一定可以二分,没有单调性也可能可以二分

整数二分

image-20240808190812596

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
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}


作者:yxc
链接:https://www.acwing.com/blog/content/277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

浮点数二分

控制精度来控制循环,精度要比题目所要求的多2(y总经验)

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}

高精度

算法_202408092113_02094 2

算法_202408092113_03934 3

加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);

vector<int> C;
int t = 0;//t代表上一位的进位,初始为0只有两种取值0或者1
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}

if (t) C.push_back(t);
return C;
}

作者:yxc
链接:https://www.acwing.com/blog/content/277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;//t代表上一位的借位初始为0 只有两种取值0或者1
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}

while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

作者:yxc
链接:https://www.acwing.com/blog/content/277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

乘法

高精度*低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;

int t = 0;//代表上一位的进位 t>=0
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}

while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0

return C;
}

作者:yxc
链接:https://www.acwing.com/blog/content/277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

除法

高精度除以低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

作者:yxc
链接:https://www.acwing.com/blog/content/277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

前缀和与差分

image-20241114212056491

image-20241114212111998

前缀和

一维前缀和

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 <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化

while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
}

return 0;
}

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/39796/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

子矩阵的和

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
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

int main()
{
scanf("%d%d%d", &n, &m, &q);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &s[i][j]);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

while (q -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}

return 0;
}

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/39797/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

差分

一维差分

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
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);//小技巧

while (m -- )
{
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}

for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];

for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

return 0;
}

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/39799/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

差分矩阵

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
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}

int main()
{
scanf("%d%d%d", &n, &m, &q);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &a[i][j]);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
insert(i, j, i, j, a[i][j]);//小技巧

while (q -- )
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
puts("");
}

return 0;
}

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/39800/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

双指针

image-20241117225214841

1
2
3
4
5
6
7
8
9
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;

// 具体问题的逻辑
}
常见问题分类:
(1) 对于一个序列,用两个指针维护一段区间
(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

位运算

基础操作

image-20241117225306326

1
2
3
4
//求n的第k位数字: 
n >> k & 1
//返回n的最后一位1:
lowbit(n) = n & -n

快速幂

image-20241001204959516

1
2
3
4
5
6
7
8
9
10
//对p做二进制拆分, 对n做平方倍增 -- O(log n)
ll quick_power(ll n, ll p){
ll res = 1;
while(p){ //如果指数不为0
if(p & 1) res *= n; // 如果对应二进制数的当前位为1, 则res 乘以当前位的值
n *= n; //对n进行倍增
p >>= 1; //指数右移1位
}
return res;
}

延申

64位整数乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

typedef unsigned long long ULL;

int main() {
ULL a, b, p;
cin >> a >> b >> p;//a*b 看成a个b相加
ULL res = 0;
while (a) {
if (a & 1) res = (res + b) % p;
b = (b + b) % p;
a >>= 1;
}
cout << res << endl;
return 0;
}

离散化

image-20241117225439611

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}

作者:yxc
链接:https://www.acwing.com/file_system/file/content/whole/index/content/3190/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

区间合并

image-20241117225456596

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void merge(vector<PII> &segs)
{
vector<PII> res;

sort(segs.begin(), segs.end());

int st = -2e9, ed = -2e9;//最左边
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);

if (st != -2e9) res.push_back({st, ed});

segs = res;
}

作者:yxc
链接:https://www.acwing.com/file_system/file/content/whole/index/content/3190/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

数学

高斯消元

应用

883.高斯消元解线性方程组

质因数分解

OI-wiki 分解质因数

867.分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<pair<int,int> > div(int x)
{
vector<pair<int,int> > res;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
int times=0;
while(x%i==0)
{
x/=i;
times++;
}
res.push_back(make_pair(i,times));
}
}
if(x!=1)
res.push_back(make_pair(x,1));
return res;
}

坐标旋转公式

(xy)=(cosαsinαsinαcosα)(xy)\left( \begin{array}{c} x^{'} \\ y^{'} \end{array} \right) = \left( \begin{array}{c} \cos\alpha&\sin\alpha \\ - \sin\alpha & \cos\alpha \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right)

数据结构

链表

不采用结构体+指针的做法,因为效率低下,采用数组模拟

![算法课程_202502181430_06788 11](算法课程_202502181430_06788 11.jpg)

![算法课程_202502181430_08625 12](算法课程_202502181430_08625 12.jpg)

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
head = -1;
idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除,需要保证头结点存在
void remove()
{
head = ne[head];
}

双链表

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
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
//0是左端点,1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}

栈与队列

![02502181437_07407 13](02502181437_07407 13.jpg)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空,如果 tt > 0,则表示不为空
if (tt > 0)
{

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// hh 表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空,如果 hh <= tt,则表示不为空
if (hh <= tt)
{

}

单调栈

AcWing 830. 单调栈

![算法课程_202502181437_07407 13](算法课程_202502181437_07407 13.jpg)

1
2
3
4
5
6
7
常见模型:找出每个数左边离它最近的比它大/小的数,栈中存储的是数组的下标
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}

单调队列

力扣–无重复字符的最长子串

![算法课程_202502181437_09401 14](算法课程_202502181437_09401 14.jpg)

1
2
3
4
5
6
7
8
常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}

KMP

KMP字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度,下标均从1开始
求模式串的Next数组:
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}

并查集

![算法课程_202502181451_21985 17](算法课程_202502181451_21985 17.jpg)

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
(1)朴素并查集:

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合:
p[find(a)] = find(b);


(2)维护size的并查集:

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}

// 合并a和b所在的两个集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集:

int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}

// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量

Trie树

字典树

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
int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点为结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}

![算法课程_202502181451_23639 18](算法课程_202502181451_23639 18.jpg)

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
// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置 数组下标-->堆中的下标
// hp[k]存储堆中下标是k的点是第几个插入的 堆中的下标--->数组下标
int h[N], ph[N], hp[N], size;

// 交换两个点,及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
//小根堆
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;//与左边子节点进行比较取小的
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//与右边子节点比较取小的
if (u != t)//将小的变为父节点
{
heap_swap(u, t);
down(t);
}
}

void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

哈希

一般哈希

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
(1) 拉链法
int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];//插入头部
h[k] = idx ++ ;//更新头指针
}

// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;

return false;
}

(2) 开放寻址法
int h[N];

// 如果x在哈希表中,返回x的下标;如果x不在哈希表中,返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}

字符串哈希

核心思想:将字符串看成P进制数,P的经验值是131或13331,取这两个值的冲突概率低
小技巧:取模的数用2^64,这样直接用unsigned long long存储,溢出的结果就是取模的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}

搜索

DFS与BFS

动态规划

用集合的思想思考动态规划问题,没有固定的代码模板,重在思想

背包问题

问题分类:

  • 0-1背包
  • 完全背包
  • 多重背包
  • 分组背包

0-1背包

完全背包

多重背包

分组背包

线性DP