Blog
I use blog to record something.
数据结构
单调栈 单调栈除了满足普通栈的性质外，还满足： • 满足从栈顶到栈底的元素具有严格的单调性 • 假设我们维护的是一个单调递减的栈： • 若进栈的元素为x，栈顶元素为S[l] • 那么当x>=S[l]时弹出栈顶元素，直到x<...
Prime算法O(NM)
贪心的思想 流程： 1.设定起始点，放入A集合，将起始点连接的边放入可选的边的集合中去。 2.循环n-1次， 1.找出可选的边集合中另一个端点在b集合中且边权最小的一条，将它加入最小生成树 堆优化O(n log m) 把边按边...
待搞懂P1140
// // Created by dhy on 18-8-5. // # include <iostream> # include <cstring> # include <algorithm> u...
搜索ex
剪枝 避免访问那些已经不可能成功的后继状态 最优性剪枝 若当前价值加估价已经大于目前最优解，则剪掉，估价越高效果越好 引入随机 解空间非常大的时候，可以引入随机来减少解空间 预处理 预处理一些数据，方便之后剪枝dfs与bfs结合 折半...