电影网站内页,wordpress图片插件使用,购物车网站源码,上百度推广 免费做网站算法基础篇
前言
算法内容还有搜索#xff0c;数据结构#xff08;进阶#xff09;#xff0c;动态规划和图论 数学那个的话大家也知道比较难#xff0c;放在最后讲 这期包含的内容可以看目录 模拟那个算法的话就是题说什么写什么#xff0c;就不再分入目录中了 注意事…算法基础篇
前言
算法内容还有搜索数据结构进阶动态规划和图论 数学那个的话大家也知道比较难放在最后讲 这期包含的内容可以看目录 模拟那个算法的话就是题说什么写什么就不再分入目录中了 注意事项 1.多组测试时一定要考虑需不需要清空数据 一般是能覆盖的话(没覆盖的部分不用就行了)不清空或者还能用就不清空 (权衡时间复杂度清空是用时间换空间) 2.int类型的无穷大可以搞为 int inf 0x3f3f3f3f 1.高精度
当数据的值特别大各种类型都存不下的时候要用高精度算法来加减乘除
步骤:
1.先用字符串读入这个数然后用数组逆序存储该数的每一位
2.利用数组模拟加减乘除运算的过程
高精度加法(c ab其字符串存在c[],a[],b[]中)例题洛谷的 [P1601 AB Problem⾼精]
la,lb是a,b的字符串长度
lc max(la,lb)
for(int i 0;ilci)
{c[i]a[i]b[i];//对应位相加c[i1]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(stringx,stringy)
{
if(x.size()!y.size()) return x.size()y.size();//比长度return xy//比字典序}if(cmp(x,y))
{swap(x,y);cout-; }高精度减法过程:(x大于y才行)
lzmax(lx,ly);for(int i 0;ilzi)z[i]x[i]-y[i];if(z[i]0)
{z[i1]-1;//借位z[i]10;}
while(lz1z[lz-1]0)lz--;//处理前导0高精度乘法:(c a*b)(也要逆序存储)
例题:洛谷 P1303 A*B Problem
lc lalb
//无进位相乘
for(int i 0;ila,i)
for(int j 0,jlb,j){c[ij] a[i]*b[j];}
//处理进位
for(int i 0;ilc,i)
{c[i1]c[i]/10;c[i]%10;}
//处理前导0
while(lc1c[lc-1]0)lc--;高精度除低精度
数组也是逆着存的即个位在a[0]
高精度除法(这个模板是正数的并且数组不用逆序存储)(ca/b)(0b10的9次方)
如果要解决负数的就先判断是不是就一个负数是就打印个-,之后转换为此做long long t 0;//标记每次除完之后的余数
for(int i la-1;i0;i--)
{
//计算当前的被除数t t*10a[i];c[i]t/b;t%b; }
//处理前导0
while(lc1c[lc-1]0)lc--;2.枚举和二进制枚举
枚举其实就是暴力求解
使用时一般都会超时此时要先根据题目的数据范围来判断暴力枚举能不能通过
不能的话就要使用后面的各种算法去优化(比如二分这些)还有就是寻找题目的各种性质去简化题目(eg:洛谷 P10449 费解的开关)
二进制枚举:
用一个数的二进制表示中的0/1表示两种状态从而达到枚举各种情况
例题:力扣 子集
而且把一个数的二进制存在数组中时一般用反着存储会让过程变得简单常用于的题型:
抽象图都是矩阵改变矩阵的值产生效果达到要求问有几种途径
eg: 洛谷 Even Parity3.前缀和一维和二维 在使用前缀和数组时下标最好从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[i1]-a[i];2.利用差分数组解决m次修改操作
修改操作是原数组[L,R]区间全部加k这个操作
相当于在差分数组中f[L]k;f[R1]-k;3.还原原始的数组
直接对差分数组做前缀和运算即可
f[i]f[i-1]f[i];注意事项
差分数组使用的时候所有的操作必须全部进行完毕后才能还原出操作之后的数组如果操作和查询穿插在一起的话不用差分数组不然时间复杂度很高
eg:每操作若干次就查询一个操作之后的结果然回还会继续操作继续查询
这种问题要用线段树二维差分
例题:牛客网 【模板】⼆维差分利用差分矩阵解决问题
作用快速处理将二维数组中某一个子矩阵加上一个元素的的操作
这个子矩阵的左上是[x1][y1]右上是[x2][y2]
与一维差分很不同的地方
在于利用差分数组来解决m次修改
f[x1][y1]k;
f[x1][y21]-k;
f[x21][y1]-k;
f[x21][y21]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(lr)
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(b1)ret ret*a%p;a a*a%p;b1;
}return ret;//这个;易忘}
2.洛谷 P10446 64位整数乘法
//a乘b对p取模
LL qmul(LL a,LL b,LL p)
{LL sum 0;
while(b){if(b1) sum(suma)%p;a (aa)%p;//倍增b1;}return sum;}9.离散化 应用场景:当题目中数据的范围很大但是数据的总量不是很大就可以用离散化的思想先预处理一下所有的数据 离散化模板:
排序使用哈希表去重并且记录离散化之后的值
(有时还需要再加一个统计每个位置出现几次的数组去记录每个位置出现了几次)
离散化常要对模板进行修改
例题洛谷 P1496 ⽕烧⾚壁用到离散化时容易出现问题的地方(区分同种和异种)
同种被覆盖的范围的例题:洛谷 P1496 ⽕烧⾚壁异种被覆盖的范围的例题:洛谷 P3740 [HAOI2014] 贴海报
要在离散化区间[x,y]时不仅考虑x,y这俩个值还要把[x1,y1]也考虑进去。
可以让单个区间内部和区间与区间之间都出现空隙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开始的话:
可以在cinx之后就立马xeg:如果a和b的和固定那就只用记录a的值 b的值到时候推就行了
这样可以节省存储空间求中点用
mid left(right - left)/2
和 mid left(right - left1)/2避免溢出做题时常需要观察的性质有
1.是不是改变顺序不影响结果
例题:洛谷 A-B 数对取模运算技巧
1.当计算过程中只有加法和乘法时想对结果取模的话取模可以放在任意的位置
但是最后一定要有个取模
eg:(a*b*c*d)%p
和 (a%p*b*c%p*d)%p的结果一样
这个在防止超出范围时很好用
2.当计算过程中存在减法时取模结果可能是负数的此时如果需要补正就需要模加模
的技巧来补正--负的模给搞成正的那一个模
eg:写为((a-b)%pp)%p
3.如果当计算过程中存在除法时取模是会造成结果错误的
需要用求逆元的方法解决顶出元素且不插入新元素的问题:
int cnt[N];
//用于标记第i行还有多少个老元素没被顶出
让a[i][cnt[i]]每次都是第i行的最后一个元素
//顶出元素之后要i--,下标为0的不存东西13.例题链接传送
洛谷的 [P1601 AB 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 逆序对
