很早就想学的东西了……但是要学的实在是太多了…… 01分数规划是分数规划中最简单的，所谓01，就是对于每一件物品，他都是不同的，你只有取或者不取两种选择，没有在数量上太多的选择。就像01背包一样。 01分数规划 虽然考察的不多，套路也比较死，但是多校的时候着实出现过。记得应该是cls的那一场，记得是01分数规划的新操作…… 01分数规划是用来解决取舍导致的比例最值问题。解决该问题的方法有两种。 一种是二分，另一种是迭代，迭代法也称 Dinkelbach 算法。 二分法基于验证，迭代法基于直接计算，一般来说迭代法会更快一些。 两者写起来都非常简单。 入门资料推荐。具体思路不再细说。 入门题在这里。 入门资料中谈到，如果对于题目改成最小化，那么就尽量少选，不是很理解他的说法。 就我看来，把分子分母倒一下就转换过来了。 题意： 最裸的01分数规划，要你从 n 个中挑出 k 个使得比例最大。 就图片来说就是要你求这样的结果，当然是选取 k 个。 思路： 验证板子的题，因为它的限制只有一个，没什么好说的。…
CCPC网络赛的KMP模板题……
比赛期间因为被1003卡住了，这道题根本没时间去想……
本来一眼看去我也是想到AC自动机，只要吧字符串反转一下，就可以套用上一次的AC自动机直接求解。
但是模式串和匹配串都只有一个，建立AC自动机虽然可解，但有不必要的消耗。
这道题几乎卡掉了除了KMP以外的所有求这道题的其他解法。
题意：
给你两个串a , b，要你找出 b 串的所有后缀同时也是 a 串的子串。
然后按题意计算。
思路：
其实还是和上一道AC自动机有些类似之处。
但还是有很大不同，AC自动机可以在匹配的时候不断 fail 到前缀。
而KMP只能通过记录匹配，然后从后往前不断 next 累加。
AC Code
#include
南大所谓的最小费用有向图………… 什么 jb 玩意？？？？不是都叫最小树形图么……………… 这道题适合Yasola一起讨论的，虽然说一起讨论，但是对权值进行修改这一关键操作还是他想得 太巨了呀！！！ 然而最后还是差一点。 题意： 给你一张有向图，要你求最大树形图，同时满足最后一个结点的父亲字典序最小。 思路： 这个朱刘算法……有毒…… 朱刘算法真的是把原图毁的不成样子…… 然后我们两个就在这里踩了很多坑…… 首先认清一点，朱刘算法是可以求负权的。这就保证了最大树形图可解。 再是单独一个结点的字典序最小。 首先一个重要的操作就是对边权扩大处理。对于指向最后一个结点的边权我们让它与父亲结点编号联系起来。 联系方法： $ edges[i].cost = v == n ? -w * 1000 – 1000 + u : -w * 1000 $ 说一下我们的很多错误思路，不想看可以直接跳过。 1. 直接用pre 数组输出。 不可行，因为结点都已经缩点染色过了，边数组的起点终点不是原起点，原终点， 2. 开一个ori 数组记录每一个染色后的点的原起…
昨天多校的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 )。 问满足所有要求的最大愉悦值。…