配置overleaf服务器教程

1. 安装docker

   以Ubuntu为例：安装，其他系统的安装问题可Google解决。

   国内用户下载docker镜像很慢，可以使用国内镜像加速服务。亲测阿里云的加速比中科大快很多，推荐使用阿里云（内含配置教程）。

   more >>

2018华中科技大学计算机学院保研机试真题

写在最前面

侥幸在保研上机的时候拿到满分，在此记录下考试的题目以及一些体会。

因为考试试卷和答案代码均不能带出考场，以下内容皆为回忆版，附上我仓促写的答案代码，如有不妥还望指教。

0. 前言

机考成绩在保研中占比越来越重，在最后参加机考的人里，加权相差也不会太大，而机考可以轻轻松松拉开二三十分的差距，所以不夸张的说，上机考试一考定乾坤。

不过学院一直在淡化机考，突出CCF CSP考试的重要性，往后有可能只将CCF CSP作为上机唯一标准，所以希望学弟学妹尽早把CSP刷高。当然，CSP难度比机考大很多，但所谓 “取法乎上，仅得乎中”，如果仅仅准备学院机考，最后成绩可能也未必理想。

Leetcode以及牛客网上的题目比较偏重于完成某个小函数，可能与机考以及CSP套路不太相同，这里更推荐刘汝佳大佬的《算法竞赛入门经典》，完成了上面一定量的题目后，学院机考便不在话下。

AVL的SML实现

我们通过一个简单的数据结构(AVL平衡二叉树)，对比了函数式语言和命令式语言的区别和联系。并且，通过一些大样例的实验，分析函数式和命令式语言在运行速度方面的特点。

与命令式C语言对比

AVL平衡树是在BST的基础上，加入平衡操作得到的。具体来说，对于一棵AVL树的插入和删除操作，我们必须要保证树的平衡性，即某个节点的左右孩子的高度之差最多为1。由此，引入了旋转的操作，分别为左旋、右旋、双左旋和双右旋。

AVL定义

首先，需要定义这个数据结构。对于SML来说，提供了类似typedef和struct的语法，可以得到如下的定义：

1
2
3
4

type data = int;
type height = int;
datatype AVL = Leaf
            |  Node of AVL * data * height * AVL;

函数式语言SML简介

摘要

从函数式语言家族的起源来看，其问世以来的数十年间，始终是作为一类小众的语言。大多数情况下，只有实验室对其进行一些理论上的研究。但是，随着编程语言的不断发展，我们看到越来越多的主流语言，将函数式特性或者函数式思想纳入到了自己的体系之中。

通过对于函数式语言特性的分析，我们可以了解到其独特的优点。正式由于其严格的类型检查和良好的封装，使得程序员能加不容易写出错误的程序。同时，得益于其数学思想，程序员可以很方便的写出更加优雅且利于并行的程序。这正是函数式特性在现代编程语言如C++、Java、Python不断得到加强的原因。

Binary Indexed Tree

问题描述

首先来引入一个问题：

给定$n$个数字，有两种频繁的操作需要处理：

• 求$\sum_{k = i}^j A_k$；
• 对某个$A_i$数据进行增减操作。

如果我们使用普通的数组，这两种操作的复杂度分别为$O(n)$和$O(1)$，如果进行$m$次操作，最坏的情况下，复杂度是$O(mn)$的。

所以，为了降低复杂度，我们可以使用一种数组数组的结构，可以将复杂度降低到$O(m\lg n)$。当然，可以使用$RMQ$的方法，但是$RMQ$的编程实现稍微麻烦些，所以这里介绍数组数组的方法。

LCA and RMQ

问题描述

LCA问题，即最近公共祖先问题。(Lowest common ancestor)

指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。

RMQ问题，即范围最值查询问题。(Range Minimum Query)

针对数据集的一种条件查询。若给定一个数组$A[1, n]$范围最值查询指定一个范围条件$i$到$j$，要求取出$A[i, j]$中最大/小的元素。

特别的，如果$A$上，任意两个相邻元素相差为$\pm1$，则称此$RMQ$问题为$\pm1RMQ$问题。

Segment Tree

问题描述

首先，回到树状数组的问题：

给定$n$个数字，有两种频繁的操作需要处理：

• 求$\sum_{k = i}^j A_k$；
• 对某个$A_i$数据进行增减操作。

对于这种情况，使用树状数组肯定是十分方便的，而且编程十分的简单。

但是如果题目的要求更加的灵活，树状数组在很多的情况下是不适和的。(或者更准确的说，对设计技巧要求更高)

现在需要有一个支持区间更新、区间查询等等操作的数据结构，并且要保证每个操作基本可以在$O(\lg n)$的时间完成。

于是我们引入了线段树的数据结构。通过将整体区间进行分割，由叶节点管理最小的分割单元，其他节点以类似$2^k$的形式逐层进行管理。

Suffix Array

问题描述

首先来考虑一个字符串匹配的问题。

假设文本是一个长度为$n$的字符串$T$，模版是一个长度为$m$的字符串$P$，并且$m \leqslant n$。需要求出模版在文本中的所有匹配点$i$。如下图：

这个问题可以通过$KMP$算法解决。

但是如果匹配的模版有多个的时候，$KMP$算法不太合适，因为每次查找一个模版，都要遍历整个文本串。

或者说，更进一步的，如果我们都不能提前知道需要进行匹配的模版，需要我们对于一些动态的模版进行匹配，为了满足速度的要求，我们只能通过预处理$T$串，引入了后缀数组的概念。