未整理算法的总结

标签：blog   结合   线性   第k大   静态   获得   get   证明   logs   

之前一直都是认真更博的，但是为了赶时间出板子，粘贴了很多的别人的文字和代码

十分的懊悔

但是，还是剩下了一些没有学的东西，我是实在不想再去找题粘代码了

所以在这里进行一个简单的总结，方便回忆和查阅相关的资料

贪心法：

排序不等式：

给定两个等长的乱序数列，对应位做乘积，问怎样才能获得最大乘积累加和

这是一道算法导论上的题，我记得当时通过取对什么的奇葩操作证明出来了，贪心的方法就是两个数列都从小到大排序就好了

拟阵上的最大独立集问题：

算法导论重点讲的一个东西，有点儿类似于最小生成树的贪心思想（Kruskal）,其实最小生成树的贪心思想就是这个

首先证明是拟阵，然后求最大独立集就可以了，求的算法和Kruskal算法很像，在刘汝佳的黑书上有涉及，在算法导论上也有详细的说明

汽车加油问题：

同样是算法导论上的一道题

一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少

把距离相加，判断是否大于n，如果大于n,计数一次

过河问题（加强版）：

经典的过河问题是只有一盏灯，只有一艘船什么的，这个问题的拓展是潜水问题，是过河问题的加强版，具体解法感觉要根据数据来定，需要算一下

乘船问题：

这是刘汝佳书上的一个经典贪心题，当时偷懒没有写这个代码

计算几何：

仿射变换与矩阵：

刘汝佳在训练指南的拓展部分描述的一部分知识点

三维计算几何：

这部分内容考察的可能没有二维计算几何深入，直接看知识点就好了

扫描线：

和线段树结合之后可以求边长啊面积啊什么的，好像用SET也可以巧妙求面积

字符串哈希：

字符串哈希可以解决LCP问题，它独特的哈希方式可以用来迅速判断两个字符串是否相等

这里贴一篇博文，很有意义：

https://www.cnblogs.com/Slager-Z/p/7807011.html

后缀数组：

这应该是一个比较难的知识点，俗称SA算法，它好像可以用SAM算法替换掉，具体应用没有总结过，没怎么深入研究过字符串

拓展KMP：

设字符串T，长度为n，字符串S，长度为m。在线性时间内求出T的每一个后缀所对应S的最长前缀

还好Kuangbin有板子，而且会了SAM什么都不怕了吧（orz我不会SAM）

后缀树：

这个东西貌似完全可以用后缀数组替换掉，而且很不实用

图论：

EK算法：

最大流的入门级算法，有必要弄懂其原理

ZKW费用流：

不容易被卡掉的费用流，有必要弄懂其原理

数据结构：

分段哈希表：

论文中才有的东西完全没有任何生存的价值呀

跳表：

据说可以替代任何的平衡树，还可以O（1）求前驱和后继

还可以方便地实现简单的数据库

然而并不实用

归并树和划分树：

难兄难弟，静态区间第K大，基于归并排序的树和快速排序的树？

RMQ标准算法与约束RMQ：

这个东西我们可以联想到ST表，这个东西可以O（n）预处理是不是很吊

先说这么多了，我该想想怎么整理板子了

未整理算法的总结

标签：blog   结合   线性   第k大   静态   获得   get   证明   logs   

原文地址：https://www.cnblogs.com/aininot260/p/9643913.html