一.前缀和与差分
(一维)
假设有一个数列:A1,A2,A3,...,AnA_1,A_2,A_3,...,A_nA1 ,A2 ,A3 ,...,An
那么它对应的前缀和数列就是:
A1,A1+A2,A1+A2+A3,...,(A1+A2+A3+...+An)A_1,A_1+A_2,A_1+A_2+A_3,...,(A_1+A_2+A_3+...+A_n)A1 ,A1 +A2 ,A1 +A2 +A3 ,...,(A1 +A2 +A3 +...+An )
与其相反的则是差分:
假设有一个数列:A1,A2,A3,...,AnA_1,A_2,A_3,...,A_nA1 ,A2 ,A3 ,...,An
那么它对应的差分数列就是:
A1,A2−A1,A3−A2,...,An−An−1A_1,A_2-A_1,A_3-A_2,...,A_n-A_{n-1}A1 ,A2 −A1 ,A3 −A2 ,...,An −An−1
假设这个差分数列的每一项是BiB_iBi ,则满足:
B1+B2+B3+...+Bi=Ai(i≠1)B_1+B_2+B_3+...+B_i=A_i(i\ne1)B1 +B2 +B3 +...+Bi =Ai (i=1)
前缀和数列的差分数列就是原数列.
差分数列的前缀和数列就是原数列.
(高维)
二.快速幂
参考Microsoft Bing的回答.
快速幂是高效的指数级运算方法.
比如计算a^b,快速幂可将时间复杂度为O(b)O(b)O(b)的计算,降低至O(logb)O(logb)O(logb)
具体方法可以看一个示例:2132^{13}213
将13转化为1101(二进制);而后计算220∗222∗2232^{2^0}*2^{2^{2}}*2^{2^{3}}220∗222∗223
三.最短路
//其实我本来想做动态规划的.
最短路分为"单源"和"多源".
单源指的是只有一个起点,多源指的是有多个起点.
然后求它们到某个顶点的最短路.
我学过了Dijkstra,Floyd,SPFA.
这三个算法各有特点.
Dij是由贪心思想作为基础,所以无法处理负环.不过有稳定性.
Floyd的代码是简单的,但效率不高.
SPFA可以处理负环,但代码容易与Dij搞混,且容易出问题.
从Dijkstra开始看吧.
它是单源最短路算法.
这里因为不是教程,只是自己的知识点总结,所以不会有过多解释.
Dij,前文提过,使用了贪心的思路.
主要体现在每次会选择距离起点最近的一个顶点进行松弛.
松弛:最短路算法的核心.即用某个顶点作为中转站,用这个顶点来更新与其相邻的其他顶点的最短路数值.
Dij模板:
然后是一个跟最短路有关系的小技巧:反向建边.
题目:邮递员送信 差不多是这样:
所以只要反向建边,原来需要运行n+1次的Dij,就只需要运行2次了(都是算从点1到其他节点的距离,只不过一次正边一次反边.
然后是SPFA。
SPFA是Bellman-Ford的优化。
Bellma-Ford：枚举所有顶点的所有边进行松弛，无视先后顺序，每次枚举时，disdisdis数组发生了变化，就继续枚举，直到不再发生变化。
而它的优化是 disdisdis 发生了变化的点的边继续松弛，没有发生变化的就置之不理。
而每条边最多会进行n次松弛。
所以SPFA的最坏时间复杂度是 O(nm)O(nm)O(nm) 。
如果说一条边进行了超过n次的松弛，那就证明图中存在负环。
负环即一个环中的边的边权相加是负数，负环之上不存在最短路.
题目：小码君的太空基地
四.动态规划
本来打算在这里写的，但是由于这个板块太大了，会直接写一整个文章来介绍DP。
