洛谷：P3366 ，和Dijkstra堆优化模板差不多 题目描述 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz 输入输出格式 输入格式： 第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000） 接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi 输出格式： 输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz 输入输出样例 输入样例#1： 4 5 1 2 2 1 3 2 1 4 …
简介 ST表用于区间RMQ问题，它可以做到O(nlogn)预处理，O(1)查询最值。相比线段树，更加有利于静态数据的最值问题。主要是利用倍增的思想。 洛谷：P3865 模板 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <iostream> #include <vector>…
笔记 1、出度：以顶点v为起点的弧的数目 入度：顶点v为终点的弧的数目 2、如果在有向图G中，有一条<u，v>有向道路，则v称为u可达的，或者说，从u可达v。 3、强连通图：若有向图G的任意两个顶点都互相可达，则称图 G是强连通图，如果有向图G存在两顶点u和v使得u不能到v，或者v不能到u，则称图G是强非连通图。 4、强连通分量：如果有向图G不是强连通图，他的子图G2是强连通图，点v属于G2，任意包含v的强连通子图也是G2的子图，则称G2是有向图G的极大强连通子图，也称强连通分量。 5、极大强连通子图（…
裴蜀定理 在数论中，裴蜀等式是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a,b和m，关于未知数 x和y的线性丢番图方程（称为裴蜀等式）：ax+by=m 有整数解时当且仅当m是 a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 x、y都称为裴蜀数，可用扩展欧几里得算法求得。 就是关于 x, y 的不定方程 ax + by =c 有整数解的充要条件是 gcd(a,b)∣c 。 题目见洛谷:P4549 模板 #include <cstdi…
简介 Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 无优化复杂度：O(n ^ 2) 那么有O（km）的Spfa算法我们为什么需要Dijkstra算法呢？ 因为某些毒瘤出题人会专门设计网格图来卡Spfa算法，使其变为O（m ^ 2）如下方提到的落谷题目。 洛谷：P3371（弱化版） Spfa能过 P4779（标准版）卡S…
简介 朴素的算回文串的办法一般是O（n ^ 2） 或 O（n ^ 3）的。而Manacher发明的马拉车算法能将空间复杂度和时间复杂度均优化到O（n）的线性。 具体算法过程是： 1、将字符串中加入# 如 abcde -> ##a#b#c#d#e 举个例子 一个字符串s = abbahopxpo，转换为$#a#b#b#a#h#o#p#x#p#o#（这里的字符 $ 只是为了防止越界，下面代码会有说明），如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#…
简介 Hash算法类似于给字符串进行加密的方式，方便判断重复 那字符串Hash就非常好理解了。就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值。 进制哈希是最常见（NOIP）的哈希方式 它的主要思路是选取恰当的进制，可以把字符串中的字符看成一个大数字中的每一位数字，不过比较字符串和比较大数字的复杂度并没有什么区别(高精数的比较也是O(n) 评测：洛谷P3370 模板 #include <cstdio> #include <cstdlib> #include <…
逆元 a * b = 1 (mod p) 则a,b互为逆元 费马小定理 a ^(p-1) = 1 (mod p) p 为质数 -> a * a ^(p-2) = 1 (mod p) 于是 a和a ^(p-2) 互为逆元 欧拉函数 定义：φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) p(1),p(2)…p(n)为x的所有质因数 表示 小于x的数中与x互质的数的数目 欧拉公式：a ^ φ(p) =1 (mod p) -&…
问题模型 现在有一个这样的问题：有一个数组a，，现在给你w次修改，q次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和。 这个问题很常见，首先分析下朴素做法的时间复杂度，修改是O(1)的时间复杂度，而查询的话是O(n)的复杂度，总体时间复杂度为O(qn) 可能你会想到前缀和来优化这个查询，我们也来分析下，查询的话是O(1)的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是O(n)，总体时间复杂度还是O(qn)。 可以发现，两种做法中，要么查询是O(…
