早上比赛

省流，30分，没爆零

下午改题

T1 最短路径

看到这个题目，我真把它当成一道数学题来解了，我先算出了0点和n-1点的解析式，然后把中间点坐标进去，看能不能形成一个凸包，然后猜结论，每次沿凸包的边走是最优的

但是这就没考虑到题目要求的中间路径有必经点的限制

这题正解是dp

LINK

注：这篇题解的点是1起下标，不妨看作是从0点开始的两条路径，一条经过b1，一条经过b2，求两条路径之和最小，类似与传递纸条那题

下次思考脑洞还是要打开一点

Code:

T2 Vani和Cl2捉迷藏

这题看到DAG，我就想着是不是BFS后看一下同一层顶点数的最大数量就是答案(手模样例所得的猜测，但WA了，能骗到25也是奇迹)

这题正解竟然是闭包传递+二分图最大匹配！

题解

连闭包都不知道是什么的我开始看起了《算法竞赛》，大概懂了，传递闭包就是一种连通性的传递，大概就是如果a->b，b->c那么有a->c

可以使用Floyd算法做闭包传递，《算法竞赛》里给出了用bitset一个优化后的Floyd传递闭包的做法

大致如下：

然后还需要一些前置知识
二分图最大匹配+最小路径覆盖

二分图最大匹配

模板题
求二分图最大匹配有两种算法，一种可以用网络流，另一种使用匈牙利算法
我们学习第二种

Code：

然后我们就可以做原题了

晚自习

稍微学习了一下LaTeX插入数学公式
Link

然后出了一道水题

看一下数据规模哈

不会真的有人以为要高精度吧
正解：边读入边取模

从哪学的呢？LINK

第一次出题，试试水，还是很有意思的(当然现在才还不到7点，所以乱搞)

达成成就：硬控zmx 40min

Manacher算法

下午讲题的时候提到的，是一种用于求解一个字符串中最长回文子串长度的算法，又称作“马拉车”算法

模板题
讲解

Code：

最后吐槽一下，虽然现在博客支持图片的复制粘贴，但画质太糊了，下次还是上传图片吧

今天博客水一点(虽然每天都那么水)，但还是要say goodbye了

byebye