首页 > 编程语言 >算法总结

算法总结

时间:2023-11-16 20:46:53浏览次数:39  
标签:总结 匹配 适用范围 括号 算法 最优 border 节点

贪心算法

  • 解决问题:最优化问题;

  • 优点:是解决最优化问题的最优策略,时间复杂度低;

  • 缺点:要满足局部最优解可以推出全局最优解,这意味着在考场上想出一个贪心策略需要通过举例以及证明。

  • 常见思考方式:

    • 如果是决定谁先做谁后做的,类比排队问题,邻项交换;如果先后有限制关系,比如谁先做谁后做,那么通常套路还是找出最优的,尽可能合并,或者直接将限制的直接干掉。

    • 对于树上问题,通常考虑从下到上进行合并。

    • 区间问题,首先将区间左/右端点进行排序,然后考虑怎么处理。

    • 更为一般的问题,如果几种策略的贡献相等,就考虑对于后面的影响。

    • 对于每个必选的,直接考虑每个点如何加入。

    • 实在不会,考虑反悔贪心。

搜索

深搜优化

  • 剪枝

    • 可行性剪枝;

    • 最优性剪枝;

    • 优化搜索顺序;

    • 减少冗余状态;

  • 迭代加深搜索

    • 适用范围:不知道明确的搜索边界,或者做搜索树的简单优化;

    • 可以达到广搜第一次搜到就是最优解的效果;

  • \(IDA^*\) 算法

    • 注意:估价函数 \(f()\) 一定要 \(\le\) 真实值,约接近效率越高。

    • 适用范围:比较容易得出估价函数的题目。

广度优先搜索

  • \(bfs\)

    • 适用范围:边权相等,最优化问题,第一次搜到就是最优;

    • 优点:在时间常数上,广搜最优,所以对于信息容易放进队列的题目,宜用广搜;

    • 缺点:由于必须将信息存进队列,因此若信息过大,则无法放进队列,这时只能深搜。

二分

  • 适用范围:具有单调性的最优性问题,求最大值最小/最小值最大,排名,变化后的数字。

  • 注意:

    • 合理选取二分写法,否则造成死循环;

    • 如果 \(l,r\) 特别大,考虑加在一起会不会爆 \(int\)。

  • 优点:可以将最优性问题转化为可行性问题,然后利用条件进行一系列简化。

  • 思考方向:

    • 利用二分出来的值进行分段 ;

    • 利用 \(mid\) 将已知条件进行重新赋值,比如赋值 \(0,1,-1\) 这种较具代表性的数。

线性表

  • 概念:先进后出的数据结构;

  • 适用范围:

    • 表达式求值。

      • 两个栈,一个数字栈,一个符号栈,遇到数字就往数字栈里面塞,遇到符号,如果这个符号比栈顶符号的优先级大,直接将数字栈弹出了两个算出结果再塞回去,这个符号就不放回去了。否则将符号塞进去,若是遇到左括号,直接塞,遇到右括号,将数字栈和符号栈轮流弹出,直到遇到左括号为止。在将结果塞回去。
    • 括号匹配

      • 左括号就塞进栈,右括号就将顶上的括号弹出,然后标记那两对是匹配的,一般还会结合 \(dp\) 进行出题,这时需要利用匹配结果进行转移。

并查集

  • 适用范围:

    • 维护图的连通性;

    • 维护某种关系;

      • 如果是关系较多,考虑扩展域并查集。
    • 实现快速找到第一个没有填数字的位置。

      • 对于某类区间操作的题目,考虑时间倒流加并查集操作。

前缀和与差分

倍增

  • 适用范围:

    • 对于一步一步跳并统计贡献的暴力,尝试用倍增对其优化。

图论

拓扑排序

  • 适用范围:在 \(DAG\) 上 \(dp\) 或者计算;

欧拉路径

  • 使用范围:图论建模后,不重复且全部走完边的方案。

  • 概念:从一个点出发,不重复地走边,将所有边走完,最后回到一个点;

  • 有向图:

    • 欧拉路径:要么全部节点入度等于出度,要么有一个节点出度等于入度 \(+1\)(起点),一个节点的入度等于出度 \(+1\)(终点),其他节点的入读等于出度。

    • 欧拉回路:全部节点入度等于出度。

    • 注意:当前弧优化。

  • 无向图:

    • 类似有向图,此处只需考虑节点度数的奇偶性即可。

    • 注意:无向图只能写邻接表存图,否则要用 map 对边进行标记,效率很低。

  • 思考方向

    • 这种题通常会有不能重复,且首尾有些关系的条件,这时要将关键信息放在边,其他信息放在点。

    • 可以利用欧拉路径将若干简单环构成的图,进行分解,得到这些环。

最短路

最小生成树

  • 概念:在图中边权和最小的一棵树。

  • 适用范围:

    • 找出一颗最小生成树,只是贡献的计算有点奇怪;

    • 希望边权尽可能的大/小,可以在图上找一棵最小/大生成树;

    • 利用 \(kruskal\) 的性质出题,只需掌握合并的规律即可。

联通性问题

  • 强连通分量

    • 适用范围:有向图。

    • 常见功能:

      • 将一个有向图转化成一个 \(DAG\);

      • 能缩点的题目,通常对于环的处理都很简单,唯一困难就是在 \(DAG\) 的递推上。

    • 易错点

      • 要记得写 is_stack 数组,在满足 dfn[x]!=0 时,先判断 is_stack[x] 再更新 low[nd]

      • 如果不是先 tarjan 的,要用 dfn[x] 更新 low[nd]

  • 边双连通分量

    • 适用范围:无向图。

    • 常用功能:

      • 将一个无向图转化为一棵树;

      • 缩边的题目通常上在题目描述上会特别描述,因为变成树以后,所有边都是桥,也就是必须经过的边。

树论

树的直径

  • 概念:树上一条最长链。

  • 求解:

    • 两边 dfs 可以求出树的直径。

    • 若要求出树的直径上的点,设置上一个节点然后往回跳即可。

  • 性质

    • 与一个点距离最远的点,一定是树的直径端点;

    • 若树边权为正,则所有树的直径必定有点重合,即没有不相交的两个树的直径。

树的重心

  • 概念:使得以该点为根的最大子树最小的点。

  • 性质:

    • 树中所有点到重心的距离和是最小的。

    • 重心的最大子树大小不超过整棵树大小一半。

最近公共祖先

  • 求法:倍增,树剖。

  • 基本上树上问题统计贡献或是判定问题都可以在 \(LCA\) 处解决。

树链剖分

  • 概念:根据轻重儿子将树剖分成一条条轻重链。

  • 维护各种树上信息。

字符串

border

  • 概念:最长相等前后缀。

  • 性质:

    • 字符串 \(s\) 的 \(border\) 的 \(border\) 还是自己的 \(border\)。

    • 在原来字符串后添加一个字符,字符串的 \(border\) 长度至多加 \(1\).

    • 周期:除去 \(border\) 剩下的就是周期。

  • 常考题目

    • 利用 \(border\) 性质进行出题,一般涉及周期,相同字母覆盖,以及一些失配树的相关问题。

    • 利用 \(border\) 的性质实现 \(dp\) 转移。

kmp

  • 性质:利用 \(border\) 计算出失配数组,便可以在 \(\rm O(n)\) 时间内完成匹配。

哈希

  • 使用范围:要对子串进行一定程度的匹配,如果单纯是对整个字符串进行匹配,直接 map 即可。

  • 注意:在考场上为了保险,最好写双哈希

字典树

  • 适用范围:

    • 字符串字典树:进行前缀信息匹配,以及相关计算;

    • 01字典树:进行 \(xor\) 相关计算,具有求出排名为第 \(k\) 大的异或值。

  • 常见技巧:

    • 在字典树上标记通常有两种,一种是直接在最后标记,这样计算完全匹配;一种是在过程中的节点标记,这样可以计算匹配前缀。
  • 注意:字典树的空间小号算是比较大的,清空时记得清空 \(tot\)。

标签:总结,匹配,适用范围,括号,算法,最优,border,节点
From: https://www.cnblogs.com/zhangyuzhe/p/17837219.html

相关文章

  • 学期2023-2024-1 20231401 《计算机基础与程序设计》第八周学习总结
    学期2023-2024-120231401《计算机基础与程序设计》第八周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第八周作业这个作业的目标《计算机科学概论》第9章《C语言程序设计》第7章并......
  • 算法~totp用作签名防止url被复用
    之前写过关于totp的文章,对它的基础有不清楚的同学,可以先看我的这篇文章《TOTP基础一》《TOTP基础二》想到的问题因为totp是把时间分成了一个一个小的时间窗口,当生成totp的服务器和校验totp的服务器不在一起时间窗口,就会出现验证失败的问题,这是不可避免的,时间戳是一个long类型的......
  • 「总结」同或卷积
    前置知识:FWT的另一种理解FWT的另一种理解,文中使用的系数矩阵\(F\)似乎不太标准,本文中认为\(\mathscr{F}(\bma)=F\times\bma\)。摘要:FWT使用的线性变换的系数矩阵\(F\)需要满足\(F(i,x\oplusy)=F(i,x)\timesF(i,y)\)。同或卷积因为同或运算在每一位上是独立的,所以......
  • 树算法题
    目录1、计算二叉树中所有结点个数2、计算二叉树中所有叶子节点的个数3、计算二叉树中所有双分支的节点个数4、计算二叉树的深度5、找出二叉树中最大值的点6、判断两个二叉树是否相似(指都为空或者都只有一一个根节点,或者左右子树都相似)7、把二叉树所有节点左右子树交换8......
  • NOIP2023 考前9场 总结
    RoundT1T2T3T4估分实分R11001001070280280R2100101000210210R31001002540265265R44010000180140R560100500250210R6100500130105R71001001000300300R81001005030295280R90957502751......
  • 【C++】【图像处理】形态学处理(腐蚀、膨胀)算法解析(以.raw格式的图像为基础进行图像处
    1voiderosion(BYTE*image,intw,inth,BYTE*outImg)2{3intrept;4//腐蚀5memcpy(outImg,image,sizeof(BYTE)*w*h);//将读取的图像赋值给outImg,方便进行腐蚀操作67inti,j,m,n;8BYTEflag;9for(rept=0;rept......
  • 11.16每日总结
    今天准备好明天的测试了,但是由于上周的作业太复杂了,于是又推迟了一周,但是今天上课我们进行了讨论。目前的状况是我们的原型已经搭建起来了要做的就是要把相应流程图和用例图搞明白流程还是不太熟悉,因为中间涉及到很多环节。 ......
  • 你真的了解字符截取函数substr吗?php字符截取函数substr参数的6种情况。分别是:正正 负
    <?php$str='123456789abcd';echo'<br/>';echo'原字符:'.$str;echo'<br/>';//情况1正正++从指定位置开始截取3个echo'1正正substr($str,0,3):'.substr($str,0,3);//123echo'<br/>';//情况2......
  • 随机产生n个数的排列(Fisher-Yates洗牌算法)
    #include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inta[N];//Fisher-Yates洗牌算法voidshuffle(intn){srand(time(NULL));for(inti=n;i>1;i--){intj=rand()%i+1;swap(a[i],a[j]);}......
  • 软件设计模式学习每日总结-第四天
    第四天建造者模式:将一个复杂对象的构建和他的表 建造者模式服务于多个成员的产品,无需用户关注建造的细节。 ......