放在前面的话:

​ 这份笔记是在大二下刚开学的时候进行书写的,主要参考的是Acwing的蓝桥杯辅导课,笔者在成体系的学习算法之前已经学习过基本的数据结构,以及离散数学。(PS: y总讲课很好,如果可以建议报一下试试)

基础概念

1s内c++可以运算一亿次即1e8次,因此我们的最大次数小于1e7到1e8之间便可以

int的范围约为[-2e9,+2e9],最大值可以通过 0x7fffffff 来表示,long long的范围是 [- 1e18,+1e18]

由数据范围反推算法复杂度以及算法内容:

image-20240412192522712

下取整 (int)直接除

上取整:转化成下取整

image-20240314212814712

image-20240314213050728

输入技巧

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++;
}

递归与递推

递归:把问题分成若干个相同子问题

递推:由子问题推出最终问题

二分

整数二分

  • 确定一个区间使得答案一定在一个区间里

  • 找一个性质,满足两点:

    性质具有二段性

    答案是二段性的分段点(有两种情况,一种是前段的终点a,一种是后段的起点b,a与b不重合)

image-20240307215445608

image-20240307215206733

y总模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
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;
}

记忆技巧:

如果我们想要的点x是左部分的右端点,则区间分为 [l,mid-1] ,[mid,r]

如果我们想要的点x是右部分的左端点,则区间分为 [l,mid] ,[mid+1,r]

即我们想要的x是什么方向的端点,mid就在哪个部分,只要l=mid出现计算mid的时候一定要加一

前缀和

一定要将下标加一,不然遇见s[i-1]会出问题

一维前缀和

利用数列的思想:

SrSl=al+1+al+2+...+arS_r-S_l=a_{l+1}+a_{l+2}+...+a_{r}

二维前缀和

与一维前缀和思想类似:

容斥原理:

在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理

1.计算前缀和矩阵

S(x,y)=S(x1,y)+S(x,y1)S(x1,y1)+a(x,y)S_{(x,y)} = S_{(x-1,y)}+S_{(x,y-1)}-S_{(x-1,y-1)}+a_{(x,y)}

2.利用前缀和矩阵计算子矩阵的和

S(x1,y1),(x2,y2)=S(x2,y2)S(x2,y11)S(x11,y2)+S(x11,y11)S_{(x_1,y_1),(x_2,y_2)} = S_{(x_2,y_2)}-S_{(x_2,y_1-1)}-S_{(x_1-1,y_2)}+S_{(x_1-1,y_1-1)}

差分

前缀和的逆应用

在指定的区间内统一加上或者减去一个数字

image-20240412195444573

输入一个 n 行 m列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c1,1,2,2,,其中 (x1,y1)和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 n,m,q,。

接下来 n 行,每行包含 m 个整数,表示整数矩阵。

接下来 q 行,每行包含 55个整数 x1,y1,x2,y2,c表示一个操作。

输出格式

共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

输入样例:

1
2
3
4
5
6
7
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例:

1
2
3
2 3 4 1
4 3 4 1
2 2 2 2
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
#include<iostream>
#include<cstdio>

using namespace std;
const int N = 1010;
int a[N][N],n,m,q;

int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int x;
scanf("%d",&x);
a[i][j]+=x;
a[i+1][j]-=x;
a[i][j+1]-=x;
a[i+1][j+1]+=x;
}
}
int x1,y1,x2,y2,c;
for(int i=1;i<=q;i++)
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
a[x1][y1]+=c;
a[x2+1][y1]-=c;
a[x1][y2+1]-=c;
a[x2+1][y2+1]+=c;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%d ",a[i][j]);
puts("");
}
return 0;
}

一维差分

二维差分

数学知识

尽力分析

打表找规律

裴蜀定理

image-20240412201207067

image-20240412201220057

image-20240314210202079

最大公因数

1
2
3
4
5
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

朴素筛质数

1
2
3
4
5
6
7
8
9
10
11
12
13
int primes[N], cnt;     // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}

枚举 模拟 排序

归并排序模板

计算逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LL merge_sort(int q[],int l,int r)
{
LL cnt=0;
if(l>=r) return 0;
int mid=l+r>>1;
cnt+=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j]) tmp[k++]=q[i++];
else
{
cnt+=mid-i+1;////key
tmp[k++]=q[j++];
}

}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
return cnt;
}

树状数组与线段树

前者精密 后者处理范围广

image-20240324104634741

image-20240324105942645

image-20240324110501255

image-20240324194807646

image-20240324195124747

线段树节点的个数最多是4n,存储方式和堆的存储方式一样,使用一维数组存储,下标为x的节点的父节点是x/2(x>>1) 左儿子是2x 右儿子是2x+1

位运算

求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;
}

高精度计算

大数加法

课程

没有考虑负数的情况

b站大数加法

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
string vector2string(vector<int>& x, int s, bool flag = 1)//flag为1则x为正数
{
string ans(s, '0');
for (int i = 0; i < s; i++)
{
ans[i] = '0' + x[i];
}
reverse(ans.begin(), ans.end());//倒置
if(!flag) ans.insert(0,"-");//如果为负数在数字前面添加负号
return ans;
}
string add(string& num1, string& num2)
{
vector<int> a(num1.size(), 0);
vector<int> b(num2.size(), 0);
for (int i = 0; i < num1.size(); i++)
{
a[num1.size() - i - 1] = num1[i] - '0';
}
for (int i = 0; i < num2.size(); i++)
{
b[num2.size() - i - 1] = num2[i] - '0';
}
vector<int> c(num1.size() + num2.size(), 0);
int len = num2.size();
if (num2.size() > num1.size()) len = num1.size();
int i = 0;
for (i = 0; i < len; i++)
{
c[i]+= a[i] + b[i];
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
//位数较长的数平移加上对应位置的c[i]
if (num1.size() > num2.size())
{
for (; i < num1.size(); i++)
c[i] += a[i];
}
if (num1.size() < num2.size())
{
for (; i < num2.size(); i++)
c[i] += b[i];
}
len = num1.size();
if (num2.size() > num1.size()) len = num2.size();
while (c[len] == 0)//去除前导0
{
len--;
}
string ans = vector2string(c, len + 1);//转换为string

return ans;
}

练习

力扣 字符串加法

大数减法

课程

b站

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
string divide(string& num1, string& num2)
{
char flag = '+';
if (num1.size() < num2.size() || (num1.size() == num2.size() && num1 < num2))
{
swap(num1, num2);
flag = '-';
}
vector<int> a(num1.size(), 0);
vector<int> b(num2.size(), 0);
for (int i = 0; i < num1.size(); i++)
{
a[num1.size() - i - 1] = num1[i] - '0';
}
for (int i = 0; i < num2.size(); i++)
{
b[num2.size() - i - 1] = num2[i] - '0';
}
vector<int> c(num1.size(), 0);
int len = num2.size();
int i = 0;
for (i = 0; i < len; i++)
{
if (a[i] < b[i])
{
a[i] += 10;
a[i + 1]--;
}
c[i] += a[i] - b[i];
}
for (; i < num1.size(); i++)
c[i] += a[i];
len=c.size()-1;
while (c[len] == 0)
len--;

string ans;
if (flag == '-')
{
ans = vector2string(c, len + 1, 0);
}
else
ans = vector2string(c, len + 1);
return ans;
}

大数乘法

b站 高精度算法

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
string mulity(string& num1, string& num2)
{
vector<int> a(num1.size() + 1, 0);
vector<int> b(num2.size() + 1, 0);
vector<int> c(num1.size() + num2.size() + 1, 0);
int i = 0;
for (i = 0; i <= num1.size(); i++)
{
a[num1.size() - i] = num1[i] - '0';
}
for (i = 0; i <= num2.size(); i++)
{
b[num2.size() - i] = num2[i] - '0';
}
int j = 0;
for (i = 1; i <= num2.size(); i++)
{
for (j = 1; j <= num1.size(); j++)
{
c[i + j - 1] += b[i] * a[j];
c[i + j] += c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
}
int len = c.size() - 1;
while (c[len] == 0)
{
len--;
}
string ans = vector2string(c, len + 1);
ans = ans.substr(0, ans.size()-1);
return ans;
}

动态规划(dp)

暴力dfs->记忆化搜索–>递推(dp)

记忆化搜索 = 暴力dfs+记录答案

递推的公式 = dfs向下递归的公式

dp的重点在于状态转移方程,即从树的最下层向上归的过程

跳楼梯

大盗阿福

背包问题

  • 状态表示

  • 状态计算

    image-20240315092802200

    image-20240315093548155

注意:右边的子集不一定存在只有 当 j >= v[i]的时候才存在

之后转化为一维

0-1背包问题

已知一个背包容积为V,现在有N个物品,每个物品有一个价值Wi,一个体积Vi,每件物品最多用一次,求可以选择的总价值最大。

完全背包问题

每件物品有无限个

多重背包问题

每个物品有有限个

分组背包问题

每一组最多选择一个物品

[mid+1, r]: