平面图
1. 定义
1.1 平面图 & 非平面图
如果能够将无向图 GGG 画在平面上使得除顶点处外无边相交，则称 GGG 为可平面图，简称平面图。
画出的无边相交的图称作 GGG 的平面嵌入。
无平面嵌入的图称作非平面图。
2. 性质
平面图的子图都是平面图，非平面图的母图都是非平面图。
支配集、独立集、覆盖集
1. 定义
1.1 支配集
设无向简单图 G=<V,E>,V∗⊆V
G = \lt V,E \gt, V^* \subseteq V
G=<V,E>,V∗⊆V，若 ∀vi∈V−V∗,∃vj∈V∗
\forall v_i \in V - V^*, \exists v_j \in V^*
∀vi∈V−V∗,∃vj∈V∗ 使得 (vi,Vj)∈E(v_i,V_j) \in E(vi,Vj)∈E，则称 V∗V^*V∗ 为 GGG 的一个支配集，并称 vjv_jvj 支配 viv_ivi 。
设 V∗V*V∗ 是 GGG 的支配集，且 V∗V*V∗ 的任何真子集都不是支配集，则称 V∗V*V∗ 为极小支配集。
GGG 的顶点最少的支配集称作 GGG 的最小支配集。
最小支配集中的顶点个数称作 GGG 的支配数，记作 γ0(G)\gamma_0(G)γ0(G)，简记为 γ0\gamma_0γ0 。
1.2 独立集
1.2.1 点独立集
设无向简单图 G=<V,E>,V∗⊆V
G = \lt V,E \gt, V^* \s ...
排队论模型
1. 简介
我们使用六个符号表示排队模型，在符号之间用斜线隔开，记为 X/Y/Z/A/B/C 。第一个符号 X 表示顾客到达流或顾客到达间隔时间的分布；第二个符号 Y 表示服务时间的分布；第三个符号 Z 表示服务台数目；第四个符号 A 是系统容量限制；第五个符号 B 是顾客源数目；第六个符号 C 表示的是服务规则，例如先到先服务 FCFS， 后到先服务 LCFS 等。
2. Little（利特尔）公式
在排队论模型中，可以通过平均队长 LsL_sLs ，平均排队长 LqL_qLq，平均等待时间 WqW_qWq，平均逗留时间 WsW_sWs 这些基本数量指标判断系统运行的优劣。
2.1 定义
Little (利特尔)法则可用于一个稳定的、非占先式的系统中。其定义为：
在一个稳定的系统（LLL）中，长时间观测到的平均顾客人数等于长时间观测到的有效抵达率（λ\lambdaλ）乘以顾客在这个系统中平均的等待时间（WWW）；用一个代数式表示为：
L=λW\begin{array}{c}
L = \lambda W
\end{array}
L=λW
用 λ\lambdaλ 表示单位时 ...
欧拉图
1. 定义
1.1 欧拉通路 & 欧拉回路
通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的通路称作欧拉通路。
通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路。
【注】规定平凡图是欧拉图。
1.2 欧拉图 & 半欧拉图
具有欧拉回路的图称为欧拉图。
具有欧拉通路而无欧拉回路的图称作半欧拉图。
2. 性质
无向图 GGG 是欧拉图当且仅当 GGG 是连通图且没有奇度顶点。
无向图 GGG 是半欧拉图当且仅当 GGG 是连通的且恰有两个奇度顶点。
有向图 DDD 是欧拉图当且仅当 DDD 是强连通的且每个顶点的入度等于出度。
有向图 DDD 是半欧拉图当且仅当 DDD 是单连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大 1 ，另一个顶点的出度比入度大 1 ，而其余顶点的入度等于出度。
无向图 GGG 是非平凡的欧拉图当且仅当 GGG 是连通的且是若干个边不重的圈的并。
哈密顿图
1. 定义
1.1 哈密顿通路 & 哈密顿回路
经过图（无向图或有向图）中所有顶点一次且仅一次的通路称作哈密顿通路。
经过图（无向图或有向图）中所有顶点一次且仅一次的回路称作哈密顿回路。
1.2 哈密顿图 & 半哈密顿图
具有哈密顿回路的图称作哈密顿图。
具有哈密顿通路但不具有哈密顿回路的图称作半哈密顿图。
【注】规定平凡图是哈密顿图。
2. 性质
【注】p(G)p(G)p(G) 表示 GGG 的连通分支数。
设无向图 G=<V,E>
G = \lt V,E \gt
G=<V,E> 是哈密顿图，则对于任意的 V1⊂V
V_1 \subset V
V1⊂V 且 V1≠∅
V_1 \ne \varnothing
V1=∅，均有
p(G−V1)≤∣V1∣\begin{array}{c}
p(G-V_1) \leq |V_1|
\end{array}
p(G−V1)≤∣V1∣
设无向图 G=<V,E>
G = \lt V,E \gt
G=<V,E> 是半哈密顿图，则对于任意的 V1⊂V
V ...
P1169「棋盘制作」
1. 题目
题目链接：P1169「棋盘制作」 。
题目描述
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 8×88 \times 88×8 大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。
而我们的主人公小 Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小 W 决定将棋盘扩大以适应他们的新规则。
小 Q 找到了一张由 N×MN \times MN×M 个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小 Q 想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。
不过小 Q 还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。
于是小 Q 找到了即将参加全国信息学竞赛的你，你能帮助他么？
输入格式
包含两个整数 NNN 和 MMM，分别表示矩形纸片的长和宽。接下来的 NNN 行包含一个 N ×MN ...
P4147「玉蟾宫」
1. 题目
题目链接：P4147「玉蟾宫」 。
题目背景
有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
题目描述
这片土地被分成 N×MN\times MN×M 个格子，每个格子里写着 R 或者 F，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着 F 并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为 SSS，它们每人给你 SSS 两银子。
输入格式
第一行两个整数 NNN，MMM，表示矩形土地有 NN 行 MMM 列。
接下来 NNN 行，每行 MMM 个用空格隔开的字符 F 或 R，描述了矩形土地。
输出格式
输出一个整数，表示你能得到多少银子，即「3×3\times3×最大 F 矩形土地面积」的值。
输入输出样例
输入 #1
1234565 6 R F ...
单调栈
1. 简介
单调栈是一种用来解决首递增序列问题的数据结构，其满足从栈顶元素到栈底元素单调的性质。单调栈还可以用来解决求矩形统计图中最大内矩形面积的问题，进一步可以用来求最小矩阵和问题。
2. 概念
首递增序列
对于序列 a1,a2,⋯ ,aNa_1,a_2,\cdots,a_Na1,a2,⋯,aN，定义从左往右 aia_iai 的首递增序列为 ab0=ai,ab1,ab2,⋯ ,abma_{b_0}=a_i,a_{b_1},a_{b_2},\cdots,a_{b_m}ab0=ai,ab1,ab2,⋯,abm，满足 ∀j∈(0,m]
\forall j \in (0, m]
∀j∈(0,m]，都有 ∀1≤k<bj,abj−1≥ak∧ak<abj
\forall 1 \leq k \lt b_j, a_{b_{j-1}} \geq a_k \wedge a_k \lt a_{b_j}
∀1≤k<bj,abj−1≥ak∧ak<abj 。
首递减序列
对于序列 a1,a2,⋯ ,aNa_1,a_2,\cdots,a_ ...
POJ3250「Bad Hair Day」
1. 题目
题目链接：POJ3250「Bad Hair Day」 。
Description
Some of Farmer John’s NNN cows (1 ≤ NNN ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.
Each cow i has a specified height hih_ihi (1 ≤ hih_ihi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow iii can see the tops of the heads of cows in front of her ( ...
后缀数组
1. 简介
后缀数组是处理字符串的一种强有力工具，高效而且容易编程实现，可应用于求字符串的多种子串问题中，可谓处理字符串的一大利器。
2. 思想
2.1 子串
字符串 SSS 的子串 s[i..j], i≤js[i..j], \ i \leq js[i..j], i≤j 表示串 SSS 中从第 iii 个字符到第 jjj 个字符形成的字符串。
2.1.1 重复子串
字符串 sss 在字符串 SSS 中至少出现两次，则称 sss 为 SSS 的重复子串。
可重叠重复子串：即重复子串间可以重叠部分子字符串。
不可重叠重复子串：即重复子串间不可以有部分重叠的子字符串。
2.1.2 回文子串
字符串 SSS 的子串 sss 满足 inverse(s)=s
inverse(s) = s
inverse(s)=s ，则称 sss 为 SSS 的回文子串。
2.1.3 公共子串
如果字符串 sss 同时出现在字符串 SASASA 和 SBSBSB 中，则称字符串 sss 为字符串 SASASA 和 SBSBSB 的公共子串。
2.2 前缀 & 后缀
前缀是指从串开头到第 iii 个字符形 ...
桶排序
【注】参考自教材「算法导论」。
1. 简介
桶排序是将待排序序列分到有限数量的桶中，然后对每一个桶分别进行排序。桶排序的前提假设为被排序序列的关键字数值符合均匀分布，此时桶排序的平均时间复杂度为 O(n+n2k+k)O(n + {n^2 \over k} + k)O(n+kn2+k)，最坏时间复杂度为 O(n2)O(n^2)O(n2)，其中 kkk 为桶的数量。当桶数量 k≈nk \approx nk≈n 时，此时桶排序的复杂度为线性复杂度 O(n)O(n)O(n) 。
桶排序是非原址的，其稳定性取决于内层排序的稳定性。一般采用稳定的插入排序作为内层排序算法，此时桶排序是稳定的。
2. 思想
桶排序的主要思想是对待排序序列的关键字数值进行分块，每一块对应一个桶，然后对每个桶使用插入排序（或其他排序算法）进行排序，最后将所有桶中的元素串联起来即得到有序序列。
3. 实现
3.1 伪代码
12345678910111213141516BucketSort(A, mx, n) { // mx 为最大数值，n 为桶数量 // 定义 n 个桶 define ...
希尔排序
1. 简介
希尔排序又称缩小增量排序，其也属于插入排序类算法。相较于一般的插入算法、折半插入算法、2-路插入算法以及表插入算法，希尔排序在时间效率上更加优秀。
2. 思想
对于普通的插入算法，其时间复杂度为 O(n2)O(n^2)O(n2)，且在序列有序时，可以达到最好的时间复杂度 O(n)O(n)O(n)；而且当 nnn 较小时，由于移动的元素较少，插入排序效率也比较高。
因此，我们可以采用分治的思想，先将整个待排序序列分割成为若干个子序列分别进行插入排序，待整个序列「基本有序」时再对全体进行插入排序，即自底向上实现整个序列的排序。
【注】这里的子序列不是简单的逐段分割，而是将相隔某个增量的元素组成一个子序列，这样对子序列进行插入排序时，元素就不是一步一步移动，而是跳跃式地往前移。
3. 伪代码
123456789101112ShellSort(A, D) { // 按增量序列 D 对数组 A 进行希尔排序 for i = 1 to D.length // 以下类比与一般的插入排序，增量为 D[i] 而不是 1 for j = D ...
