CF487E Tourists
闲扯这道题也是比较套路的，在之前[APIO2018] Duathlon 铁人两项的基础上，我们可以比较快的找到思路。
题面CF487E Tourists
Solution由于是求任意两点间的简单路径的问题，我们考虑建出原图的圆方树。
在铁人两项这道题里面，我们用到了一个结论，根据这个结论，我们可以知
...
P4630 [APIO2018] Duathlon 铁人两项
发表于
闲扯这是一道圆方树好题，只要注意到这道题的性质，就可以轻松做出。
题面P4630 [APIO2018] Duathlon 铁人两项
Solution首先，我们需要注意到一个很关键的性质：在一个点双连通分量中，任意两个点 $u,v$ ，它们之间的简单路径至少有一条通过点 $w$ 。其中 $w$ 是该点
...
P4606 [SDOI2018]战略游戏
发表于
闲扯1234圆方树上圆方果，圆方树下你和我。圆方树前建虚树，欢乐多又多
题面P4606 [SDOI2018]战略游戏
Solution这个题的题意很明显。
给出一个连通图，每次选择几个点作为关键点，问有几个除关键点之外的点，满足将该点及其周围的边去掉后，存在两个关键点 $u,v$ 不再连通。
我们有
...
P4459 [BJOI2018]双人猜数游戏
发表于
闲扯双人猜谜游戏？？
题面P4459 [BJOI2018]双人猜数游戏
Solution我们先康康 $Alice$ 和 $Bob$ 这两个神仙是怎么做到说着说着就知道答案是什么的。
大概思路就是每个人根据之前那个人的回答，在当前的答案集合中，排除掉一些不合法的情况，直到只剩下一个合法答案。
我们设
...
P4457 [BJOI2018]治疗之雨
发表于
闲扯据说这是一个套路题，果然我还是太嫩了呀。
题面P4457 [BJOI2018]治疗之雨
Solution我们设 $E(i)$ 表示当前剩余生命值为 $i$ 时，英雄死亡的剩余步数，其中 $E(0)=0$ 。
我们将每一个 $E(i)$ 看做一个点，将它们之间的转移看做一条有向边，那么我们就可以得
...
P4458 [BJOI2018]链上二次求和
发表于
闲扯不愧是一道省选题，感觉做着还是很有难度的。
题面P4458 [BJOI2018]链上二次求和
Solution我们先把题意简化出来。
给出一序列，有以下两个操作：
给区间 $[l,r]$ 内的每一个数加上 $d$ 。
询问长度在 $[l,r]$ 之间的连续子序列的权值和。
设 $sum_k=
...
Manacher 算法总结
发表于
$Manacher$ 算法总结今天学习了一下这个算法，做了几道题稍微找到了点感觉，过来写一下学习记录。
$Manacher$ 算法并不难理解，就是利用回文串对称的性质，将我们求解回文串的时间复杂度降至 $O(n)$ 。
这里总结一下几个性质和需要注意的点位。
性质
一个串中，本质不同的回文串最多有
...
P3311 [SDOI2014]数数
发表于
闲扯这道题感觉很有价值，练习了 $AC$ 自动机上的 $DP$ 的同时，顺便加深一下对数位 $DP$ 的理解。
题面P3311 [SDOI2014]数数
Solution看到不能包含某个子串，我们先套路的建出 $AC$ 自动机，顺便处理出那些节点是不能选取的（会构成非法子串）。
然后问题就有些讲究了
...
P2536 [AHOI2005]病毒检测
发表于
闲扯还是没有学到 $AC$ 自动机的精髓，不过倒是学到了一种不错的解决通配符的 $dp$ 方法（不过是单次 $O(n^2)$ 的）。
题面P2536 [AHOI2005]病毒检测
Solution我们可以设计一个 $dp_{i,j}$ 表示原串匹配到了 $i$ ，模式串匹配到了 $j$ 是否可行。
...
CSP-S 2019 游记
发表于
CSP-S 2019 游记考完已经过了一周多了，终于还是滚来写游记了。
趁着成绩还没出来，心态还比较稳的时候，简单记录一下。
Day -inf整天在机房里刷题，划水，按时出去打球，生活过得轻松自在。
Day 0中午 $2:30$ 从学校出发，在车上看了 $40$ 分钟的番，但是网太差了， 选择睡觉。
...