2020 4.8

计蒜客 – 蒜头君的银行卡

这是算尽天下系列的第10篇文章,以“计蒜客”的“蒜头君的银行卡”一题为例,分享了如何使用 SPFA 算法进行差分约束系统的求解,可以加深对 SPFA 的理解,并了解其广泛而强大的功能,对理解单源最短路有非常好的帮助。... 1065 2
2020 4.7

计蒜客 – 闯关游戏

算尽天下系列的第 9 期文章,分享一道 SPFA 的经典算法题——“计蒜客”的“闯关游戏”。SPFA 是是 Bellman-ford 算法的队列优化,在代码形式上接近于 BFS,是一个在实践中非常高效的单源最短路算法。... 1037 0
2020 3.20

计蒜客 – 情报加密

蒜头君的情报加密是想要我们求出对于一个给定的字符串,至少修改多少次可以使得该字符串不出现任何一个字典中的子串。使用 AC 自动机进行动态规划即可求解。... 1092 0
2020 3.19

计蒜客 – 蒜厂工作手册

计蒜客的蒜厂工作手册,又是一道使用KMP算法、AC自动机来求解字符串出现次数的题目。... 1066 1
2020 3.18

计蒜客 – 猴子打字

计蒜客的猴子打字是一道 AC 自动机的模板题,直接套用模板就好了。AC 自动机算法主要依靠构造一个有限状态机(类似于在一个 Trie 树中添加失配指针)来实现。... 1138 0
2020 3.17

计蒜客 – 新年礼物

计蒜客的新年礼物是一道字符串的题目,使用预处理的KMP算法,加上前缀树(字典树)即可求解... 1052 0
2020 3.16

计蒜客 – 糟糕的Bug

计蒜客的糟糕的BUG是一题字典树(前缀树)的模板题,直接套用字典树(前缀树)的模板即可解决... 1058 0
2020 3.16

计蒜客 – 匹配格式

格式匹配是一道KMP的经典算法题,需要用到拓展KMP的知识,并以一种合理的方法枚举可能出现的答案并完成计算... 1034 0
2020 3.16

计蒜客 – 旋转数字

计蒜客的旋转数字这道题是一道利用拓展 KMP 算法的好题目。主要思想是利用字符串的比较来实现大数的大小比较。... 1054 0
2020 3.15

计蒜客 – 首尾相接

计蒜客的首尾相接是一道有关字符串的经典算法题,这题用 KMP 或者拓展 KMP 都能做。... 1045 0