KMP 1. 简介 KMP 算法是一种优秀的字符串模式匹配算法，相对于暴力匹配方法来说，其改进在于：每当一趟匹配过程出现字符比较不相等时，不需回溯主串的 iii 指针，而是利用已经得到的「部分匹配」的结果将模式串向右「滑动」尽可能远的一段距离后（即回溯模式串的 jjj 指针），继续进行比较。 2. 实现 设模式串为 p1p2⋯pmp_1 p_2 \cdots p_mp1p2⋯pm，主串为 s1s 2020-09-03 Technique ACM 算法 字符串 Technique ACM 算法 字符串
字典树 1. 简介 字典树（Trie）用边来代表字母，从根结点到树上某一结点的路径就代表了一个字符串。 2. 实现 由于字典树中的字符串都是从根结点开始，于是我们可以通过标记字符串的终止结点来记录已经插入字典树中的字符串。 我们用 δ(u,c)\delta(u,c)δ(u,c) 表示结点 uuu 的 ccc 字符指向的下一结点，即在结点 uuu 代表的字符串后面添加一个字符 ccc 形成的字符串的结点 2020-09-02 Technique ACM 算法 字符串 Technique ACM 算法 字符串 数据结构 算法
字典树 1. 简介 字典树（Trie）用边来代表字母，从根结点到树上某一结点的路径就代表了一个字符串。 2. 实现 由于字典树中的字符串都是从根结点开始，于是我们可以通过标记字符串的终止结点来记录已经插入字典树中的字符串。 我们用 δ(u,c)\delta(u,c)δ(u,c) 表示结点 uuu 的 ccc 字符指向的下一结点，即在结点 uuu 代表的字符串后面添加一个字符 ccc 形成的字符串的结点 2020-09-02 Technique ACM 算法 字符串 Technique ACM 算法 字符串 数据结构 算法
P2580「于是他错误的点名开始了」 1. 题目 题目链接：P2580「于是他错误的点名开始了」 。 题目背景 XS中学化学竞赛组教练是一个酷爱炉石的人。 他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛 CON900）。 题目描述 这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么 2020-09-01 Technique ACM 题解 Technique ACM 题解
平面图 1. 定义 1.1 平面图 & 非平面图 如果能够将无向图 GGG 画在平面上使得除顶点处外无边相交，则称 GGG 为可平面图，简称平面图。 画出的无边相交的图称作 GGG 的平面嵌入。 无平面嵌入的图称作非平面图。 2. 性质 平面图的子图都是平面图，非平面图的母图都是非平面图。 2020-09-01 Technique Math Theory 图论 Technique Math Theory 图论
支配集、独立集、覆盖集 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) \i 2020-09-01 Technique Math Theory 图论 Technique Math Theory 图论 math
排队论模型 1. 简介 我们使用六个符号表示排队模型，在符号之间用斜线隔开，记为 X/Y/Z/A/B/C 。第一个符号 X 表示顾客到达流或顾客到达间隔时间的分布；第二个符号 Y 表示服务时间的分布；第三个符号 Z 表示服务台数目；第四个符号 A 是系统容量限制；第五个符号 B 是顾客源数目；第六个符号 C 表示的是服务规则，例如先到先服务 FCFS， 后到先服务 LCFS 等。 2. Little（利特尔） 2020-09-01 Technique Math Modeling Technique Math Modeling
欧拉图 1. 定义 1.1 欧拉通路 & 欧拉回路 通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的通路称作欧拉通路。 通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路。 【注】规定平凡图是欧拉图。 1.2 欧拉图 & 半欧拉图 具有欧拉回路的图称为欧拉图。 具有欧拉通路而无欧拉回路的图称作半欧拉图。 2. 性质 无向图 GG 2020-08-31 Technique Math Theory 图论 Technique Math Theory 图论 math
哈密顿图 1. 定义 1.1 哈密顿通路 & 哈密顿回路 经过图（无向图或有向图）中所有顶点一次且仅一次的通路称作哈密顿通路。 经过图（无向图或有向图）中所有顶点一次且仅一次的回路称作哈密顿回路。 1.2 哈密顿图 & 半哈密顿图 具有哈密顿回路的图称作哈密顿图。 具有哈密顿通路但不具有哈密顿回路的图称作半哈密顿图。 【注】规定平凡图是哈密顿图。 2. 性质 【注】p 2020-08-31 Technique Math Theory 图论 Technique Math Theory 图论 math
P1169「棋盘制作」 1. 题目 题目链接：P1169「棋盘制作」 。 题目描述 国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 8×88 \times 88×8 大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。 而我们的主人公小 Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小 W 决定将 2020-08-30 Technique ACM 题解 Technique ACM 题解