写在最前面

早在大二我就想写一篇KMP的总结,主要是因为大部分blog上的文章有着各种各样的不足:有的过于冗长,有的学习曲线太陡,而《挑战》和《算法竞赛》上相关部分都因为字符串相关的内容过多,KMP算法部分不甚详尽。但是当时没有发在blog上,因为感觉从next数组谈起的话,算法的推导总会很奇怪、不顺畅。
时隔两年,花了两天时间,重新梳理了逻辑,缀字成文。

KMP算法有什么用

在文本编辑中,我们经常要在一段文本(text)中找到一串我们想要的字符串(即模板,pattern)的位置。由此,便产生了字符串的匹配问题。而KMP就是为高效解决这一问题提出来的。
kmp1

事实上,KMP算法的运行速度和理解的难度都高于其他的单文本单模板匹配算法。但是KMP算法在Tier树上扩展得到的AC自动机算法,是解决单文本多模板匹配的不二法门。如果读者有志于ACM竞赛的话,KMP算法是不能不理解的基础内容。

基础定义

这里简单地定义几个基础的名词,随着推导的深入,新的名词会在文中给出定义。

  • 文本较长,模板较短。我们在文本链上查找模板链。
  • 文本用T表示,长度为n。模板用P表示,长度为m。
  • 文本指针:一个指针
Read the rest

什么是LaTeX

了解LaTeX之前,首先要知道TeX,TEX(TeX)是由著名的计算机科学家Donald E. Knuth(高德纳)发明的排版系统,本质上还是一门宏语言。而LaTeX是基于这门宏语言,经过后人不断的完善形成的一种排版格式。

其和现在很多人使用的、常常用于写文章的Markdown格式,没有本质的不同,都是通过不同标签来控制文章的格式。

快速安装

先给出结论:推荐使用TeX Live( https://tug.org/texlive ) (编译器、内核)+Atom(https://atom.io) (编辑器、IDE)

  1. 分别完全安装上述两个软件
    • TexLive的安装时间会很长,因为它会下载很多可能会用到的宏包,慢慢等待吧=v=
  2. 打开Atom,File -Settings -Install,搜索并安装
    • language-latex
    • latex
    • pdf-view
  3. 安装后,File -Settings -Packages,点击latex的settings选项
  4. 在第一个空白栏“Tex Path”中添加自己安装latex所在的bin目录
  5. 环境已经配置成功,输入下面的测试代码并使用Ctrl+Alt+B运行(或者通过 Packages -LaTeX
Read the rest

前言

本文用尽量简短和明了的方式说明什么是模糊评价模型,以及怎么使用,所以表述可能在数理上不太严谨,请读者多加包涵。

什么是模糊数学模型

1965 年,美国著名计算机与控制专家查德(L.A.Zadeh)教授提出了模糊的概念,并在国际期刊《Information and Control》并发表了第一篇用数学方法研究模糊现象的论文“Fuzzy Sets”(模糊集合),开创了模糊数学的新领域。

模糊数学中有一个研究的热点问题就是“模糊决策”,它就是研究在模糊环境下或者模糊系统中进行决策的数学理论和方法。模糊决策的目标是把决策论域中的对象在模糊环境下进行排序,或按某些模糊限制条件从决策域中选择出最优对象。

当被评价的对象有两个以上时,从多个对象中选择出一个最优的方法称为多目标模糊综合评价决策法。可以将多个事物排序,得到相对排名和得分。
对于美赛,很多问题都可以通过模糊评价模型来得到答案。

基本步骤

  1. 为属性确定特征及其隶属函数
  2. 计算隶属度矩阵
  3. 确定评价矩阵,计算权重
  4. 检验评价矩阵
  5. 计算最后得分并排序
  6. 选取前6个

模糊评价模型的基本概念

模糊集和隶属函数

模糊集:我们要排序的事物集合,这里不妨记作A。
特征:为了将A排序,我们自然… Read the rest

前言

欧几里德算法作为有着非常简短的实现的算法,可能很多初学者(包括当时的我)都不求甚解。本文给出了GCD、LCM的性质,以及欧几里德算法的实现、证明和时间复杂度推导。

什么是欧几里得算法

最大公约数问题是最早被研究的算法问题之一了,并且是ACM竞赛中能涉及到的很多数论内容,比如模线性方程,模线性方程组的基础。

欧几里得算法 (Euclidean algorithm) ,即大部分选手所知的“辗转相除法”,其核心在于不断将两数规模变小,最后实现对数时间内求解两个数的最大公约数。

其核心是:\[gcd(a,b) = gcd(b, a \% b)\]

名词解释

  1. 最大公约数:即最大公因子,能够同时整除a和b的最大因子,记作gcd(a, b),或gcd
  2. 最小公倍数:能够被a和b整除的最小数,记作lcm(a, b),或lcm。
  3. %:指的是取余运算(取模运算),用例: a % b
  4. |:指的是整除运算,a | b表明a可以整除b,即a是b的因子

GCD和LCM的一些性质

  1. a, b都能分解为有限个素数的积
  2. gcd(a, b)中只含a,b的全部公共素因子
  3. lcm(a, b)中含有a,b的所有素因子
  4. \(gcd\%lcm=0\)
  5. \(gcd
Read the rest

什么是哈夫曼树

给定n个权值,作为n个叶结点,构造一棵二叉树,而这棵树的特点是,有n个叶节点,叶节点的值为给定的权值。而内部节点的值为子树的权值和。

这样的二叉树有很多,但树的带权路径和达到最小,则这棵树被称为哈夫曼树。
huffman tree 1

Note:带权路径和指的是所有叶节点的权值*深度和,即\(\Sigma value∗deep=100+2∗50+3∗20+3∗10\)

而我们不妨让内部节点的值为子树的权值和,我们可以发现,实际上一棵树的带权路径和=这棵树的所有节点值之和-根节点的值。(显然)

哈夫曼树有什么用

哈夫曼树主要应用在文本编码上。我们考虑如何将文本中出现的单词编码为二进制数(01串),让文本的总长度最小。

对于文本{1, 1, 2, 2, 3, 3, 3, 5},我们可以将单词1、2、3、5出现的频率作为叶节点的权值,为{2, 2, 3, 1}。那么上述最短编码问题等价于寻找一棵树,其带权路径和最小,也就是找对应的哈夫曼树。

唯一可译码

如果我们直接将单词按照频率的从高到低排序,不就得到了一个编码了吗?

但这样的编码不是一个“唯一可译码”,即对于10001010100101,我们不… Read the rest

CodeForces 1009 div2 ABCD / Educational Codeforces Round 47 div2 ABCD

A Game Shopping

一眼题,随便以一个文本作为基础,扫描另外一个即可

/**
 * @Date:   16-Jul-2018
 * @Email:  zengsw_study@qq.com
 * @Filename: A.cpp
 * @Last modified time: 17-Jul-2018
 * @Copyright: Copr. 2018 EndlessLethe. All rights reserved.
 * @Description:
 */

#include <stdlib.h>
#include <iostream>
using namespace std;

const int MAXN = 1000;
int a[MAXN], b[MAXN];

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> b[i];
    }
    int j = 0, i = 0;
    for (i = 0; i 
Read the rest

前言

Bellman-Ford算法,限于资料匮乏和时间复杂度比Dijkstra算法高,包括白书在内的很多资料,都没说得太明白。对于优化后的SPFA算法也没有提及。
而且最短路问题通常是作为图论的入门问题,学习者通常没有图论基础,不知道图论的一些基本常识,看已有的资料很容易产生疑惑。其实,从Bellman-ford算法优化到SPFA算法实际上是顺理成章的。

本文旨在阐明这两个算法思想和步骤,如果有什么晦涩或者疏漏之处在所难免,烦劳读者们指出。

Bellman-Ford算法有什么用

Bellman-Ford算法是用来解决单源最短路问题的。
在现实生活旅游途中,我们通常想知道一个景点到其他所有景点的最短距离,以方便我们决定去哪些比较近的景点。而这时候,Bellman-Ford算法就有用了。

Bellman-Ford算法的优点是可以发现负圈,缺点是时间复杂度比Dijkstra算法高。
而SPFA算法是使用队列优化的Bellman-Ford版本,其在时间复杂度和编程难度上都比其他算法有优势。

算法流程

(1)初始化:将除起点s外所有顶点的距离数组置无穷大 d[v] = INF, d[s] = 0
(2)迭代:遍历图中的每条边,… Read the rest

Update 2019/07/26:根据读者提出的问题,添加了查找数据方法、时间安排、论文及代码的下载地址等内容。

前言

本文主要是记录这次建模的过程和思路。用到的模型简单提及,并省略数据和结论。

涉及到的最小二乘法、模糊数学模型和马尔科夫链知识可以见我的文章“半小时学习最小二乘法”“模糊评价模型-以2018美赛为例”“马尔科夫链详解(TBC)”。

问题

Problem: A large multinational service company, with offices in New York City in the United States and Shanghai in China, is continuing to expand to become truly international. This company is investigating opening additional international offices and desires to have the employees of each office speak both in English and one or more additional languages. The Chief Operating Officer of… Read the rest

前言

梯度是机器学习中的重要概念,其和拉格朗日乘数法、梯度下降法之间的联系密不可分。所以本文给出了梯度的定义,并证明负梯度的方向是函数下降最快的方向(梯度的方向是函数上升最快的方向)。

至于为什么梯度下降算法能够work,是因为对于凸函数,随着函数下降的方向,一定能到达最小值。取梯度是为了沿最快下降方向,降低迭代次数。后来发现对于非凸函数,梯度下降算法表现不错,所以对于非凸函数也有使用。更具体的内容,见下一篇文章《梯度下降算法》。

本文重点结论

本文有大量证明,部分读者可能会感到有些冗余,故将重点结论罗列于下:
1. 梯度\(
\nabla f\left( {{\theta_1},{\theta_2},\cdots,{\theta_n}} \right) = \left( {\frac{{\partial f}}{{\partial {\theta_1}}},\frac{{\partial f}}{{\partial {\theta_2}}},\cdots,\frac{{\partial f}}{{\partial {\theta_n}}}} \right)
\)
2. 梯度的方向是函数上升最快的方向
3. 梯度是 || … Read the rest

前言

这是我在上学期面试中遇到的一道概率题,现场没做出来,让面试官快速进入算法题环节了= =
今天突然联想到最近在看的内容,一下子顿悟了,开心
其实这道题是语文题

题面

甲认为一道题是对的,且这道题是对的概率为0.9。乙认为一道题是对,且这道题是对的概率为0.8。求甲乙都认为一道题为对,且这道题确实为对的概率?

Note:答案不等于0.72… Read the rest