2020 NOIP赛前总结

伢子妹子们一定要杜绝答案错误

伢子妹子们一定要杜绝文件错误

伢子妹子们一定要杜绝非知识性错误

它与每题得分绝不是一句空话

红太阳xqz和金牌爷Fuyuki与你同在

[toc]

1 整体评价

NOIP赛前集训于11月14日正式开始，在停课集训的一段时间内，针对不同算法，不同数据结构进行测验以及学习，还有一些模拟赛，作为NOIP前的热身与准备，一些题目较难但总体来说和联赛难度差不多，自认为在这三个星期的时间内对于信息学竞赛有了更深一步的认识，对于信息学的了解进一步加深了，同时个人的代码能力与思维和思考方式都得到了极大的提升

从今年八月第一次接触信息学竞赛到如今联赛前最后的冲刺，一路走来感想与收获颇多，兴趣与热情不但没有磨灭但反倒在这个过程中得到了更大的提升

现将近期感想总结于下：

整份总结分为四个部分（根据前人经验）：考试成绩表，考试总结，整体提升，不足与反思

2 考试成绩

咕了·······

3 每日考试总结

咕了·······

4 动态规划

在联赛中动态规划一类的算法对于思维的考察量是最大的，对于状态的设计以及对于状态转移方程的设计都是具有一定难度的，在考场上提高动态规划的设计能力以及对于部分正确的状态转移的分析能力尤为关键，必要时可以采用搜索代替动态规划

4.1 数位$DP$

数位$DP$是在$11.28$日晚上在高二学长$xzx34$的$T1$中接触到的

数位$DP$：主要用来解决给定区间 $[A,B]$内，符合条件$ f(i)$的数 $i$的个数。条件 $f(i)$一般与数的大小无关，而与数的组成有关，由于数位$DP$主要是按位$DP$所以数的大小对于复杂度的影响较小

对于$[l,r]$区间问题，我们一般把他转化为两次数位$dp$,即找$[0,r]$和$[0,l-1]$两段，再将结果相减就得到了我们需要的 $[l,r]$

模意义下的数位统计一般是要求一个数长度为$𝑛$，这个数$mod \ 𝑝$以后余数为$𝑎$的数的 个数。第一次思考这个问题的时候我的想法是从低位向高位递推，但是明显是行不通的， 因为从低位向高位需要讨论很多细节。因此我们可以采用从高位向低位递推的方法，注 意到在一个数$𝑥$后面增加一个数字$\ 𝑘$，它$mod \ 𝑝$的值也相应的在后面增加了一个数字$𝑘$，并 再次对$\ 𝑝$取余。这就很方便我们从高位开始递推，一边递推一边统计即可。 需要注意的一个细节是，一般的数字是不包含前导$0$的，因此对于特殊题目的第$一$ 位要记得特殊处理

4.2 状压$DP$

状压$DP$主要指通过将状态压缩为二进制数，三进制数等不同形式来代表事物的状态，主要与位运算结合使用，一般适用于$n$较小的情况，由经验可得$n\le23$时一般采用二进制，$n\le30$时一般采用三进制

状压DP适用于数据规模比较小的棋盘， 图的统计，最优问题中，一般情况下用二进制来的0和1来表示状态，因此时间复杂度为 指数级别，空间复杂度也为指数级别。虽然出现的次数并不是很多，但还需要对其进一 步掌握。

对于状压$DP$这一类的问题一般会应用到枚举子集的技巧，关键在于标蓝的一行，时间复杂度为$O(3^n)$

4.3 树形背包

树形背包是背包中的一大类，同时也是一个非常难的考点，常考技巧有于泛化物品结合考察，以及各种依赖关系成树形的一类$DP$问题，或者是直接在树上进行的一类$DP$问题

树形DP的做法一般建立在$DFS$上，或者是由 根节点向下的拓扑序上。主要难点在于设计树上的状态。一些常见的题型有：在树中选 几个点，达到一个目标。状态通常可以表示为$f[节点][0,1][子树中选择节点的个数]$，还有 一些其它的状态设计方法还需要自己再进一步深入研究。

树形$DP$有时候还会与背包问题联系在一起，这样就大大加深了问题的难度。一个比 较经典的例子是“有依赖性的树形背包”，这道题可以根据状态数组的连续段，把需要 转移的状态数减少了，最后再还原到该求的状态，达到优化复杂度的目的

对于状态而言，一般记录$f[i][j]$表示以$i$为根的子树中选了$j$个物品的最优方案，有时也 会多加一维$0$和$1$来表示根节点是否被选。

对于转移而言，需要谨慎处理转移的顺序。一种比较好的方法是先处理当前节点 的每个儿子节点，每处理完一个节点后就枚举从大到小一个$a$，表示之前已经处理过的 儿子节点中总共选$a$个物品最优解，再枚举一个$b$，表示当前儿子节点中选$𝑏$个的最优解， 用$𝑎$和$𝑏$来更新当前节点的$𝑎 + 𝑏$，前提是$𝑎 + 𝑏$在总的限制范围内。当处理完所有的儿子节 点后，再枚举当前节点的数量，把当前节点的有关信息与所有儿子节点的信息合并起来， 达到全局最优的目的。这样操作可以形象地理解为“先计算儿子，再把自己插入进去”， 理解了思想以后，实现起来问题不是很大，但是仍然要落实，以防考试时出现紧张而忘记代码细节。

4.4 字符串$DP$

这里指的并不是字符串算法，而是一个基于字符串的一个$DP$算法。这个模型比较经 典的题就是“最长公共子串$（LCP）$”，做法是设$f[i][j]$表示第$1$个串的前$𝑖$位和第$2$个串的 前$𝑗$位的$DP$结果，从小到大枚举两个字符串的$𝑖$和$𝑗$，可以简单的列出转移的方程$f[i][j]=min(f[i][j-1],f[i-1][j])$但且仅当$a[i]=b[j]$时$f[i][j]=f[i-1][j-1]+1$，实现 起来也不是很困难，时间复杂度为$𝑂(𝑙𝑒𝑛^2 )$。在集训的一次考试也遇到了类似的题目，当 时我并没有想出这道题的做法，考试后通过请教才通过这道题的做法归纳出这一类型题 可以用这种方式来$DP$，只是还需要在自己脑海里加深印象，以后遇到这种题目要能够想到使用这种方法。

5 贪心与随机化算法

贪心算法在各种比赛与考试中应用广泛，在各类难题的部分分解法中发挥着极其重要的作用，对于无法想出正解的题目，应用贪心与各种随机化算法能起到意想不到的作用

举个栗子：听说在$NOI\ 2020$中高二某学长在$Day\ 2$ $T2$中应用随机化贪心混到$70$分比考场上众多写网络流与思考$DP$算法的高手高出$40$到$50$分（大雾）

贪心算法的核心：以局部最优的贪心策略来保证全局最优

5.1 随机化贪心

前置知识：$STL$中各种随机化函数的用法

对于随机化算法的卡时技巧

$clock()$是$C/C{++}$中的计时函数，它的返回值为程序从启动到函数调用占用$CPU$的时间

$CLOCKS_PER_SEC$是标准$c$的$time.h$头函数中宏定义的一个常数，表示$一$秒钟内$CPU$运行的时钟周期数，用于将$clock()$函数的结果转化为以秒为单位的量，但是这个量的具体值是与操作系统相关的

具体用法：$while ((double)clock() / CLOCKS_PER_SEC \le 0.95) work()$;

其实具体说来随机化贪心并不是一种算法，而是一种思想，具体说来其实就是将一种错误的贪心策略，重复多次以最大程度得到正解，结合上面的卡时技巧能收获不一般的分数

5.2 爬山算法

概念：爬山算法是一种局部择优的方法，是一种局部贪心的最优算法。
采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 该算法每次从当前解的临近解空间中选择一个最优解作为当前解。 直到达到一个局部最优解，属于人工智能算法的一种。

多起点爬山对于大部分答案呈现多峰函数趋势的题目来说是一个绝佳的选择

上板子

5.3 模拟退火算法

模拟退火算法$（Simulate Anneal，SA）$是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。

模拟退火是由$S.Kirkpatrick$,$ C.D.Gelatt$和$M.P.Vecchi$在1983年所发明的。$V.Černý$在$1985$年也独立发明此演算法。

模拟退火算法是解决$TSP$问题的有效方法之一。

模拟退火的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。

——百度百科

简单说，模拟退火是一种随机化算法。当一个问题的方案不是一个单峰函数时，我们常使用模拟退火求解。它与爬山算法最大的不同是，在寻找到一个局部最优解时，赋予了它一个跳出去的概率，也就有更大的机会能找到全局最优解。

对于模拟退化来说调参是一个痛苦的过程，在$IOI$赛制中应用空间极其优越，但在普通平时的$OI$赛制中并不建议使用，对于模拟退火中的$exp$来说由高$二$某巨佬学长透露可以采用在距末温较远的时候每次$\times0.98$距离末温不远时$\times 0.0098$使每次的答案更接近正解

5.5 小总结

1 随机化贪心非常的$nb$

2 随机化贪心的正确率随贪心次数的增长而增长

3 随机化贪心的正确率受随机种子影响，建议选取较大的质数作为随机种子

4 ** **爬山算法看起来很好卡但实际上表现非常优秀。在$OI$中，很多构造$/$最优化问题都可以使用爬山算 法来解决。对于普通$OI$赛制中更推荐使用多起点爬山而不是模拟退火

6 分治与二分答案

分治在很多数据结构以及常用算法中都有具体体现，最经典的模型是$CDQ$分治以及归并排序，同时二分答案的思想在比赛中经常用到，二分法是个神奇的东西你永远也不知道循环条件到底是小于还是小于等于，$L$到底是等于$mid$还是$mid-1$······

6.1 分治算法

6.1.1 归并排序

来上个归并排序的板子

当然线段树也是分治算法的典型体现，在后序数据结构篇会有更具体的总结，此处暂时不提

6.1.2 $CDQ$分治

$CDQ$ 分治和整体二分都是基于分治的思想，把复杂的问题拆分成许多可以简单求的解子问题。但是这两种算法必须离线处理，不能解决一些强制在线的题目。不过如果题目允许离线的话，这两种算法能把在线解法吊起来打（如树套树）。

普通分治与${CDQ}$分治都是基于分治思想之上的算法，但是他们是有区别的。普通分治的适用条件是，产生的小问题之间互不影响，然而分治就相对比较宽泛，小问题之间可以有影响，但是${CDQ}$分治不支持强制在线。

分治一共分为四步：

　1) 将当前处理区间分为左右两个等大的子区间；

　2) 递归处理左子区间；

　3) 处理左区间对于右区间的影响，并对于右区间或者答案进行更改与修正；

　4) 递归处理右子区间；

　　上面就是$CDQ$分治的四个步骤，这四个步骤之中第一、二、四步对于不同的题目来说基本上是相同的，因为毕竟分区间，递归没有什么好更改的。对于不同的题目来说不同点就是第三部，这一步也是$CDQ$分治的难点，对于这一步的讲解也要借助于例题。

讲 ${CDQ}$分治的时候就少不了经典的多维偏序问题了。

6.1.2.1二维偏序问题

给定 $n$ 个元素，第 $i$ 个元素有 $a_i$, $b_i$ 两个属性，设$f[i]$ 表示满足 $a_j\ \le\ a_i$ 且$b_j\ \le\ a_i$的 $j$的数量。对于 $d\in [0,n]$，求满足 $f(i)=d$ 的数量。

首先，我们可以把两个元素抽象成一个点 $(a,b)$，那么我们就是求一个矩形中有多少个点。

6.1.2.2 三维偏序问题

其实三维偏序就是在二维偏序上加一维而已。

我们先按每个元素的属性 $a$排个序，然后第二维用归并排序，第三维用树状数组。

我们在归并的时候考虑 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。因为我们已经按属性 $a$ 排过序了，所以在排序属性 $b$ 的时候，无论属性 $a$怎么被打乱， $[mid+1,r]$ 所有元素的属性 $a$ 一定不小于$[l,mid]$ 中所有元素的属性 $a$，所以第二维是成立的。

在满足前两维都是有序的时候，类似二维偏序的解法，我们可以用树状数组来统计答案了。

在【模板】三维偏序中， $a_j\le \ a_i$且 $b_j \le\ b_i$ 且 $c_j \le\ c_i$中是有取等号的，所以我们需要对元素进行去重，最后统计最终的答案，时间复杂度$O(n\times\ log{^2}_n)$

6.1.2.3 四维偏序问题

四维偏序就比较恶心了，需要 $CDQ$ 套 $CDQ$ 套 树状数组

怎么叫 $CDQ$套 $CDQ$呢？

我们可以在第二维$CDQ$ 的时候，记下那些元素在左区间还在右区间。在第三维 $CDQ$ 的时候保持前两维的有序时，加一个树状数组，时间复杂度$O(n\times log^3{_n})$

6.2 二分答案

6.2.1 整体二分

整体二分类似于一些决策单调性的分治，可以解决诸多区间第$k$小或区间第 $k$ 大的问题。

整体二分 solve(l,r,L,R) 表示答案在 $[l,r]$ 中，与操作 $[L,R]$ 有关（操作 $[L,R]$不一定对应原来 $[L,R]$ 的操作）

我们就拿静态区间第$k$小来说好了。如果原序列的数 $\le \ mid$，那么就在树状数组中对应位置 $+1$。如果碰到询问操作，那么查询询问区间 $[ql,qr]$的值相当于查询了区间中值在$[l,mid]$的个数，如果个数 ，$\le \ k$那么答案在 $[mid+1,r]$中，那么把 $k$减掉对应的个数，把操作分到右区间。否则答案在$[l,mid]$中，把操作分到左区间。

如果 $l=r$，那么直接把 $ans$ 记录一下就好了。时间复杂度 $O(n \times\ log^2{_n})$如果将答案离散化一下，常数理论上会小下很多。

那么动态区间第 $k$小带修改操作怎么搞呢？我们可以把原来的减掉再加上后来的，然后跑一遍整体二分就好了。

6.2.2 二分答案

每一次做二分答案的题目都是对其更深一步的理解。掌握二分答案的基本做法及判断边界的方法是运用二分思想解决题目的关键二分答案模型现在实现起来并不难，重要的是要学会从一个问题中发现二分答案的做法。对一个问题来说最重要的就是其答案的“可二分性”，必须仔细判断再选择实现方法

7 位运算

因为位运算是直接对数据的二进制进行处理，因为直接操作的是$0/1$字符串所以会比一般运算快很多，在程序中多使用位运算能让程序看起来更优雅，同时效率也会大大提升。对于有关位运算的题目来说，拆位是一个基本且重要的思想

7.1 线性基

线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数。

对于一组数$A_1,A_2,A_3, \dots\ A_n$ ，他们的线性基为 $d_1,d_2,d_3 \dots\ d_n$,其中 $di$ 是出现 1 的最高位在第 $i $位的数

线性基三大性质

1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到

2.线性基里面的任意一些数异或起来都不能得到$0$

3.线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

线性基的功能是通过异或运算的性质，解决与“异或和”有关的问题。其思想在于把大量$32$位整数缩小成最多$31$个数，达到这$31$个数能够异或得到之前 大量数的所有异或和，缩小了数据规模从而能够快速求解。插入的具体做法是枚举新整数的每一位，如果线性基中存在该位的数则把新数异或该位置上的数，接着往下判断，否则把当前的数插入线性基的当前位置。通过贪心扫描线性基可以求得线性基内元素的最大异或和。

构造：

7.2 求$2$进制数中$1$​的个数

求一个$2$进制数中$1$的个数并不需要对每一位进行扫描，只需运用$lowbit$操作即可。由于$lowbit$的作用是求出一个二进制数最后一 个$1$的位置，因此可以把数$x$不断减去$𝑙𝑜𝑤𝑏𝑖𝑡(𝑥)$，每次计数器变量累加,直到$𝑥$为$0$，则计 数器的值就是$1$的个数。此做法看上去效果不佳，但是在大规模数据应该会对效率起到优化作用。

7.3 一点点总结

由于位运算与二进制是密不可分的，在遇到位运算的时候不妨也想一想能否把要处 理的数据进行二进制拆分再来处理，也许会方便一些。

与异或有关的题目还可以选择找规律，通常也可以发现题目的一些做法。

8 字符串匹配

字符串算法在联赛中考查较少同时也是我掌握的比较不熟与比较不能理解的一部分，但与此同时，还是要学

8.1 $KMP$算法

$KMP$算法的核心，是一个被称为部分匹配表$(Partial Match Table)$的数组。先来理解一下这个数据到底是什么

对于字符串$abababca$，它的$PMT$如下表所示：

好了，解释清楚这个表是什么之后，我们再来看如何使用这个表来加速字符串的查找，以及这样用的道理是什么。要在主字符串$ababababca$中查找模式字符串$abababca$。如果在$ j $处字符不匹配，那么由于前边所说的模式字符串 $PMT$ 的性质，主字符串中$ i $指针之前的 $PMT[j −1] $位就一定与模式字符串的第 $0 $位至第 $PMT[j−1] $位是相同的。这是因为主字符串在$ i$ 位失配，也就意味着主字符串从 $i−j$ 到$ i$ 这一段是与模式字符串的$ 0 $到$ j $这一段是完全相同的。而我们上面也解释了，模式字符串从 $0$ 到$ j−1$ ，在这个例子中就是$ababab$，其前缀集合与后缀集合的交集的最长元素为$abab$， 长度为$4$。所以就可以断言，主字符串中i指针之前的$ 4 $位一定与模式字符串的第$0$位至第 $4 $位是相同的，即长度为 $4 $的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持$i$指针不动，然后将j指针指向模式字符串的$PMT[j −1]$位即可。

理解：对于模式串$abababca$，模式串进行自我匹配，用匹配表存下一个后缀的最长真前缀，那么匹配时当失配的时候，即可直接将模式串往后移动实现时间复杂度的优化

void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
         j++;k++;
         next[j] = k;//直到匹配上以后加一
      }
      else k = next[k];//往前回溯
   }
}

int KMP(String s,String t)
{
   int next[MaxSize],i=0;j=0;
   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s[i]==t[j])
      {
         i++;
         j++;
      }
      else j=next[j];               
   }
   if(j>=t.length) return (i-t.length);         
   else return (-1);                  
}

8.2 字符串$Hash$

字符串$Hash$在判断两个字符串是否相同时应用非常广泛。对于给定的一个字符串， 我们可以在$𝑂(𝑛)$内求得这个字符串每个元素所代表前缀的$Hash$值，通过$Hash$值的计算 公式，之后就可以在$𝑂(1)$ 时间内计算任意一段区间所表示的字符串的$Hash$值，更加方便了查询。首先是$Hash$值的递推公式：

$$Hash_i= (Hash_{i-1} \times\ seed + a_i) \ 𝑚𝑜𝑑 MOD$$

其中$seed$为$Hash$种子，$MOD$为模数。接下来是计算一段区间的$𝑖$到$𝑗$的$Hash$值$x$：

$$𝑥 = ℎ𝑎𝑠ℎ𝑗 − ℎ𝑎𝑠ℎ{𝑖−1}\ \times\ 𝑠𝑒𝑒𝑑^{𝑗−𝑖+1}$$

这里就没有写取模的操作，因为接下来要针对两种取模方式做一下比较。在此之前先提一下$Hash$种子：这个数一般为字符集${\sum}$的大小$+1$，这样避免了$Hash$值表示的字符串有多个的情况。但是选取的种子与取模的模数一定要是互质的，不然之后就会出现$Hash$值一 直为$0$的情况，这一点如果手动取模选取质数作为模数就没问题，但是如果采用自然溢， 必须选取一个奇数作为模数。接下来是比较：

手动取模+两个模数 如果采用手动取模的方法，比较保险也是非常保险的做法是设置 这两个数作为模数：$10^9 + 9$与$10^9 + 7$。这两个数为孪生质数，用这两个数来进行取模的话，两个字符串的$Hash$值冲突的概率几乎为零。但这种做法的缺点就是取模的常数巨大，如果题目时限稍微设置得紧一些就会因为被卡常数而无法通过,因此这种方法通常在时限较宽松的情况下使用。

自然溢 与手动取模相对应的，自然溢的特点就是低时间与高风险了。自然溢取模的原理是通过无符号整型的范围自动对$2^{64}$取模，因此不需要人为的取模操作，时间上比较迅速。但是缺点在于风险较高，如果出题者有意要卡自然溢，可以通过构造特殊数据来达到这个目的。另外，如果两个数自然溢有冲突的话，也无法在程序中辨别，因此也需要谨慎选择，提高自己的辨别能力。

8.3 自动机($DFA$)

自动机是一个对信号序列进行判定的数学模型。

这句话涉及到的名词比较多，逐一解释一下。$“信号序列”$是指一连串有顺序的信号，例如字符串从前到后的每一个字符、数组从 $1$ 到$ n$ 的每一个数、数从高到低的每一位等。$“判定”$是指针对某一个命题给出或真或假的回答。有时我们需要对一个信号序列进行判定。一个简单的例子就是判定一个二进制数是奇数还是偶数，较复杂的例子例如判定一个字符串是否回文，判定一个字符串是不是某个特定字符串的子序列等等。

自动机是一个数学模型，可以简化为一个有向图。

形式化定义

**1 字符集($\Sigma$) ,**该自动机只能输入这些字符

2 状态集合($Q$) 。如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点

3 起始状态($start$),$\ \ start\ \in\ Q$,是一个特殊状态

4 接受状态集合($F$) ,$\ F\ \subseteq\ Q$是一组特殊的状态

5 转移函数($\delta$),$\ \delta\ $是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个$ DFA $看成一张有向图，那么$ DFA $中的转移函数就相当于顶点间的边，而每条边上都有一个字符

$DFA$ 的作用就是识别字符串，一个自动机$A$,若它能识别（接受）字符串$S$,那么$A(S)=True$，否则$A(S)=False$

9 $0/1$分数规划

接触到$“0-1分数规划”$是在一次贪心专题测试中遇到的（大雾，理解了该类问题的二分答案做法。通过一些该类题 的训练，掌握了关于“0-1分数规划”的数学公式的变形与推导，记住了该类题一些简单的规律，比如题目中出现了“最大值”则应推出一个$“f(a,b)\ge\ ans”$，若出现 “最小值”则应推出$“𝑓(𝑎, 𝑏)\ \le\ 𝑎𝑛𝑠”$的式子，之后求最大或者最小值即可，得到一个 $“g(ans)\ \le或\ \ge\ C”$（$C$为常数）”的式子，根据符号判断求最小值或求最大值。除此之外， 还了解到$“0-1分数规划”$常常与排序，最小/大生成树，最短/长路等模型结合在一起， 并要求通过给定的式子将推出来的新表达式于一个常数判断关系的性质。

如果统计的元素个数不是有限个而是不 定数量时就不能采用$0-1分数规划$的做法，也认为$0-1分数规划$对于$DP$来说无法适用，但 其实是可以的。说到底并没有区别，只是每一步的转移也根据$DP$方程来转移，每转移一 个就在当前元素的$DP$值上减去二分到的答案与某个权值的乘积。由此可见我还需要继 续深刻理解$0-1分数规划$，之后做题要细心思考，谨慎写出$DP$方程

10 搜索

搜索在联赛中的重要性不言而喻，所以将它放在较后的位置讲，照向总的话来说只要你搜索写好了联赛一等奖，就没问题了

对于搜索来说好的剪纸与好的搜索策略是获取高分的一个重要部分

当然对于搜索来说是有很多高级技巧的，一下$一$$一$总结

10.1 $DFS$

手写栈 有很多算法都要建立在$DFS$上，因此$DFS$成了竞赛中一个非常要的$“工具”$。但是在$DFS$的过程中，一定要注意栈的大小，不能因为递归过深而导致爆栈。虽然考试一般会开无限栈。但即便如此，$“手写栈”$来模拟$DFS$时栈的情况，也是一门技术。操作起来并不是很难，但是在与一些其它树上算法搭配的时候可能会需要开设两个栈，一个是算法需要的栈，另一个就是用来模拟递归的手写栈，因此写起来十分麻烦，要特别注意重名问题

剪枝 对于$DFS$来说，为了提高效率，就需要对搜索进行剪枝。通常情况下，题目给定的限制条件越多，就有越多的细节可以剪枝，因此要善于利用题目中的条件，优化算法，在无法写出正解或者正解就是加了剪枝的搜索的题目中能够争得更高的分数

一般来说，剪枝基本分为这两种：最优性剪枝 与 可行性剪枝

最优性剪枝就是，当前搜索的答案如果已经不比当前最优解要更优，则可以直接退出，因为现在的搜索不会对答案有任何的贡献

可行性剪枝一般用在当现在搜索的状态在之后搜索每次都选取最好状态的情况下都无法满足条件，则也可直接退出。但是，剪枝必须是有效的剪枝，不能通过错误的判断把最优解也剪掉了，这样就起了反作用。 可以这么说，剪枝是一门艺术，如何在搜索中通过有效的剪枝来得到更高的分数， 是我们的一个目标，也是需要重点练习的一门技术

$DFS$是目前学习的算法中最重要的一种，不管是关于树上问题还是图上问题，$DFS$都是不可缺少的工具，许多题目的预处理工作都需要通过搜索来完成

10.2 $BFS$

树、 图的遍历 $BFS$的应用相对而言没有$DFS$那么广泛，但是在图或树的遍历中当$DFS$有爆栈的可能，又不想写手写栈的情况下就可以考虑$BFS$来遍历，稍加处理 可以达到与$DFS$一样的效果。另外在树的遍历中有时候需要统计子树大小之类的信息， 如果用$BFS$的话就必须按照入队顺序从后往前更新子树大小，不能忽略这个顺序。

搜索中的应用 一般情况下$BFS$可以用来求解最优解问题，因为广度优先， 所以每次搜索新的一层就相当于一步。所以当$BFS$最先到达终态时，即得到最优解答案，那么就可以退出搜索了

循环队列 在一些情况下我们可能无法准确确定队列的规模，或者当$BFS$一层搜索会新加入很多元素到队列的时候，我们就需要对队列添加一个循环操作。操作很简单， 当$ℎ𝑒𝑎𝑑$或$𝑡𝑎𝑖𝑙$达到队列的大小时把它们赋为$0$即可。但虽然这样仍有可能会出错，因为当一次搜索扩展太多元素的时候，可能循环后的队列会把还未处理的队列元素覆盖掉，因此我们必须设计好循环队列的大小，保证不会出现覆盖队列的情况。当然使用$STL$中的$queue$与自定义类型变量也是个不错的选择

判重 虽然$DFS$的过程中也会需要判重，但是对$BFS$来说判重更加重要一些，也更有技巧一些。好的判重可以大大降低复杂度，而差判重或无判重甚至有可能让程序无法正常结束。常用的判重方法是数组和$Hash$表，有时题目中会存在有显而易见的一种映射，这时每种状态有且仅有唯一的映射，对于判重来说具有极大的应用，所以在阅读题目的时候需要极其留意。数组判重比较直接，直接把关键字带入下标即可，但当状态比较复杂的时候就不太适用了。这时我们可以设计一个$Hash$函数来计算 当前状态的$Hash$值，在$Hash$表中查找或插入即可。使用$STL$中的$Hash$值$map$，有时会让访问与查询更加便捷当然也会大大提升代码可读性，减少代码长度与实现难度

对于$BFS$经常用来解决棋盘问题，棋盘上的游戏问题等，根据终止状态的不同可以将整个棋盘划分为二进制，由此可以大大提高代码效率

10.3 记忆化搜索

记忆化搜索是典型的空间换时间的算法，因为在$DFS$的时候我们有时会将一种状态重复计算很多次，如果此时我们将每次的最优解状态记录下来，并记录是否访问，那么我们在再次搜索的时候即可直接调用，而无需将已经搜索过的状态再次搜索一遍

记忆化搜索的实现非常简单，将$DFS$的函数类型由$void$改为$int$，再额外用一个数组记录即可。典例有数字三角形等经典问题

10.4 迭代加深搜索$(ID)$

关于迭代加深搜索，感觉实际问题中出现得比较少。十分经典的例题是“埃及分数”，可以称作迭代加深搜索的入门题。

迭代加深搜索主要适用于这样的搜索模型：无法确定搜索的层数，不加控制就会一直向下搜永远不回溯。正是因为这个特点，我们才需要人为地控制搜索的层数，先从最浅层开始搜索，如果没有找到合法解则扩宽一层，这样可以保证每轮搜索可以结束，而适当的搜索剪枝可以使得迭代加深搜索有很高的出解效率。

其实可以在迭代加深搜索上再进行优化，每次扩宽的是最多需要再向下搜索的层数，也就是实际层数可能小于当前扩宽的层数，这样的搜索算法成为$IDA$算法（迭代加深$+A*$)

10.5 $A*$算法

$A*$是一种对于机器人路径规划的网格问题解法

　路径规划是指的是机器人的最优路径规划问题，即依据某个或某些优化准则（如工作代价最小、行走路径最短、行走时间最短等），在工作空间中找到一个从起始状态到目标状态能避开障碍物的最优路径。机器人的路径规划应用场景极丰富，最常见如游戏中$NPC$及控制角色的位置移动，百度地图等导航问题，小到家庭扫地机器人、无人机大到各公司正争相开拓的无人驾驶汽车等。

在计算机科学中，$A*$算法作为$Dijkstra$算法的扩展，因其高效性而被广泛应用于寻路及图的遍历，如星际争霸等游戏中就大量使用。在理解算法前，我们需要知道几个概念：

1 搜索区域（ $The\ Searh\ Area$）：图中的搜索区域被划分为了简单的二维数组，数组每个元素对应一个小方格，当然我们也可以将区域等分成是五角星，矩形等，通常将一个单位的中心点称之为搜索区域节点$（Node）$

2 开放列表$(Open\ List)$：我们将路径规划过程中待检测的节点存放于$Open\ List$中，而已检测过的格子则存放于$Close\ List$中

3 父节点$(parent)$：在路径规划中用于回溯的节点，开发时可考虑为双向链表结构中的父结点指针

4 路径排序$（Path\ Sorting）$：具体往哪个节点移动由以下公式确定：$F(n) = G + H$ 。$G$代表的是从初始位置$A$沿着已生成的路径到指定待检测格子的移动开销。$H$指定待测格子到目标节点$B$的估计移动开销

5 启发函数$（Heuristics\ \ Function）$：$H$为启发函数，也被认为是一种试探，由于在找到唯一路径前，我们不确定在前面会出现什么障碍物，因此用了一种计算$H$的算法，具体根据实际场景决定。在我们简化的模型中，$H$采用的是传统的曼哈顿距离$（Manhattan\ \ Distance）$，也就是横纵向走的距离之和

*$A$算法总结：**

1 把起点加入$open\ list$ 。

2 重复如下过程：

　　　　$a.$ 遍历$open\ list$ ，查找$F$值最小的节点，把它作为当前要处理的节点，然后移到$close\ list$中

　　　　$b.$ 对当前方格的 $8$个相邻方格一一进行检查，如果它是不可抵达的或者它在$close\ list$中，忽略它。否则，做如下操作：

　　　　如果它不在$open\ list$中，把它加入$open\ list$，并且把当前方格设置为它的父亲

　　　　 如果它已经在$open\ list$中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更近。如果更近，把它的父亲设置为当前方格，并重新计算它的$G$和$F$值。如果你的$open\ list$是按$F$值排序的话，改变后你可能需要重新排序。

　　　　$c.$ 遇到下面情况停止搜索：

　　　　 把终点加入到了$open\ list$中，此时路径已经找到了，或者

　　　　 查找终点失败，并且$open\ list$是空的，此时没有路径。

3 从终点开始，每个方格沿着父节点移动直至起点，形成路径。

10.6 $Meet\ \ in\ \ the\ \ middle$思想

这种思想一般用于要解决的问题中所给定的$n$不大的情况，但是每一层有很多种可能情况的搜索中。常规做法是直接从第一层开始搜索，假设每一层有$k$种情况那么这样的时间复杂度为$O(k^n)$，一般情况下裸搜索会超时。这个时候$Meet\ \ in\ \ the\ \ middle$思想就有用处了。

$Meet\ \ in\ \ the\ \ middle$思想是把问题的规模分解为一半，进行两次搜索。对前一半进行搜索时，当得到一个最终结果的时候把这个结果存储下来（通常情况下采用$Hash$表来存储）。然后再对后一半进行搜索，搜索到最后把目标结果与当前结果“做差”，把得 到的“差值”在前一半搜索时建立的$Hash$表里查找，若能够找到即为合法。通过这样的 处理，搜索规模减少了一半，时间复杂度也简化为$O(2 \times\ k^\frac{n}{2} )$，相比起原来的搜索，是 一个十分成功的优化

11 倍增

倍增经常用来加速计算，对于某些常数极大的题目来说，将常数进行二级制拆分， 每次增加$2^k$倍，从而避免被卡常，是一种优雅且好用的思想

11.1 快速幂

对于一个求幂的运算显然可得$a^{2p}$$=(a^2)^p$

那么就可以对于指数进行二进制拆分，对于底数使用倍增思想

int fastpower(long long base,int power){
	long long result=1;
	while(power>0){
		if(power&1) result=result*base%k;
		power>>=1;
		base=base*base%k;
	}
	return result%k;
}

11.2 $ST$表

考虑一个区间查询最值问题，当然可以用线段树去维护，但使用线段树时每次的查询时间就达到了$O(log_n)$的复杂度，对于一些$q$较大的题目来说显然是非常不友好的，所以$ST$表就应运而生

对于$ST$表来说，预处理的时间复杂度为$O(n\ \times\ log_V)$。查询复杂度为$O(1)$

$log_V$一般在$20$以内，所以几乎可看成线性，而查询复杂度却降到了$O(1)$这显然是非常有利于$q$极大的情况的

当然$ST$表还有许多精妙的用法，不做具体展开，典例请见$NOI\ 2010$超级钢琴

11.3 矩阵加速

对于一个存在递推式的数列来说可以通过矩阵来加速运算，通过矩阵快速幂大大降低时间复杂度

这里举一个小小的栗子，就用最常见的斐波那契数列为例：

对于斐波那契数列来说有通项公式：$a_n=a_{n-1}+a_{n-2}$

11.3 小总结

对于倍增来说，它并不是一种算法，而是一种利用$K$进制数来加速运算的一种思想，常规的倍增一般选$K$作为$2$，但其实倍增的思想在广义上$K$可取任意值，典例可见例题*能量采集​

对于K次的倍增 普通倍增中，$K=2$；普通根号分治中，$K=\sqrt{M}$

倍增的本质思想是：每次根据已经得到的信息，将考虑的范围扩大一 倍，从而加速操作。

倍增算法主要有两方面的应用：

一、在变化规则相同的情况下加速状态转移

二、加速区间操作

12 树

一颗树是信息学竞赛中最常用，同时也是应用最广泛的一种数据结构，关于树的算法与种类十分繁多，难题与各种防$AK$题都会在基于树上的问题上进行改造，从而构造出极其难以理解，并且难以下手的题目

对于树来说经常进行的操作就是深搜，对于树上问题，经常需要记录的有每个节点的深度与权值，它的父亲结点与儿子节点等系列信息

12.1 二叉搜索树

二叉搜索树是一棵二叉树，这样一棵树可以使用一个链表结构表示，其中每个结点就是一个对象。除了结点中的关键字外，每个结点还包含属性$left$ ， $right$，$ p$，它们分别指向结点的左孩子、右孩子和双亲。如果某个孩子结点和父结点不存在，则相应属性的值为$null$。根结点是树中唯一父结点为$null$的结点

二叉搜索树中的关键字总数以满足二叉搜索树性质的方式来存储：设$x$是二叉搜索树中的一个结点。如果$y$是$x$左子树中的一个结点，那么$y.key\ \le\ x.key $如果$y$是$x$右子树中的一个结点，那么$y.key\ \ge\ x.key$

二叉搜索树在实际应用中较少，重要性质在中序遍历中体现的极为明显，对于这种性质在某些$DP$题中应用极为广泛，典例为加分二叉树

12.2 线段树

线段树$（Segment\ \ Tree）$是一种基于分治思想的二叉树。支持高效的区间更新与查询操作

一、线段树的每个节点都代表一个区间 $[l,r]$

二、线段树的每个非叶子结点都有两个子节点，分别代表左半区间$[l,mid]$和右半区间$[mid+1,r]$，其中$mid=(l+r)\div2$，即下取整。

三、线段树的每个叶子结点都代表一个长度为$1$的区间$[l,l]$。

线段树主要用于处理区间问题，对于与区间有关的问题来说，经常使用线段树来进行优化，如线段树优化建图，括号匹配，以及线段树合并等操作

12.3 树状数组

树状数组$（Binary\ \ Indexed\ \ Trees）$是用来维护序列前缀和的数据结构

树状数组使用数组结构进行存储。

可以通过树状数组，在$O(log_N)$的时间内实现单点更新与区间查询操作。

定义：$lowbit(x)$等于$x$的二进制形式中最右边的$1$所对应的值

例如 二进制数$1011000$的$lowbit$值就等于$1000$

代码：$lowbit = x $ &$ -x$

对于给定的数组$a$，建立一个数组$t$

其中$t[x]$用于保存区间$[x-lowbit(x)+1,x]$中所有数的和

12.3.1 树状数组求逆序对

算法流程：（1）建立一个空的权值树状数组

​ （2）倒序扫描序列$a$

​ （3）对于$a[i]$，查询区间$[1,a[i])$的结果，累加到答案上

​ （4）执行单点更新操作，令$a[i]$的数目$+1$

​ （5）输出答案

注意点：倒序扫描序列，本质上是在维护后缀，对于每个$a[i]$，查询它后面有多少数比它本身小，也就是逆序对个数

12.3.2 树状数组解决$Range\ \ Minimum\ \ Query$($RMQ$问题)

第k小问题，就是对于给定的序列$a$，求解其第$k$小元素的值。很自然的，我们可以想到，直接对序列$a$排序后，取$a[k]$的值，时间复杂度$O(N\ \times\ log_N)$。借助快速排序的思想，我们还能得到一个$O(N)$的算法通过树状数组这一数据结构，可以在$O(log_N)$的时间内解决这一问题

12.4 基环树

每个节点向其它节点连接一条边。即题目给出 了一颗基环外向树。“基环”指这个图中只有一个环，并以这个环为“基础”。“外向树” 指这个基环上的每一个点，都可以作为一个根节点向环外延伸出一棵树，构造出一个优美的图形。实际上可以看作在一颗普通的树上增加了一条边，形成了一个环

基环内向树
基环外向树

破环成链 对于基环外向树来说，一个比较常见的做法就是记录基环上一条边的信息， 然后把这条边去掉，则原本的环变成了一条链，可以在链上维护一些信息，即“破环成链”。虽然是断掉基环树的上的一条边，使得整个环成为了一条“链”，但如果把链的“摆放方向”改变一下，就会发现断去环上一条链后整个基环树就成为了一棵树，这样子就可以对新的树进行一些基本的操作来达到题目的要求。

外向树中的信息则可通过其它算法求得，再在链上统计结果，需要时把去掉的边加进来即可

基环树上的DP 如果根据题意需要在基环树上进行$DP$，那么可以把基环树上的$DP$分为两部分：树上$DP$和环上$DP$。树上$DP$与一般的树形$DP$没有太大区别，只是根节点是环上的一个点。而环上$DP$也可以理解为把各个根节点最后的$DP$值合并起来更新答案。 而树上$DP$一般采用的方式为“自根向下”和“自底向上”，“自底向上”一般指的是依据数的拓补序来$DP$。基环树上$DP$比较难的就是环上各个点的合并方法，必须要首先把环上的点记录下来，由于事先去除了一条边，因此还需要维护两个方向的值，在处理的时候有一点麻烦，必须分析清楚

12.5 $LCA$(最近公共祖先)

用来求$LCA$的方法，我到目前为止所学会的有两种，就是上述的倍增和树链剖分的做法。

倍增做法 首先把被询问的两个点之间较深的点跳到另一个点的高度上，判断该两个点是否为同一个点，若是则返回。否则两个点同时一起上跳，最后返回他们的父节点

树链剖分做法 该做法主要是判断两个点所在重链的顶端节点的深度，把顶端节点较深 的点跳到该顶端节点的父节点，不断操作下去，最后两个节点一定处于同一条重链上， 此时较浅的节点即为被询问的两个点的$LCA$

13 图论

图论是数据结构中一门最为重要的分支，图论之复杂，之繁多，之困难，超出一般人的想象，对于这段时间来说，对于图论的各种分支，各种结论有了不小得补充认识。同时，图论也是平常考试时考察的重点，而许多树的情况也可以转化为图来研究

13.1 最小生成树

对于一张图常规进行的操作有求一张图的最小生成树，现有的算法有$Kruskal$算法与$Prim$算法

13.1.1 $Kruskal$

首先有一个引理：一张图的最小生成树中的一条边一定是能到的该点距离的最短距离

由此我们可以贪心的想，每次选取一条现有最短边将其加入已选的集合$V$中，为判断有无环出现的情况可以使用并查集维护$E$集合中的点集，这样的话时间复杂度主要在排序上，为$O(V\ \times\ log_V)$

13.1.2 $Prim$

同样的由以上引理可得，若我们只维护一个已选点集$U$，每次选出一条距离这个点集最近的点，那么这个算法就是绝对正确的，并且不会得到环

如果采用邻接矩阵存储图，那么复杂度大概在$O(n^2)$左右，如果和$Dijkstra$一样采用堆优化，那么复杂度就是稳定的$O(n\ \times\ log_n)$与边的数目无关

13.1.3 小结

对于一张稠密图来说个人更推荐使用$Prim$算法而不是$Kruskal$算法，因为$Prim$算法与点无关的特性决定了它在稠密图中优于$Kruskal$先天条件

但是$Kruskal$在各类关于最小生成树中出现概率更为频繁，主要是由于它的好写，因为对于一些最小生成树来说，$Kruskal$的算法过程对于解决题目有着巨大的启发式作用。典例请见长郡今年的$NOIP$模拟赛

13.2 最短路径问题

最短路与最小生成树一样是考试时解决图论问题的重要手段

13.2.1 $Dijkstra$

$Dijkstra$本质上与$Prim$算法相似，都是维护一个已选点集将整个集合看做一个点，求起点的单源最短路径。本质上维护的是一个将树合并到森林中的过程，所以复杂度与$Prim$一样

当数据结构为邻接矩阵时，时间复杂度为$O(N^2)$，使用二元组$pair$为关键字的$priority_queue$优化就是稳定的$O(N\ \times\ log_N)$的复杂度。当然如果你足够神犇，会使用斐波那契堆效率会更高

13.2.2 $BellMan-Ford$

$BellMan-Ford$也是一个贪心的思想，对于当前节点$v$，已经记录有一个当前的最短距离，通过边集数组找到一条由节点$u$到现在节点$ v$的路径，将$dis[v]$与$dis[u]+w$比较，以此来更新$dis$数组

分析算法过程可知最劣情况下会将一个点枚举到$n-1$次所以时间复杂度为$O(N^2)$

13.2.3 $SPFA$

$BellMan-Ford$的队列优化版

每次选取队列中更新过的节点去更新未更新节点，因为未更新的节点一定会由更新过的节点转移而来，由此还可根据进队次数判断负环，一般来说时间复杂度为$O(\varphi\ \times\ V)$$\ \ \ \varphi$是个反阿克曼函数，一般为$4$左右

13.2.4 $Floyd$

以极其简短的代码闻名于世

但其实思想同样很简单，在两个点之间每次固定规定一个中继点(即必须经过此点)从而求出全源最短路（即任意两点之间的最短路）

只要对$Floyd$的思想理解的足够透彻后就可以轻易地知道它的时间复杂度为$O(N^3)$

13.2.5 $Johnson$

对于全源最短路问题，可以考虑通过$n$次$Dijkstra$来求出，这就是$Johnson$算法的主要思想

但$Johnson$算法最大的用处是为了处理无负环的负权最短路

对于一张存在负权的图来说，很自然的会想到将负权加成一个正数。此处引入一个概念：势能

对于一条从$s$到$t$的路径$s\ \to\ p_1\ \to\ p_2\ \to\ p_3\ \to\dots\ p_k\ \to\ t$其长度为：

$$(W(s,p_1)+h_s-h_{p_1})+(W(p_1,p_2)+h_{p_1}-h_{p_2})\ \dots\ (W(p_k,t)+h_{p_k}-h_{t})$$

化简后得到：$$W(s,p_1)+W(p_1,p_2)+\ \dots\ W(p_k,t)+h_s-h_t$$

那么此时$h_s-h_t$就是$(s,t)$的势能

新建一个零号节点，利用$SPFA$求出$0$号节点到各点的最短路，然后即可求出点与点之间的势能，再在为正权的图上跑多源$Dijkstra$即可

13.2.6 $D´Esopo-Pape$

这个算法据说会比$Dijkstra$更优

此算法维护三个点集：

1 $M_0$-已经计算出距离的点（无论是否为最短距离）

2 $M_1$-正在计算距离的点（可理解为准备被计算的点）

3 $M_2$- 未被计算距离的点

每次从$M_1$取一个点$u$将$u$存入$M_0$然后我们遍历从$u$出发的所有边。设另一端是点$v$，权值为$w$

如果$v\ \in\ M_2$，将$v$插入$M_1$队尾，并更新$d_v$：$d_v\ \gets\ d_u+w$

如果$v\ \in\ M1$，那我们就更新$d_v$：$d_v\ =\ \min\ (d_v,d_u+w)$

如果$v\ \in\ M_0$，并且$d_v$可以被改进到：$d_v\ >d_u+w$，那么我们就更新$d_v$，并将$v$插入到$M_1$的队首

struct Edge {
  int to, w,nxt;
};
int n;
const int INF = 1e9;
void shortest_paths(int s) {
  memset(dis,0x3f,sizeof(dis));
  dis[s] = 0;
  FOR(i,1,n) m[i]=2;
  deque<int> q;
  q.push_back(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop_front();
    m[u] = 0;
    REP(u) {
      if (dis[e.to] > dis[u] + e.w) {
        dis[e.to] = dis[u] + e.w;
        if (m[e.to] == 2) {
          m[e.to] = 1;
          q.push_back(e.to);
        } else if (m[e.to] == 0) {
          m[e.to] = 1;
          q.push_front(e.to);
        }
      }
    }
  }
}

13.3 曼哈顿最小生成树

可以得出这样一个结论：以一个点为原点建立直角坐标系，在每$45$度内只会向距离该点最近的一个点连边。

此处不证明，过程自行去看博客证明

根据对原点对称，我们分为四组：$R_1$与$R_5$，$R_2$与$R_6$，$R_3$与$R_7$，$R_4$与$R_8$。对于$R_1$和$R_5$内的点，假设当前点为$O$，我们在其位置上建立直角坐标系，那么对于其$R_1$方向内的点$A$，$B$，我们没有必要连接$O$、$B$，只需连接$O$、$A$

因此，对于所有$y_i-y_o\ >\ x_i-x_o$，$x_i\ >\ x_o$即$y_i-x_i\ >\ y_o-x_o$（即$0$），$x_i\ >\ x_o$的点$i$，找到最小的$x_i+y_i$那个点，将其与点$O$相连（记录下边）。这样，我们对点按照$x$为第一关键字升序、$y$为第二关键字升序，然后用树状数组维护区间最小值$（x_i+y_i）$，用$y_i-x_i$离散化后的编号作为树状数组的下标，从最后一个点起更新树状数组

对于其余区域，我们计算完$R_1$与$R_5$后，先让所有点关于$y=x$对称，则$R_2$，$R_6$内的点转到$R_1$，$R_5$区域，用对待原$R_1$，$R_5$内的点同样对待它们。因此，类似地，我们通过$3$次旋转，$4$次更新树状数组和连边，就得到所有有效的边，接下来，利用最小生成树原理，找到第$n-1-(k-1)$次添加进生成树的边的边权即可

13.4 最短哈密顿路径

事实上这个东西，是个状压$DP$，但把它放在图论里是因为它是个图上的$NP$完全问题

先给出一些定义：

通过图中所有顶点一次且仅一次的通路称为哈密顿通路

通过图中所有顶点一次且仅一次的回路称为哈密顿回路

具有哈密顿回路的图称为哈密顿图

具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图

哈密顿路径的定义：是每个顶点必须经过且仅能经过一次，因此，可用当前是否经过了这些点和当前在哪个点来表示出一个状态，则一共有 $n\ \times\ 2^n$ 个状态。考虑转移方式，对于在 $j$ 这个点的情况来说，可以从以下与 $j$ 相邻的节点 $k$ 转移来，$k$ 必须满足在当前状态已经走到。因此，时间复杂度为 $O(n^2\ \times\ 2^n)$

$dp[i][S]=min\ \ (dp[k][S′])\ \ +dis[i][k]\ \ \ $$\begin{Bmatrix} k∈[1,n]，S′\ \subset\ S\ \end{Bmatrix}$

从中可以看出$ i$ 的决策是不具有阶段性的，即：$i$ 并不是从小到大进行的，而对于集合来说是从小到大进行转移的，因此应该以走过的点的集合作为阶段，即：集合应该是循环的第一层

上板子：

#include <bits/stdc++.h>
using namespace std;

int dp[1<<20][20];
int n,G[20][20];

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%d",&G[i][j]);
	memset(dp,0x3f,sizeof(dp));
	dp[1][0]=0;
	for(int i=1;i<1<<n;i++)
		for(int j=0;j<n;j++)if(i>>j&1)
			for(int k=0;k<n;k++)if((i^1<<j)>>k&1)
				dp[i][j]=min(dp[i][j],dp[i^1<<j][k]+G[k][j]);
	printf("%d\n",dp[(1<<n)-1][n-1]);
	return 0;
}

13.4 最小树形图

有向图上的最小生成树$（Directed\ \ Minimum\ \ Spanning\ \ Tree）$称为最小树形图。

常用的算法是朱刘算法（也称 $Edmonds$ 算法），可以在$O(n\ \times\ m)$时间内解决最小树形图问题。

​ ——来自$OI-wiki$

简单来说，朱刘算法分为四个过程：

1 求最短弧集合 E

2 判断集合 E 中有没有有向环，如果有转步骤 3，否则转 4

3 收缩点，把有向环收缩成一个点，并且对图重新构建，包括边权值的改变和点的处理，之后再转步骤 1

4 展开收缩点，求得最小树形图

此处省略实现

13.5 线段树优化建图

对于一个区间对于一个点连边和一个点向区间连边，此时可以非常自然的想到线段树来优化

对于出树，将每个父节点向它的儿子节点连边，对于入树，将每个儿子节点向它的父亲节点连边，然后直接跑多源$Dijkstra$即可

详细样例请见：

“小车正穿行在落基山脉蜿蜒曲折的盘山公路上”

“克里斯朵夫·李维静静地望着窗外，发现每当车子即将行驶到无路的关头，路边都会出现一块交通指示 牌：“前方转弯！”或“注意！急转弯”。

“而拐过每一道弯之后，前方照例又是一片柳暗花明、豁然开朗。”

“山路弯弯、峰回路转，前方转弯”几个大字一次次地冲击着他的眼球，也渐渐叩开了他的心扉：原来， 不是路已到了尽头，而是该转弯了。”

“路在脚下，更在心中，心随路转，心路常宽。”

“学会转弯也是人生的智慧，因为挫折往往是转折，危机同时是转机”。

13.6 二分图

二分图是联赛考试中的一个难点，对于二分图问题来说，重点是要看出它是一个二分图，二分图经常用于解决棋盘问题，对于棋盘进行奇偶性染色是一种常见的方式

13.6.1 二分图最大匹配

优先推荐匈牙利······

算法流程如图所示

嗯·····完结撒花！！！

13.6.2 二分图小总结

对于二分图，求得最多的是最大匹配问题

当然还有几个推论：

最大匹配=最小点覆盖

最大独立集=总点数-最大匹配

13.7 网络流

网络流是一个神奇的东西，是一个容易退役又容易得高分的东西······

嗯！就是这样

此处并不涉及最小割最大流等定理证明，只介绍一些基础

但是最大流等于最小割这个得知道

13.7.1 $Ford-Fulkerson$

FF算法的核心在于找增广路

增广路，是从源点到汇点的路径，其上所有边的残余容量均大于0。FF算法就是不断寻找增广路，直到找不到为止

为了保证这个算法的正确性，我们引入反向边。在建边的同时，在反方向建一条边权为0的边

其实可以把反向边理解成一种撤销，走反向边就意味着撤回上次流经正向边的若干流量，这也合理解释了为什么扣除正向边容量时要给反向边加上相应的容量：反向边的容量意味着可以撤回的量。

加入了反向边这种反悔机制后，我们就可以保证，当找不到增广路的时候，流到汇点的流量就是最大流。

时间复杂度为$O(m\ \times\ f)$，$m$为边数，$f$为流量

int n, m, s, t; // s是源点，t是汇点
bool vis[MAXN];
int dfs(int p = s, int flow = INF)
{
    if (p == t)
        return flow; // 到达终点，返回这条增广路的流量
    vis[p] = true;
    for (int eg = head[p]; eg; eg = edges[eg].next)
    {
        int to = edges[eg].to, vol = edges[eg].w, c;
        // 返回的条件是残余容量大于0、未访问过该点且接下来可以达到终点（递归地实现）
        // 传递下去的流量是边的容量与当前流量中的较小值
        if (vol > 0 && !vis[to] && (c = dfs(to, min(vol, flow))) != -1)
        {
            edges[eg].w -= c;
            edges[eg ^ 1].w += c;
            // 这是链式前向星取反向边的一种简易的方法
            // 建图时要把cnt置为1，且要保证反向边紧接着正向边建立
            return c;
        }
    }
    return -1; // 无法到达终点
}
inline int FF()
{
    int ans = 0, c;
    while ((c = dfs()) != -1)
    {
        memset(vis, 0, sizeof(vis));
        ans += c;
    }
    return ans;
}

13.7.2 $Edmond-Karp$

其实，EK算法就是BFS实现的FF算法···········

BFS可以保证每次找到的都是最短的增广路。它的复杂度上限是 $O(n\ \times\ m^2)$，至少与流的大小无关了

int n, m, s, t, last[MAXN], flow[MAXN];
inline int bfs()
{
    memset(last, -1, sizeof(last));
    queue<int> q;
    q.push(s);
    flow[s] = INF;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        if (p == t) // 到达汇点，结束搜索
            break;
        for (int eg = head[p]; eg; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && last[to] == -1) // 如果残余容量大于0且未访问过（所以last保持在-1）
            {
                last[to] = eg;
                flow[to] = min(flow[p], vol);
                q.push(to);
            }
        }
    }
    return last[t] != -1;
}
inline int EK()
{
    int maxflow = 0;
    while (bfs())
    {
        maxflow += flow[t];
        for (int i = t; i != s; i = edges[last[i] ^ 1].to) // 从汇点原路返回更新残余容量
        {
            edges[last[i]].w -= flow[t];
            edges[last[i] ^ 1].w += flow[t];
        }
    }
    return maxflow;
}

13.7.3 $Dinic$

最常用的网络流算法是$Dinic$算法。作为$FF/EK$算法的优化，它选择了先用$BFS$分层，再用$DFS$寻找。它的时间复杂度上界是 $O(n^2\ \times\ m)$。所谓分层，其实就是预处理出源点到每个点的距离（注意每次循环都要预处理一次，因为有些边可能容量变为$0$不能再走）。我们只往层数高的方向增广，可以保证不走回头路也不绕圈子。

我们可以使用多路增广节省很多花在重复路线上的时间：更具组合意义的等式：$n^m\ =\ \sum\limits_{k=0}^m\begin{Bmatrix}{m}\{k}\end{Bmatrix}\ \times\ n^{\underline k}$在某点$DFS$找到一条增广路后，如果还剩下多余的流量未用，继续在该点$DFS$尝试找到更多增广路。

此外还有当前弧优化。因为在$Dinic$算法中，一条边增广一次后就不会再次增广了，所以下次增广时不需要再考虑这条边。我们把$head$数组复制一份，但不断更新增广的起点

此算法在二分图中是$O(m\ \times\ \sqrt{n})$优于匈牙利算法

int n, m, s, t, lv[MAXN], cur[MAXN]; // lv是每个点的层数，cur用于当前弧优化标记增广起点
inline bool bfs() // BFS分层
{
    memset(lv, -1, sizeof(lv));
    lv[s] = 0;
    memcpy(cur, head, sizeof(head)); // 当前弧优化初始化
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = head[p]; eg; eg = edges[eg].next)
        {
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && lv[to] == -1)
                lv[to] = lv[p] + 1, q.push(to);
        }
    }
    return lv[t] != -1; // 如果汇点未访问过说明已经无法达到汇点，此时返回false
}
int dfs(int p = s, int flow = INF)
{
    if (p == t)
        return flow;
    int rmn = flow; // 剩余的流量
    for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) // 如果已经没有剩余流量则退出
    {
        cur[p] = eg; // 当前弧优化，更新当前弧
        int to = edges[eg].to, vol = edges[eg].w;
        if (vol > 0 && lv[to] == lv[p] + 1) // 往层数高的方向增广
        {
            int c = dfs(to, min(vol, rmn)); // 尽可能多地传递流量
            rmn -= c; // 剩余流量减少
            edges[eg].w -= c; // 更新残余容量
            edges[eg ^ 1].w += c; // 再次提醒，链式前向星的cnt需要初始化为1（或-1）才能这样求反向边
        }
    }
    return flow - rmn; // 返回传递出去的流量的大小
}
inline int dinic()
{
    int ans = 0;
    while (bfs())
        ans += dfs();
    return ans;
}

14 数论

数学与信息学竞赛结合紧密，尤其是组合数学，概率学，统计学，初等数论与具体数学，此处只解释一些已经涉及并且考察过的一些数学方面的东西

14.1 卢卡斯定理

嗯······，前几天$Yukikaze$在他的$NOIP$模拟题$T3$中涉及到的东西

只给出一些结论性的东西：

$C_{m}^{n}%P=C_{\frac{m}{p}}^{\frac{n}{p}}\ \times\ C_{m%p}^{n%p}%P$

卢卡斯定理，就是用来计算很大的组合数的

证明自己滚去看博客

证明：

首先证明：$(1+x)^p\ \equiv\ (1+x)\ \equiv\ 1+x^p$

由组合数恒等式得：$C_{p}^{j}=\frac{p}{j}\ \times\ C_{p-1}^{j-1}\ \equiv\ (0\ mod\ \ P)$

再由二项式定理得：$(x+1)^p=\ \sum\limits_{i=0}^{p}\ C_p^{i}x^i$

因为除第一项和最后一项外，其他组合数在$mod\ \ p$的意义下为零：

由此可得：$(1+x)^p\ \ \equiv\ (C_{p}^0\ \times\ x^0+C_p^p\ \times\ x^p)(mod\ \ p)$

嗯，证毕，针不戳！！！

14.2 斯特林数

斯特林数是组合数学中的一个重要内容，有许多有用的性质。它由十八世纪的苏格兰数学家$James \ \ Stirling$首先发现并说明了它们的重要性

斯特林数主要处理的是把N个不同的元素分成k个集合或环的个数问题，现在我们说的斯特林数可以指两类数，分为第一类斯特林数和第二类斯特林数，其中第一类斯特林数还分成有符号和无符号两种

14.2.1 第一类斯特林数

定义：将 $n $个不同的元素全部放入 $m $个环中,不允许有空环出现,求方案数，即求将$i$个相同的小球放入$j$个不同的盒子里的方案数，记作：$S(i,j)$

递推式为：$S(i,j)=(i-1)\ \times\ S(i-1,j)+S(i-1,j-1)$

证明：

我们在$i-1$的时候可能有两种状态：

1 已有$j$个环， 从某个元素数$>1$的环中加入一个元素，转移到$j$个环的状态，环有顺序，共有$i-1$个元素，所以可以插入到任意一个元素的左边，因此有$i-1$个种可能

2 已有$j-1$个环，直接把这个元素作为一个新环，转移到$j$个环的状态，因为只加入一个环，所以没有其他状态

根据状态1得到$(i-1)\ \times\ S(i-1,j)$；根据状态2得到$S(i-1,j-1)$，合起来就是第一类斯特林数公式：$$S(i,j)=(i-1)\ \times\ S(i-1,j)+S1(i-1,j-1)$$

边界条件：$S(i,0)=0，i\ \ge\ 1$

​ $S(i,i)=1，i\ \ge\ 0$

与阶乘的关系：$\ \sum\limits_{i=0}^{n}S(n,i)=n！\ $

与上升幂的关系：$m^{\bar{n}}=\ \sum\limits_{i=0}^{n}S(n,i)\ \times\ m^i$

14.2.2 第二类斯特林数

定义：将$n$个不同的元素放入$m$个相同的盒子里的方案数，记作：$S(n,m)$

递推式为：$S(n,m)\ =\ m\ \times\ S(n-1,m)\ +\ S(n-1,m-1)$

证明：

在$n-1$的时候可能有两种状态：

1.已有$m$个集合，因为不考虑顺序，可以插入$m$个集合中任意的集合，所以有$m$种可能

2.已有$m-1$个集合，直接把这个元素作为一个新集合，没有其它状态

根据状态1得到$m\ \times\ S(n-1,m)$；根据状态2得到$S(n-1,m-1)$，合起来就是第二类斯特林数公式：$S(n,m)=m\ \times\ S(n-1,m)+S(n-1,m-1)$

边界条件：$S(n,n)=1,(n>=0)$

​ $S(n,0)=0,(n>0)$

容斥原理：$S(n,m)=\frac1m!\ \sum\limits_{k=0}^m(−1)^k\ \times\ C(m,k)\ \times\ (m−k)^n$

性质：$n^k\ =\ \sum\limits_{i=0}^k\ S(k,i)\ \times\ i!\ \times\ C(n,i)$

14.3 乘法逆元

逆元在一些数论题中，在$mod\ \ P$意义下求组合数的一些题中经常使用的一种技巧，对于求逆元的题目，掌握一些线性算法是非常有必要的

逆元简介：如果一个线性同余方程$ax\ \equiv\ 1(mod)\ \ b$，则$x$称为$a\ \ mod\ \ b$的逆元，记作：$a^{-1}$

14.3.1 费马小定理

费马小定理内容：若$p$为素数，$gcd(a,p)=1$，则$a^{p-1}\ \equiv\ \ 1\ \ mod\ p$

这个不是重点，重点是费马小定理求逆元，也是分数下求逆元的方法

证明：

$\because ax\ \equiv\ 1(mod\ \ b)$

又$\because a^{b-1}\ \equiv\ 1(mod\ \ b)$

$\therefore ax\ \ \equiv\ \ a^{b-1}(mod\ \ b)$，$x\ \equiv\ a^{b-2}(mod\ \ b)$

由此我们可以使用快速幂的方法求得$a$的逆元，时间复杂度为$O(log_P)$

14.3.2 线性求逆元

线性求连续$n$个数的逆元：

仅给出公式：$i^{-1}=\begin{cases} 1\ \ (i=1)\ -\lfloor \frac{p}{i} \rfloor\ (p\ mod\ \ i)^{-1}\ \end{cases} $

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

线性求不连续$n$个数的逆元：

记：$S_i=\ \prod\limits_{k=1}^{i}a_i$

​ $SV_n=S_n^{-1}$

则：$SV_n\ \times\ a_n=SV_{n-1}$

所以：$a_i^{-1}=S_{i-1}\ \ \times\ \ SV_i$

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
// 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

线性求阶乘逆元：

inv[maxn]=mod_pow(fac[maxn],mod-2);
for(ll i=maxn-1;i>=0;i--)
    inv[i]=(inv[i+1]*(i+1))%mod;

15 总结与反思

在三周的集训里对于更多的算法理解更加的深刻了，在考场上的代码能力得到了极大的提升，对于一些题目的暴力做法有了深刻的体会，逐渐理解了考试时对拍的意义

不足：

对于一些思维题和数学题始终沉不下心来思考，在考场上无法冷静地推出一些公式和一些定理，在数学方面的掌握远远不够熟练，即使明白了大致做法，我也要因为细节问题而思考很长 一段时间，导致把时间消耗掉了也许就没有剩余时间去完成其它的题目。平时考试之后喜欢看着解题报告和标程去改题，这是一个非常不好的习惯。希望在第二阶段即联赛之后的学习中努力提高自己的思考能力，成为写题解写标程的人

很多题目中存在一些很容易就发现并能够证明的小结论，只要利用起来就可以帮助 自己获得更高的分数。或者是一些子任务，对于题目中的一些数据范围对正解有提示作用的小细节不够关注，从而导致考场爆零这些尴尬的事情，对于题目的分析不够透彻，理解不够清楚

感想：

$Everything\ \ that\ \ does\ \ not\ \ kill\ \ me\ \ makes\ \ me\ \ stronger$

给自己的理想与抱负多一些时间和等待

​ ——$2020$年$12$月$3$日