很久没更新BLOG了，甚至想接着发出咕咕咕的叫声。咳咳咳，这些都不重要!最近学习了一下AC自动机，发现其实远没有想象中的那么难，下面就让这篇BLOG教会你AC自动机吧！ AC自动机的来历 首先，我要说明！AC自动机并不是能自动AC的程序【刚开始天真的我也觉得学了AC自动机就无敌了QwQ】！！！ AC自动机之所以叫AC自动机，是因为这个算法原名叫Aho-Corasick automaton...
感觉最近学的东西有点杂，最近复习了一下之前学习的匈牙利算法，突然发现，匈牙利算法解决的二分图问题竟然不只有二分图最大匹配问题！这篇Blog，我就来讲解一下匈牙利算法所解决的常见的四种模型吧！ 什么是二分图 就是对于一个图中的所有点，都可以分类两个到集合X和Y，使得所有的边关联的两个顶点，恰好一个属于集合X，另一个属于集合Y。换句话说，就是集合X中任意两点间没有连边，集合Y中任意两点间也没...
最近准备总结一下常用的字符串算法，今天就让我们从最经典的回文串算法——Manacher开始吧！ 什么是回文串 “回文串”，就字面而言，就是是一个正读和反读都一样的字符串。比如“level”就是一个回文串，但是“love”就不是一个回文串。 那么如何求解回文串呢？朴素的来想，我们只需要枚举原序列中的点k，接着从k点向左右拓展直到拓展到的左端和右端字符不一样；这样操作就可以得到一个O(n^...
GDOI Cu滚出了好难受啊QwQ。今天早上目送完参加Day3的大佬后，就去听了中大严紫熙的《网络流的沧海一粟》，收获良多。现在我们就来简单介绍一下简单的网络流算法和一些推论和经典技巧吧！ 什么是网络流问题 我们最常见的问题是最大流问题： 问题表述：给定一幅图（n个结点，m条边），每一条边有一个容量，现在需要将一些物品从结点s（称为源点）运送到结点t（称为汇点），可以从其他结点中转，求最...
上一篇题解我们讲解了SCOI 2006（DAY 1）的题目，这篇博客就让我们走进更加奇幻迷离的SCOI 2006（DAY 2）的题目吧！ T1 数字立方体 题目描述： 有一个立方体被分成nnn的单位，坐标用(X,Y,Z)表示（1<=X,Y,Z<=n）。每个单位立方体内有一个绝对值不超过109的整数。统计有多少个子立方体的所有数之和是m的倍数。子立方体即满足x1<=X&...