差分约束系统 1.应用 用图论的方法求解一个每个式子只有两个元的不等式组。 # 2.求法 之所以差分约束系统可以通过图论的最短路来解,是因为xj-xi<=bk,会发现它类似最短路中的三角不等式d[v]<=d[u]+w[u,v],即d[v]-d[u]<=w[u,v]。而求取最值的过程类似于最短路算法中的松弛过程。 那么此时问题就已经转化为一个完全的图论问题了,该图论问题的解即为原问题的解,该图论 2018-07-30 #OI
最小生成树 1.定义 在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即)且为无循环图,使得 的 w(T) 最小,则此 T 为 G 的最小生成树。 用处例如:要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此 2018-07-30 #OI
欧拉路径与欧拉回路 1.定义 欧拉路径:指从某一点出发,走过所有的边一次到达终点。 欧拉回路:是一种特殊的欧拉路径,其起点和终点重合。 # 2.判断有无 ## 第一步:检查图的连通性 方法有:dfs,bfs,并查集 推荐使用dfs,染色法,从每个点出发dfs,记联通块个数 注意,有向图当作无向图来跑。 一个trick:使用vector存无向图时,把边从0开始编号,互为相反边的挨着存,使用时找相反边用原边xor1即可。 2018-07-30 #OI
欧拉筛 线性筛,复杂度为O(n)。与埃氏筛相比,不会对已经被标记过的合数再进行重复标记,故效率更高。欧拉筛将合数分解为 (最小质因数 * 一个合数) 的形式,通过最小质因数来判断当前合数是否已经被标记过。 12345678910111213141516171819const int maxn = 101; // 表长int prime[maxn], pNum = 0; // prime记录素数, 2018-07-30 #OI #数论
基本公式 a|b b|c => a|c a|b a|c => a|(bx+cy) a|b => am|bm a|n b|n gcd(a,b)=1 => ab|n 同余定理 2018-07-30 #OI #数论
逆序对 1.求法 法一 归并排序。 归并排序用到了二分的思想,在排序过程中如果a[ i ]<=a[ j ]就不会产生逆序对,如果a[ i ]>a[ j ]就会产生mid-i+1个逆序对,因为做归排的时候l~mid和mid+1~r都是已经排好序的所以如果a[ i ]>a[ j ]那么a[ i+1 ]~a[ mid ]也就都大于a[ j ] ## 法二 树状数组。 首先我们只关心两个数之间的 2018-07-30 #OI