昨天多校的AC自动机入门题……
为什么我还要写AC自动机入门题呢，因为我太不甘心了……
题意：
给你很多个字符串，很多个询问。
每个询问两个数( a , b) ，表示询问第 ( a)个字符串和第( b)个字符串的最长的子串同时必须是某一个给定字符串的前缀。
思路：
这个真的是很简单的，建议AC自动机初学者写完 HDU 2222 后马上来写这题……
仔细思考，AC自动机建立在Tire图上，Trie图上的一个结点就代表了一个前缀。
所以我将所有字符串建立一个AC自动机，对于一个询问的两个字符串，我用一个set去记录第一个字符串所能到达的结点。第二个字符串去查询是否有相同结点。如果有，就说明有一个子串同时是某一个字符串的前缀。将当前答案与这个结点的深度进行比较就好了……
AC Code
#include
昨天的多校应该是团队合作最失败的一次…… 一开始过题人数最多的那道题许颂嘉没去想，只能我自己上了，第一直觉就是DP，但这个状态转移真的想了我好久好久，但想出来后又觉得是非常显然的…… 后来不知道什么时候许学姐来想这题了，估计是急了，也没跟我说，然后就是两个人单独想题的局面，还瞒着我敲了一发容斥……是的，一个队里两个人同时用两种算法在想同一题。这是团队赛最忌讳的。 也可以说是最愚蠢的。 之后敲完之后雨情学姐又给了我一个错误数据，先是打乱我的思路，然后debug了将近一个小时，发现数据错误之后，把最开始的代码交了一发就秒了…… 不想多说什么，这场明明还有一道很简单的细心题，当时急了，没发现重点。和一道几乎是AC自动机入门题的题，没看。 我特么 心如刀割。 题意： 给你一个长度( n\和字符数量( m)，让你组成两个字符串，两个字符串两两不能有统一字符。 思路： 标程是容斥，我不会，这题提供DP解法。 令( dp[ len ] [ num ] ) 表示长度为( len ) 的字符串并且有( num )个字符的数量。 那么我现在只考虑一个字符串，它的长度固…
上一场多校一道状压DP的原题。 那我肯定是去做原题啦。 多校的时候我还觉得这肯定是许学姐的锅，没想到居然能转化成状压。 题意： 中文题面，给你( [ 2, n ] ) 这几个数，要你各找两组数字，两组数字之间两两互质。 ( n) 最大为500，问组合数量。 思路： 考虑数据 ( n) 非常小，在 ( \sqrt 500 )以内的质数只有8个，而大于( \sqrt 500 )的大元素只可能为一个，那么我们把相同的大元素放在一起处理，开一个二维数组表示这个大元素在两组中的哪一组，而对于小元素，可以用状态压缩来表示两组数字各自包含那几个质数。最后累加的时候让两个状态不重叠即可。 代码中 ( dp [ k ] [ a ] [ b ] [ c ] ) 表示 前( k)个元素中 第一组数包含的小质数状态为( a) ，第二组数包含的小质数状态为( b) ，大质数为在第一组( 0) ，或者在第二组( 1)…
例行废话 大概是前天试着去入门区间DP，中间穿插了很多其他题目，今天勉强入门并多写了几题。 又被goubi带鱼笑了，shit！ 有些时候我自己也会觉得写一些入门的东西会有点浪费时间…… 但我又想了想，应该说是每个人写博文的目的不同吧。 像我这种小网站，我也不渴求能帮到多少人，只是记录一下自己的成长罢了。 三类经典问题 区间DP被goubi带鱼说是最简单的DP，因为它是有套路可循的。 这个套路就是用小区间推出大区间。是的，这个套路就是这么简单，其他的还是考虑状态与个人思维了。 而小区间推出大区间的方法自然是按照区间长度不断向后DP，每次将所有长度相同的区间长度推出。 一般来说，把这个这个思维熟练了，再学一个四边形优化，区间DP就可以毕业了。goubi带鱼如是说 而关于三类经典问题，大多数区间DP都可以通过转换得到这三类基础模型。当然我也是听别人说啦，我也才刚入门啊 石子归并 传送门 题意： 给你一排石子，你只能将相邻的石子合成一堆，花费为两堆石子的重量和。问如何合并，花费最小。 思路： 如果去掉相邻石子才能合并的限制，那就是一个…
例行废话 哇～，惊了，多校里面第一次出现网络流的题目。然而我并没有时间甚至没有看它一眼…… 我学了这么久的图论究竟是为了什么呢…… 老实说我有一种不详的预感 现在想想的确是这样的，自己努力钻研的高级算法，又有多少会在比赛中用到呢…… 回归正题 这是一道最小割+差分约束的题目，还是第一次遇到这两个结合起来。不过其实也只是分开来的问题，用差分约束判断可行性，再用最小割求解。 题意： 你要给( n) 个小朋友糖果，最少( 1)个，最多( m )个，并且你手上有无穷多的糖。并不是说给一个小朋友的糖果越多越好，给每一个小朋友不同糖果数量对应的愉悦值不同。我们自然希望小朋友的愉悦值最大化。 但这些小朋友也提出了一些要求，对于每一个要求( ( x , y , z ) )，你给 ( x) 的糖果数量 ( ax ) 与给( y) 的糖果数量( ay) 满足如下不等式 ( ax – ay \leq z )。 问满足所有要求的最大愉悦值。…
AC自动机好题，恐怕出题人都完全没有想到是AC自动机。
队友在写这题的时候突然发现了AC自动机的题解。
我看了一下发现还真是板子题。
正文：
WTM！！！！想打人！！！！！！！！！
Shit！！！
淦，再也不为了缩行偷懒了
这题我真的写了好久，今天刚刚发现错误，真的真的真的就是一个板子题，不过要转换一下并且check一下长度就可以了。
但是！！我为了偷懒，在输出的时候，就把答案清零了，这就导致了相同前后缀的答案错误！！！
题意：
给你很多字符串。再给你多组前后缀，问这几组前后缀在以上字符串的出现次数。
思路：
将前缀prefix 与 后缀 suffix 通过一个非字母字符连接，插入到trie中。
再将模式串通过相同的非字母字符连接，对其跑一边AC 自动机记录一下答案就可以了。
需要注意的地方就是模式串的长度不能小于后缀+前缀。
AC Code
#include
后缀数组求最长不重叠重复子串的入门题。 论文题。 也是男人八题之一。 想我活了十多年终于成了 ( \dfrac {2} {8}) 个男人 虽然说是入门题，但也没有那么简单。 说到底，这道题是我第一次将后缀数组应用起来。我意外的发现，后缀数组之所以强大，在于它拆分了所有后缀，然后又构造了 height 数组描述前缀。这就掌握了所有连续子串。 神了！ 这里还是说一下我对最长不重叠重复子串求法的理解。 直接求最长不重叠重复子串是困难的，但对于一个确定的长度 len ，我们却可以( O\left( n \right) ) 地判断其可行性。而这长度又具有单调性，这就使得我们可以用二分的思维去解决它。可行性判断方法如下： 前面说了，sa + height 可以用来描述子串 不是所有。不考虑其它，height 可以单纯的描述为存在的一个公共子串长度。而这个长度大于 len 是我们的必要条件。接下来要判断的就是是否会产生重叠。 sa数组记录的是这个公共子串所对应的后缀起始位置，如果两个后缀它们的起始位置大于等于 len ,毫无疑问，不会重叠。…
好题。但kuangbin说这道题已经是很简单的DP了。 首先kuangbin并没有说错，但是该题的解题思维有点难想到。 如果你按照题意去解题，那你是想不出来的。 还是重在转化啊………… 题意： 给你很多串DNA病毒序列，再给你一串待修复的DNA序列。现在待修复的DNA序列中可能包含病毒序列。 我们的工作是要求修改最少的次数使得待修改序列中不含病毒序列。 问最少次数。 思路： 不要想着去寻找如何修改，有个简单的思路是去寻找所有不含病毒序列的DNA序列，并求出与原串不同的字符数量。然后找出最小值。 但这显然复杂度是很高的。我们可以考虑用DP求解。 记( dp \left[ len \right] \left[ status \right] ) 为当前长度为len，状态结点为 status 时需要修改的最少次数。 那么对下一状态，我对于下面四个结点，如果所组成的字符串构成了病毒串，那么不成立，否则如果当前字符与原字符串当前位置相同，则不需要花费。否则，需要改变一次，花费 + 1。 转移方程 $ dp\left[ len + 1 \right] \left[…