至少半年没写算法题了，手生了不少，由于python写太多导致行末老是忘记打分号，printf老是忘记写f，for和if的括号也老是忘写，差点连&&和||都忘记了。题目都是回忆版本，可能有不准确的地方。代码如果有机会能拿到的话，会补充的。

开始复习，过了一遍大部分板子本来打算再学一遍SAM，但是想到去年考了字符串大题今年应该不会再考了吧。。过了一遍数据结构和图论，就1点了两点的时候还没睡着，舍友打游戏好像打到2点过。。

题面：https://loj.ac/problem/6038题解居然再原题重测（原题重错、新题爆错）的考场上切了一道LCT的题（对于我这种菜鸡来说这是新题）一看就是维护森林中每棵树的直径以为可以用倍增LCA来求两点距离，发现它强制在线想了一下，发现可以用LCT来求两点距离因为所有的边权都为1，所以我们把一条链spilt出来后得到的链的节点树-1就是两点的距离...

一、相关概念1.完美匹配如果一个二分图，X部的每一个顶点都与Y部的一个顶点匹配，并且Y部的每一个顶点也与X部的一个顶点匹配，则该匹配为完美匹配。2.完备匹配如果一个二分图，X部的每一个顶点都与Y部的一个顶点匹配，或者Y部的每一个顶点也与X部的一个顶点匹配，则该匹配为完备匹配。完美匹配属于完备匹配。3.最大权匹配带权二分图的权值最大的匹配为最大权匹配。

一、题目描述总时间限制: 1000ms 内存限制: 65536kB描述有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a.    每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b.    走过的格子立即塌陷无法再走第二次；c.    只能向北、东、西三个方向走；请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步

A组，当然是 很 蓝 的 啦答案是n*m+3，无法节省步数先手必败无论先手怎么下，必定可以转化为xxxooooo然后，如果先手下第一行，后手就可以下第二行中间两个xxxxoxxo必败如果先手下第二行，则后手必定可以把第二行转化为oxxx或xxxoxxxo 或 xxxooxxx xxxo必败有种不好的预感啊，“必败”水，代码：#include<cstdio>#define LL long

一、启发式合并的算法原理一听这名字，感觉好高大上，实际上很简单。之前讲过并查集的大部分时间都浪费在了find()函数上，于是就对find()函数进行了优化，其实还有一种算法可以使find()函数的时间复杂度控制在O(logn)左右，这种算法就是启发式合并。并查集是一种树型的数据结构，而树也有它的深度，如果我们把一棵深度大的树的根节点接在了一棵深度小的树上，那么整棵树的深度为那一棵深度大

一、题目描述犯罪团伙(gang.cpp)题目描述 警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。输入 第1行：n（输出 第1行：一个

一、题目描述最短路径问题(floyed.cpp & dijkstra.cpp)题目描述平面上有n个点(n输入第1行：1个整数n第2..n+1行：每行2个整数x和y，描述了一个点的坐标第n+2行：1个整数m，表示图中连线的数量接下来有m行，每行2个整数i和j，表示第i个点和第j个点之间有连线最后1行：2个整数s和t，分别表示源点和目标点输出

一、题目描述给n个区间，形式为[a, b]，a和b均为整数，且a求一个最小的整数点的集合，使得每个区间至少2个不同的元素(整数点)属于这个集合。求这个集合的元素个数。输入第1行：1个整数n(1接下来n行，每行2个整数，表示区间的左右端点a, b(0输出第1行：1个整数，表示集合的元素的个数样例输入43 62 40 24 7样例输出