算法基础篇（蓝桥杯常考点）

算法基础篇

前言

算法内容还有搜索，数据结构（进阶），动态规划和图论
数学那个的话大家也知道比较难，放在最后讲
这期包含的内容可以看目录
模拟那个算法的话就是题说什么写什么，就不再分入目录中了

注意事项：

1.多组测试时，一定要考虑需不需要清空数据

一般是能覆盖的话(没覆盖的部分不用就行了)不清空或者还能用就不清空

(权衡时间复杂度，清空是用时间换空间)

2.int类型的无穷大可以搞为 int inf = 0x3f3f3f3f

1.高精度

当数据的值特别大，各种类型都存不下的时候，要用高精度算法来加减乘除

步骤:

1.先用字符串读入这个数，然后用数组逆序存储该数的每一位

2.利用数组，模拟加减乘除运算的过程

高精度加法：(c= a+b，其字符串存在c[],a[],b[]中)
 例题：洛谷的 [P1601 A+B Problem（⾼精）]
la,lb是a,b的字符串长度
lc = max(la,lb)
for(int i = 0;i<lc；i++)
{
 c[i]=a[i]+b[i];//对应位相加
 c[i+1]=c[i]/10;//处理进位
 c[i]%=10;//处理余数
}
if(c[lc])lc++;//易忘，来让lc为c字符串的长度
这里字符串的长度不用数组求
读的时候先读成string，再用size()求字符串长度，最后for循环读到数组里（逆序存储）

高精度减法:(z = x - y)存储在z[],x[],y[]（逆序存储）
例题: 洛谷P2142 ⾼精度减法
要让大的数减小的数才行(判断方法如下：)
1.位数不等，按照字符串的长度比较
2.位数相等，用字典序比较
bool cmp(string&x,string&y)
{
if(x.size()!=y.size()) return x.size()<y.size();//比长度
 return x<y//比字典序
 }
 if(cmp(x,y))
{
 swap(x,y);
 cout<<'-'; 
 }

高精度减法过程:(x大于y才行)
lz=max(lx,ly);
 for(int i = 0;i<lz；i++)
 z[i]+=x[i]-y[i];
 if(z[i]<0)
{
 z[i+1]-=1;//借位
 z[i]+=10;
 }
while(lz>1&&z[lz-1]==0)lz--;//处理前导0

高精度乘法:(c = a*b)(也要逆序存储)
例题:洛谷  P1303 A*B Problem
lc = la+lb
//无进位相乘
for(int i =0;i<la,i++)
｛
 for(int j = 0,j<lb,j++)
  {
  c[i+j] = a[i]*b[j];
  } 
 ｝
//处理进位
for(int i = 0;i<lc,i++)
{
 c[i+1]+=c[i]/10;
 c[i]%=10;
 }
//处理前导0
while(lc>1&&c[lc-1]==0)lc--;

（高精度除低精度）
（数组也是逆着存的，即个位在a[0]）
高精度除法(这个模板是正数的，并且数组不用逆序存储)(c=a/b)(0<b<10的9次方)
（如果要解决负数的，就先判断是不是就一个负数，是就打印个-,之后转换为此做）
 
long long t = 0;//标记每次除完之后的余数
for(int i = la-1;i>=0;i--)
{
//计算当前的被除数
 t = t*10+a[i];
 c[i]=t/b;
 t%=b; 
 }
//处理前导0
while(lc>1&&c[lc-1]==0)lc--;

2.枚举和二进制枚举

枚举其实就是暴力求解

使用时一般都会超时，此时要先根据题目的数据范围来判断暴力枚举能不能通过

不能的话就要使用后面的各种算法去优化(比如二分这些)，还有就是寻找题目的各种性质去简化题目(eg:洛谷 P10449 费解的开关)

二进制枚举:
用一个数的二进制表示中的0/1表示两种状态，从而达到枚举各种情况
例题:力扣 子集
而且，把一个数的二进制存在数组中时，一般用反着存储会让过程变得简单

常用于的题型:
抽象图都是矩阵，改变矩阵的值，产生效果达到要求，问有几种途径
eg: 洛谷 Even Parity

3.前缀和（一维和二维）

在使用前缀和数组时，下标最好从1开始

核心思想就是预处理(用空间代替时间)，避免多次重复运算

一维前缀和:
例题:牛客网 【模板】前缀和
其实就是把前面的和加在一起

二维前缀和：
例题:牛客网 【模板】⼆维前缀和
用二维数组解决
前缀和矩阵一般为
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];

4.差分(一维和二维)

核心思想也是预处理，也是用空间替换时间

其实，前缀和与差分是一对互逆的运算

一维差分:
例题:牛客网 【模板】差分
     洛谷    P1496 ⽕烧⾚壁
 步骤:
1.预处理出来差分数组
f[i]表示当前元素和前一个元素的差值
      f[i]+=a[i];
      f[i+1]-=a[i];

2.利用差分数组解决m次修改操作
修改操作是：原数组[L,R]区间全部加k这个操作
相当于在差分数组中，f[L]+=k;f[R+1]-=k;

3.还原原始的数组
直接对差分数组做前缀和运算即可
f[i]=f[i-1]+f[i];

注意事项：
差分数组使用的时候，所有的操作必须全部进行完毕后，才能还原出操作之后的数组


如果操作和查询穿插在一起的话，不用差分数组，不然时间复杂度很高
eg:每操作若干次，就查询一个操作之后的结果，然回还会继续操作，继续查询
这种问题要用线段树

二维差分：
例题:牛客网 【模板】⼆维差分

利用差分矩阵解决问题
作用：快速处理"将二维数组中，某一个子矩阵加上一个元素的"的操作
这个子矩阵的左上是[x1][y1]，右上是[x2][y2]
与一维差分很不同的地方：
在于利用差分数组来解决m次修改
f[x1][y1]+=k;
f[x1][y2+1]-=k;
f[x2+1][y1]-=k;
f[x2+1][y2+1]+=k;
这里的前缀和的用法也是要注意的！(用的前面的二维前缀和)

5.双指针(也叫尺取法或滑动窗口)

两个指针不回退（回退没啥用）时，才能用滑动窗口法

滑动窗口的时间复杂度是O(n平方)

是先分析暴力解法(发现第一行那个)，然后可以用滑动窗口法

滑动窗口步骤:
例题:洛谷  唯⼀的雪花 Unique Snowflakes
1.初始化:left right 哈希表(不一定每题都用的哈希表)
2.进窗口:right位置元素记录到统计次数的哈希表中
3.判断:当哈希表中right位置的值超过1次之后，窗口内子串不合法
4.出窗口:让left所指位置的元素在哈希表中的次数减1
5.更新结果:判断结束之后，窗口合法，此时更新窗口的大小
(在其他题时，这个更新结果不一定为这5步中的最后一步)

6.二分算法

如果逐个遍历会超时时，常用此

使用条件:要研究的问题具有二段性才行

二段性:按某种要求可以分为两部分(比如大于18岁和不大于18岁)

二分算法的时间复杂度是O(logN)

这里的模板就只用记两点:
1.while(l<r)
2.if/else成立所要执行的语句中出现-1的话(这个好判断)，前面的mid就要用有+1那个
3.如果想要最后的＞a，则if里面就填(f[mid]>a)

如果是有序数组中查找的话，直接用STL的lower_bound和upper_bound
这个的时间复杂度O(logN)
反之则要自己模拟实现

模拟实现的细节问题：
a.while循环里面的判断如何写
b.求中点的方式选哪一种
c.二分结束之后，相遇点的情况
需要判断一下，循环结束之后，是否是我们想要的结果

二分答案：
其实跟二分查找很类似，只不过把对象改成了答案
应用场景:求最大值最小和最小值最大问题
例题:洛谷  P1873 [COCI 2011/2012 #5] EKO / 砍树

7.贪心

鼠目寸光，也就是想用局部最优找出全局最优

步骤:
1.把解决问题的过程分成若干步
2.解决每一步时，都选择"当前看起来最优的"解法
3."希望"得到全局的最优解
在竞赛时，如果根据贪心策略想出来的若干个边界情况都能过的话，就大概率没问题，不去证明了

8.倍增思想

它能够使线性的处理转化为对数级的处理，优化时间复杂度

例题:（一般只用于这俩个）
1.洛谷  P1226 【模板】快速幂
  LL qpow(LL a,LL b,LL p)//a的b次方对p取模
 {
 LL ret = 1;
 while(b)
{
 if(b&1)ret = ret*a%p;
 a = a*a%p;
 b>>=1; 
}
 return ret;//这个;易忘
  }
2.洛谷  P10446 64位整数乘法
//a乘b对p取模
LL qmul(LL a,LL b,LL p)
{
 LL sum = 0;
while(b)
  {
 if(b&1) sum=(sum+a)%p;
 a = (a+a)%p;//倍增
 b>>=1;
   }
 return sum;
 }

9.离散化

应用场景:当题目中数据的范围很大，但是数据的总量不是很大，就可以用离散化的思想先预处理一下所有的数据

离散化模板:
排序+使用哈希表去重并且记录离散化之后的值
(有时还需要再加一个统计每个位置出现几次的数组去记录每个位置出现了几次)
离散化常要对模板进行修改
例题：洛谷  P1496 ⽕烧⾚壁

用到离散化时容易出现问题的地方(区分同种和异种)
同种被覆盖的范围的例题:洛谷  P1496 ⽕烧⾚壁

异种被覆盖的范围的例题:洛谷  P3740 [HAOI2014] 贴海报
要在离散化区间[x,y]时，不仅考虑x,y这俩个值，还要把[x+1,y+1]也考虑进去。
可以让单个区间内部和区间与区间之间都出现空隙

10.递归

应用场景：搞类似二叉树和东西和有重复子问题并要dfs时常用
如果会多次重复已知计算的话，建议用递推，而不是递归

注意事项:
1.递归的出口一般写在开头的
2.尾和头处理的对就一般没问题
3.用的全局变量和局部变量的值是多久的要注意(这俩个不同)
4.递归里面的输出是从底到头搞的
5.一定要设法转化为重复子问题(利用传参的增多来实现通用化)

11.分治

就是把一个问题分为多个子问题解决

一般分为左－右－中间

应用场景:
1.解决逆序对
例题：洛谷  P1908 逆序对

‍12.其他

按照方向走的时候:
可以int d[x]={1,0,-1,0}
   int d[y]={0,1,0,-1}这样来表示二维上的东西可以上下左右走一格这样走
eg:洛谷的蛇形方阵

如果想要数从0开始变成从1开始的话:
可以在cin>>x之后就立马x++

eg:如果a和b的和固定，那就只用记录a的值 b的值到时候推就行了
这样可以节省存储空间

求中点用
mid = left+(right - left)/2
和 mid = left+(right - left+1)/2，避免溢出

做题时，常需要观察的性质有：
1.是不是改变顺序不影响结果
例题:洛谷  A-B 数对

取模运算技巧：
1.当计算过程中，只有"加法"和"乘法"时，想对结果取模的话，取模可以放在任意的位置
但是最后一定要有个取模
eg:(a*b*c*d)%p
和 (a%p*b*c%p*d)%p的结果一样
这个在防止超出范围时很好用
2.当计算过程中，存在"减法"时，取模结果可能是负数的，此时如果需要补正，就需要"模加模"
的技巧来补正--负的模给搞成正的那一个模
eg:写为((a-b)%p+p)%p
3.如果当计算过程中，存在"除法"时，取模是会造成结果错误的
需要用求逆元的方法

解决顶出元素且"不插入"新元素的问题:
int cnt[N];
//用于标记第i行还有多少个老元素没被顶出
让a[i][cnt[i]]每次都是第i行的最后一个元素
//顶出元素之后要i--,下标为0的不存东西

13.例题链接传送

洛谷的 [P1601 A+B Problem（⾼精）]
洛谷P2142 ⾼精度减法
洛谷 P1303 A*B Problem
洛谷 P1480 A/B Problem
力扣 子集
[牛客网 【模板】前缀和]
牛客网 【模板】⼆维前缀和
牛客网 【模板】差分
[洛谷 P1496 ⽕烧⾚壁]
牛客网 【模板】⼆维差分
洛谷 唯⼀的雪花 Unique Snowflakes
洛谷 P1873 [COCI 2011/2012 #5] EKO / 砍树
洛谷 P1226 【模板】快速幂
洛谷 P10446 64位整数乘法
洛谷 P3740 [HAOI2014] 贴海报
洛谷 P1908 逆序对