笔记-改
2023-07-30 13:53:26
发布于：广东
2阅读
0回复
0点赞
截止至27日上午（全打完讨论放不下）
原帖地址
现在这个txt比我复制时多了一倍左右qwq
7月22日上午：
通俗地讲，算法是解决一系列问题的清晰步骤和方法，是准确解决问题方案的完整描述，
是对有一点规范的输入，在有限的时间内获得所要求的输出的这种能力的表达。
一个合格的算法，具备五个特性：
1.有穷性：一个合格的算法必须在执行完有穷（有限）步骤后再结束且有时间限制；
2.确定性：算法的步骤规定，含义和执行方法都是非常明确的；
3.可行性：所有操作都可实现；
4.输入：算法有多个或者零个输入；
5.输出：与输入一样，算法有多个或零个输出。没有输出（结果）的算法没有意义；
7月22日下午
STL：Standard Template Library 标准模板库，一般将这些模板称之为“容器”
常用容器包括string vector set map queue等。
vector：容器内元素访问：
1.通过下标访问，类似普通数组，下标从0开始
2.通过迭代器访问：vector<DataType>::iterator it;
常用成员函数(设 vector 容器名 val)：
函数名 功能 时间复杂度
val.push_back(data) 对val向后插入data数据 O(1)
val.pop_back() 删除val尾数据 O(1)
val.size() 当前val内元素个数 O(1)
val.clean() 清空当前val容器 O(N)
val.begin() 起始迭代器 -
val.end() 末尾迭代器 -
val.empty() 判空 -
set：容器内元素访问：
只能通过迭代器访问：set<DataType>::iterator it;
常用成员函数(设 set 容器名 val)：
函数名 功能 时间复杂度
val.insert(data) 对val插入data数据 O(1)
val.erase(it) 1.删除一个迭代器it所指的位置 O(1)
2.删除一个值为it的数据 O(log(n))
val.erase(first,last) 3.删除迭代器于[first,last)的数据 O(last-first)
val.size() 当前val内元素个数 O(1)
val.clean() 清空当前val容器 O(N)
val.begin() 起始迭代器 -
val.end() 末尾迭代器 -
val.find(data) 在val中查找data O(log(n))
map：容器内元素访问：
1.通过“下标”访问，即键值对访问，例如map['name']。
2.通过迭代器iterator访问元素：
map<DataType1,DataType2>::iterator it;
迭代器指代的是一个键值对对象:
用it->first访问键(DataType1)，it->second访问值(DataType2)。
常用成员函数(设 map 容器名 mp)：
函数名 功能 时间复杂度
mp.erase(it) 1.删除一个迭代器it所指的位置 O(1)
2.删除一个键为it的数据 O(log(n))
mp.erase(first,last) 3.删除迭代器于[first,last)的数据 O(last-first)
mp.size() 当前mp内,键的个数 O(1)
mp.clean() 清空当前mp容器 O(N)
mp.begin() 起始迭代器 -
mp.end() 末尾迭代器 -
mp.find(data) 在mp中查找键data O(log(n))
7月23日上午：
前缀和：
前缀和是指一段序列的前n项之和，可以理解为数学中，数列的前n项之和。
下标位置 0 1 2 3 4 5 6
数据数组a 0 4 3 2 5 9 6
数据数组b 0 4 7 9 14 23 29
b[1] = a[1] 令b[i] = a[1]+a[2]+…+a[i-1]+a[i]
b[2] = a[1] + a[2] 则b[i-1]=a[1]+a[2]+…+a[i-1]
b[3] = a[1] + a[2] + a[3]…… 有b[i] = b[i-1]+a[i]
区间和：
区间和往往是值一段序列连续某段连续区间之和。
下标位置 0 1 2 3 4 5 6
数据数组a 0 4 3 2 5 9 6
前缀和数组b 0 4 7 9 14 23 29
推广到[L,R]区间和：ans = a[L]+a[L+1]+a[L+2]+…a[R]
可知前缀和h[R]=a[1]+a[2]+…+a[L-1]+a[L]+a[L+1]+…+a[R]
整理算式得b[R]=b[L-1]+ans 因此 [L,R]区间和：ans=b[R]-b[L-1]
差分区间修改:
问题表述：
对序列区间[L,R]中的每个数都加上c。
思路分析：
对d[L]增加c将使得a[L]及之后的数据都增加c。
对d[L]减少c将使得a[R+1]及之后的的数据减少c。
两种操作同时操作 则易知从a[R+1]开始之后的数据
因+c-c而无变化。
时刻牢记：
差分是前缀和的逆运算。
7月23日下午
递归：
根据递归调用自身的位置不同，数量不同，可以将递归执行大致分为：
前置递归，后置递归，前后混合递归。
7月23日晚上
初赛知识点：
宏定义
#define ll long long
在编译时将所有ll替换为long long
进制转化
-整数
除x取余，逆序排列
-小数
乘x取整，顺序排列
原码
由符号位和数值位表示。符号位为最左边的位，为0表示正数，为1表示负数
14-0000 1110
-14-1000 1110
反码
反码也是由符号位和数值位表示。符号位为最左边的位，为0表示正数，为1表示负数。正数的原码与反码相同。
补码
补码也是由符号位和数值位表示。符号位为最左边的位，为0表示正数，为1表示负数。正数的原码与补码相同，补码等于反码+1。
-14(原码)-1000 1110
反码-1111 0001
补码-1111 0010
位运算
程序中的所有数在计算机内存中都是以二进制的形式储存的。
位运算就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。
按位与 & - 7&10=0011
按位或 | - 5|9=1101
按位异或(相同为0，不同为1) ^ - 5^9=1100
按位取反 ~
按位右移(右移一位，高位补零，低位丢弃) >> - 9>>2=0011 (/2的x次方)
按位左移(右移一位，高位丢弃，低位补零) << (*2的x次方)
7月24日上午
贪心：
贪心算法，又称贪婪算法，是指在对问题求解时，模拟一个“贪心”的人做出决策的过程。
在每次做出决策的时候都采用当前看来最好的选择，不从整体最优上去考虑，
他所做出的仅是在某种意义上的局部最优解，所以贪心算法不是对于所有问题都能够得到最优解，
关键是选择贪心的策略。
贪心算法需要具备的特征：
1.贪心的选择：一个问题的整体最优解，能够通过一系列局部的最优解的选择
达到。每次的选择可以依赖以前做出的选择，但不依赖于后面要做出的选择，
这就是贪心选择性质
2.最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。
问题的最优子结构性质是该问题可用贪心法求解的关键所在。
7月24日下午
二分搜索：
二分搜索，又名二分查找，折半查找。从算法大类来讲，属于分治的策略。
经典的二分搜索例子，猜数字。
顾名思义，每次将搜索规模缩小一半，因此搜索的时间复杂度为：O(logN)
二分模版：
寻找x
int binSearch(int a[],int x,int left,int right){
while(left<=right){
int mid=(left+right)/2;
if(x==a[mid]){
return mid;
}else if(x>a[mid])
left=mid+1;
}else{
right=mid-1;
}
}return -1;
}
大于等于x
int BinarySearch(int b[],int left,int right,int x){
int midd=-1;
while(left<=right){
int mid=(left+right)/2;
if(b[mid]>=x){
midd = mid;
right = mid-1;
}
else if(x>b[mid]){
left=mid+1;
}
}
return midd;
}
大于x
int BinarySearch(int b[],int left,int right,int x){
int midd=-1;
while(left<=right){
int mid=(left+right)/2;
if(b[mid]>x){
midd = mid;
right = mid-1;
}
else{
left=mid+1;
}
}
return midd;
}
函数：所需头文件：#include<algorithm>
使用前提：递增序列，如递增数组
作用：
lower_bound (a, a + n, x)
在[a, a + n)区域内二分搜索第一个大于等于目标值 x 的地址。
upper_bound (a, a + n, x)
在[a, a + n)区域内二分搜索第一个大于目标值 x 的地址。
若该值存在，返回该值的地址，若该值不存在，返回a+n这个地址。
地址换算为数组中的下标
int v = lower_bound (a, a + n, x) - a
int v = upper_bound (a, a + n, x) - a
7月25日上午：
7月25日下午：
归并排序：
归并排序，又名二路归并排序。顾名思义，该排序算法涉及了二分的思想
即将原数列不断的平均拆分成两个子部分，再分别对子部分分别进行处理。
而“并”字,则意味着，将处理好地子部分再有序地合并起来。
归并排序步骤：
(1)令 mid=(R+L)/2 将[L,R]拆为[L,mid]于[mid+1,R]
(2)若L < mid,则将[L,mid]作为新[L,R]跳转(1),否则跳转(3)
(3)若mid + 1 < R,则将[mid+1,R]作为新[L,R]跳转(1),否则跳转(4)
(4)有序合并[L,mid]于[mid+1,R]
归并排序代码：
// 将a数组的 [L1,R1] 和 [L2,R2] 区间元素进行归并
void merge(int a[],int L1,int R1,int L2,int R2){
int i=L1,j=L2,cnt=0;
// 两个范围都没有越界
while(i<=R1&&j<=R2){
if(a[i] <= a[j]) tmp[cnt++] = a[i++];
else tmp[cnt++] = a[j++];
}
// 前半段还有元素
while(i<=R1) tmp[cnt++] = a[i++];
// 后半段还有元素
while(j<=R2) tmp[cnt++] = a[j++];
// 将数组 tmp(0~cnt-1) 复制到数组 a(L1,R2)
for(int i=0;i<cnt;i++){
a[L1+i] = tmp[i];
}
}
// 将数组 a 区间 [l,r] 的元素进行升序排列
void MergeSort(int a[],int l,int r){
// 只有一个元素，无法再划分，返回
if(l>=r){
return;
}
// 求中间元素位置
int mid = (l+r)/2;
// 对前半段 [l,mid] 继续递归划分
MergeSort(a,l,mid);
// 对后半段 [mid+1,r] 继续递归划分
MergeSort(a,mid+1,r);
// 归并区间 [l,mid] 和 [mid+1,r] 的元素
merge(a,l,mid,mid+1,r);
}
快速排序：
快速排序，简称快排，排序的核心逻辑是拆。但这个拆法于归并排序不同，
归并是单纯的拆开,快排是寻找一个基准值val,将数列拆分不小于val的部分
和不大于val的部分。然后对两个拆出来的部分重负这个拆分行为，直到
不可再拆为止
1.选择枢纽(一般是序列第一个数)
2.比枢纽小(大)，移到枢纽的前面
3.比枢纽大(小)，移到枢纽的后面
4.对新的两个子序列，再次重复上述步骤。
（1.不断将j--，j指向最后一个元素，当i<=j时重复以下步骤
2.不断将j--，直到a[j]<=key
3.不断将i++，直到a[i]>=key
4.如果i<=j，交换a[i]和a[j],i++,j--）
快速排序代码：
void QuickSort(int a[],int l,int r){
if(l>=r){
return;
}
int key=a[(l+r)/2],i=l,j=r; // key选中间元素 i指向第一个位置 j指向最后一个位置
// 通过这样一个while就可以将<=key的放在l~i-1 >=key的放在i~r
while(i<=j){
while(a[j]>key) j--; // 从右向左找到第一个<=key的
while(a[i]<key) i++; // 从左向右找到第一个>=key的
if(i<=j){
swap(a[i],a[j]);
i++;j--;
}
QuickSort(a,l,i-1);
QuickSort(a,i,r);
}
}
高精度：
高精度加法：
1.读入和存储
输入：
string s/char s[]
存储：
int a[](方便计算/相同数位对齐)
s[len-1] = a[0]
......
2.做加法（进位）
1.从个位开始，逐位相加，满10进1
2.枚举的范围（c的下标范围）
0~lenc-1 lenc=max(len(a),len(b))
3.判断最高位的进位情况
4.逆序输出
高精度减法：
1.读入、比较和存储
输入：
string s/char s[]
比较：
若被减数<减数，则交换并输出负号
①比位数，位数多的数大
②位数一样，从高位到低位按位比大小
逆序存储：
int a[](方便计算/相同数位对齐)
s[len-1] = a[0]
......
2.做减法（借位）
1.从个位开始，逐位相加，满10进1
2.枚举的范围（c的下标范围）
0~lenc-1 lenc=max(len(a),len(b))
3.判断最高位的进位情况
4.逆序输出
高精度乘法：
1.读入存储
输入：
string s/char s[]
逆序存储：
int a[](方便计算/相同数位对齐)
s[len-1] = a[0]
......
2.做乘法（进位）
a[i+j] += a[i] * b[i]
满10向前一位进位
先认为结果是两个乘数的的长度的和
1.从个位开始，逐位相加，满10进1
2.枚举的范围（c的下标范围）
0~lenc-1 lenc=max(len(a),len(b))
3.判断最高位的进位情况
4.逆序输出
高精度除法：
1.读入和存储
输入：
string s/char s[]
顺序存储：
int a[](方便计算/相同数位对齐)
s[i]='0' = a[i]
......
2.做除法
a[i+j] += a[i] * b[i]
满10向前一位进位
先认为结果是两个乘数的的长度的和
1.从个位开始，逐位相加，满10进1
2.枚举的范围（c的下标范围）
0~lenc-1 lenc=max(len(a),len(b))
3.判断最高位的进位情况
4.逆序输出
3.去除前导零
7月25日晚上：
排列数
从n个不同的元素中，任取m个不同的元素按照一定的顺序排成一列，所有排列的个数，叫做从n个不同的元素中取出m个元素的排列数，以A(n,m)表示
计算：A(n,m) = n*(n-1)*(n-2)* ... *(n-m+1)
分子分母同时乘以(n-m)!
A(n,m) = n!/(n-m)!
组合数
从n个不同的元素中，任取m个元素叫做从n各不同元素中取出m个元素的组合
从n个不同的元素中取出m个元素的组合数，以*****)表示
计算：
A(n,m) = n!/(n-m)!
*****) = A(n,m)/m! = n!/[(n-m)!*m!]
递推式：
①不取第一个元素-从(n-1)个元素取m个元素的组合数C(n-1,m)
②取第一个元素-从(n-1)个元素取(m-1)个元素的组合数C(n-1,m-1)
*****) = C(n-1,m)+C(n-1,m-1);
-当m=1 从n个中取出1个 C(1,n) = n
-当m=0 从n个中取出0个 C(0,n) = C(n,n) = 1
-从n个中取出m个与从n个中取出n-m个等价
*****) = C(n,n-m)
递推方法：
用递推的方法求组合数，f[i][j]表示C(i,j)
初始状态：f[0][0]=1 f[0][n]=1
i=j时：f[i][j]=1
其余情况可以递推：f[i][j] = (f[i-1][j-1]+f[i-1][j])
7月26日下午:
队列：
入队操作，是指向一个队列插入新元素。
（当head与tail相等时 队列为空）
出队操作，是指向一个队列删除队头元素
（根据队列的性质，从队头开始删数据，遵循先进先出原则）
深度搜索：右下左上
7月27日上午：
记忆化递归：
将每次递归的结果以数组存储，不需要每次调用。
有帮助，赞一个