前言

我们小队能获得JDDC2019的并列亚军(3th),既有运气的成分,也离不开我们做的很多工作。

但本文只具体谈谈我参与JDDC2019的感想与收获,大概就是一篇写给自己的流水账吧。至于检索模型的细节可以参见我的github jddc2019-3th-retrieve-model以及我在12月中旬将完成的一篇关于多轮对话的综述。

正文

其实在参加这个比赛之前,我对NLP都只是一知半解,因为NLP的基本模型太多了,看书看得不明白,也没有对模型有个总体的认识。

在完成JDDC这个比赛的过程中,我确实获益良多。主要可以分为三个方面:

数据预处理(数据探索性分析)

在数据探索性分析的过程中,我发现世界之大无奇不有,有很多有趣的事情都蕴含在语料之中。

列举几个影响比较深刻的例子:最长的会话长度(即多次QA的句数之和)有300句,可以说是客服和用户“大战”300回合;最长的用户提问有超过两万个字,是由一个短句复制了无数遍产生,可想而知用户当时的心情有多么的崩溃;有的用户前言不搭后语,还存在大量错别字,可以看出用户是刚刚接触网购,对拼音和手机沟通比较生疏。

而这次的数据预处理工作比较让人头疼。之前没有接触过这种基本没有经过处理、在实际对话中产生… Read the rest

归并排序

首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中  
void merge(int a[], int n, int b[], int m, int c[]) {
    int i, j, k;  
    i = j = k = 0;  
    while (i < n && j < m) {  
        if (a[i] < b[j]) c[k++] = a[i++];  
        else c[k++] = b[j++];   
    }  
    while (i < n) c[k++] = a[i++];  
    while (j < m) c[k++] = b[j++];  
}  

可以发现合并有序数列的效率是非常高的,有O(N)此时N = len(a)+len(b)。

加上一点分治的想法:
mergesort1

从而对于一个数组,我们可以如下的方式二分分治:
mergesort2

如上图所示,最下面是我们需要排序的数组。我们把它分成N个长度为1的区间。那么相邻两个区间进行一次… Read the rest

题目

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

Note:题目没有说明,但是边界条件 size num.size() or size <= 0,都需要直接返回空的vector。

四种解法

  1. 暴力,时间复杂度O(n*size)
  2. 线段树,时间复杂度O(nlogn+nlogn)
  3. 用两个优先队列,一个容纳size中的元素pq1,一个容纳已滑动删除的元素pq2。每次滑动时,看当前元素t和pq1.top()的大小,如果相等,则弹出,否则加入pq2。时间复杂度为O(n logn)
  4. 维护一个单调队列,单调队列模板题,维护滑动区间的区间最值。时间复杂度O(n)

不会单调队… Read the rest

写在最前面

早在大二我就想写一篇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