- 博客(373)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 【每周题解】道路与航线
道路与航线的算法思想是把双向边添加到图中，那么会形成若干个连通块，可以把每个连通块看作一个点，再把单向边添加到图中，会得到一张有向无环图。在有向无环图中，无论边权正负，都可以按照拓扑序进行遍历，在线性时间复杂度内求出单源最短路
2024-04-19 11:24:55
701
原创 每周一算法：负环判断
每周一算法：判断负环可以使用Bellman–Ford算法，时间复杂度为O(nm)；也可是使用SPFA，它比Bellman-ford要快上许多倍，最好情况下的复杂度是O(km)，这里的k是一个小于等于2的常数，最坏情况也是O(nm)。
2024-04-18 15:34:09
483
原创 每周一算法：旋转游戏
每一步操作有A~H一共8种选择，状态空间随着深度增加呈指数级别增长，但是答案序列不会太长，为了避免搜索超时，可以使用迭代加深A*（IDA*）实现。在每个状态下，如果中间8个格子里出现次数最多的是x，一共出现了m次，那么其余数字全变成x，至少需要8-m次操作。可以用这个作为预估步数。
2024-03-22 14:49:59
688
原创 每周一算法：迭代加深A*
把估价函数与迭代加深的DFS结合就是迭代加深A*（IDA*），基本思想是以迭代加深DFS的搜索框架为基础，把原来简单的深度限制加强为：若当前深度+未来估计步数>深度限制，则立即从当前分支回溯。
2024-03-22 10:10:17
663
原创 每周一算法：双向深搜
双向搜索——从初态和状态出发各搜索一半，产生的两棵深度减半的搜索树，在中间交汇、组成最终答案。避免了层数过深时，分支数量的大规模增长。
2024-03-15 10:54:03
1059
原创 每周一算法：迭代加深搜索
当搜索树规模随着层次的深入增长很快，并且题目能够确保答案在一个较浅层的节点时，就可使采用迭代加深的深度优先搜索算法来解决问题。其基本思想是从小到大限制搜索的深度，如果在当前深度限制下搜索不到答案，就把深度限制增加，重新进行一次搜索。
2024-03-14 23:32:31
826
原创 每周一算法：第K短路
A*算法解决第K短路问题，对每个节点，使用节点到终点的最短路径长度作为预估代价，当终点第K次出队时，就得到了第K短路的长度。
2024-03-08 13:19:08
906
原创 每周一算法：A*（A Star）算法
A*（A Star）算法是一种很常用的路径查找和图形遍历算法，它有较好的性能和准确度。A*算法与BFS类似，不同之处在于A*算法使用优先队列，选取优先级最高的状态作为下一个待扩展的状态。
2024-03-07 23:20:07
1108
原创 NOIP2002提高组T2：字符串变换
朴素版BFS虽然可以满足题目要求，但是要搜索的状态空间大、时间复杂度太高，可以使用双向广搜进行优化。双向广搜，是指从起点和终点同时开始进行BFS，双向奔赴直到找到共同的目标为止。
2024-03-06 10:18:53
922
原创 每周一算法：双向广搜
双向广搜，是指从起点和终点同时开始进行BFS，双向奔赴直到找到共同的目标为止。使用双向广搜可以大大减少了要搜索的状态空间，剪枝效果明显。使用双向广搜时要注意：* 在双向广搜时，优先选择队列中状态数量较少的方向来扩展，可以优化搜索效率* 在扩展时，需要将一层的所有节点扩展完，不能只扩展一个点。
2024-03-01 15:33:55
979
原创 每周一算法：双端队列广搜
对于只包含边权0和1的最短路问题，可以使用双端队列广搜求解。与普通的BFS不同的是：如果扩展到的新节点边权为0时，需要把新节点插入队列的头部。
2024-03-01 12:46:41
1016
原创 NOIP2011提高组day1 - T3：Mayan游戏（玛雅游戏）
NOIP2011提高组day1 - T3：Mayan游戏（玛雅游戏），DFS深度优先搜索，可行性剪枝,优化性剪枝。
2024-01-19 17:22:06
864
原创 NOIP2014提高组day2-T2：寻找道路
NOIP2014提高组day2-T2：寻找道路，路径上的所有点的出边所指向的点都直接或间接与终点连通，求该路径的最小长度。
2024-01-10 18:49:20
960
原创 每周一算法：倍增法求最近公共祖先（LCA）
最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。本文介绍了如何通过倍增法球LCA。
2024-01-05 14:04:06
1012
原创 每周一算法：倍增法求区间最大最小值（RMQ）
RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。本文介绍如何使用倍增思想解决 RMQ 问题。
2024-01-05 10:38:46
1044
1
原创 每周一算法：倍增法查找位置
倍增法（Binary Lifting），顾名思义，就是利用“**以翻倍的速度增长**”的思想来解决问题的一类算法。本文介绍如何使用倍增法在有序的序列中查找满足条件的位置。
2024-01-02 11:50:41
968
原创 每周一算法：最大连续子序列
每周一算法：最大连续子序列。给出一个长度为n的序列，选出其中连续且非空的一段使得这段和最大，并求解该序列的开始位置和结束位置。
2023-12-22 14:53:09
879
原创 CSP-S2019提高组day1-T2：括号树
CSP-S2019提高组day1-T2：括号树。树形动态规划，括号匹配方案数的算法思想、时间复杂度和代码实现。
2023-12-20 10:55:29
925
scratch3.0文件打包工具-htmlifier
2020-04-02
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人