kmp 题意： 分析： 我们看着一题，我们仔细想想。首先如果没有要求中间 子串 的话，就很简单了。我们直接输出前后缀相等的就好了。无论是 kmp 还是 暴力 都是线性时间。 但是麻烦就在于中间要有字串。 那我们想想，如何判断中间有没有子串呢？ 假设，next[n] = k 意味着s0,s1,s2,s3,s4.....sk-1 == sn-k+1,sn-k+2.....sn子串即为s[0:k] 那么如何判断中间有没有子串呢？如果有子串，s[i:i+k]那么我肯定s[0:i+k]的next就会是k想想是不是这样？也就是说我们求next数组就可以了。求出next[n]看next[n]的值一共被...

思维，dp，枚举 题意： 分析: 这题我拿到手时，是一脸懵逼。我不知道该从哪里下手才好。我率先的想法是，统计每一个索引i处，开个数组记录他后面与他数值相等的索引。 再从头到尾遍历，遍历到i时，一一遍历他的索引数组。假设遍历到了j 我们确定了第三个数索引为j 第一个为i然后在i到j之间再遍历去确定第二个数字的索引，然后同样进去其中的数组，寻找第四个数字的索引，必须保证索引大于第三个。这里可以利用二分。 但是，着其实是很麻烦的。时间复杂度直接爆表！！！！！！ 那么我们看看上面的哪里超时的了。我们先确定了第一个数字，然后再确定第三个数字，然后再确定第二个数字，最后确定第四个数字。 虽然我们进行了...

tarjan，dfs 题意： 分析： 不知道怎么回事，这道题做的时候总是有点迷迷糊糊的，犯了好多低级错误。。。。。。 总之，如果接触到tarjan的话那么我们肯定能够反映过来：一定要缩点的。缩点后啊，这张图就是一张拓扑图。有向无环。每割点都有权值，就是此节点缩的点数那现在让我们从这张有向无环图中找一条路径，是这个路径的点权和最大！！ 很简单啦，因为是有向无环图。所以我们可以对每一个点直接dfs。 int res[max_n]; int dfs(int u) { if (res[u] != 0)return res[u]; for (int i = head2[u];i;i ...

结论题，最小割，tarjan 题意： 分析： 题目看了，就是让我们对图中的每一条边都做判断：是否可以是最小割边？是否一定是最小割边？暴力做法：n*m对于每一条边我们都单独判断！ 那么现在来看tarjan做法：首先让我们想想，传统如何判断一条边能不能在最小割集中。先跑最大流，得到其残余网络(此残余网络中满流边自动断开，即cap==0我们就当他不存在)1.对于边e(u,v)如果e没有满流，那么绝对不是最小割。2.对于边e(u,v)如果满流但是在残余网络中有一路径使得u->v那么他绝对不是最小割。3.对于边e(u,v)如果满流且残余网络中不存在u->v那么可以是最小割4.对于边e(u...

字符串同构，tarjan，hash 题意： 分析： 不难想到用tarjan算法，将互相愿意组队的人员划分出来。但是，稍微有困难把你的便是：如何计算这只队伍的团结系数呢？ 这里牵扯到了一个知识点：字符串同构！！对于字符串a,和字符串b我们知道a经过一定的循环就会变成b。我们称a与b同构。那么倘若我们将a,b都变为其最小的同构字符串c。然后我们统计又多少人是同构字符串时，直接用hash表统计c的个数不就好了吗？ 关键是如何变为最小的同构字符串呢？这里给出代码： string getmin(string s) { int len = s.size();int i = 0, j = 1, ...

建图拆点，最小费用最大流 题意： 分析： 首先我们认识到，对于我所在的棋盘，如果我把所有的黑子都摆放在指定的位置上了的话，那么白子也一定被摆在了指定的位置。所以，这里我们不妨只看黑子，考虑让其摆放在规定的黑子位置上所消耗的步数最小。 不难想到，这是个匹配问题。我们要对所有的黑子对其归属位置进行匹配！ 最小费用网络流的想法自然孕育而生。但是还有一个问题：我们在匹配的过程中是否会影响到其他的匹配呢？即，黑子在不断进行交换移动中会不会对其他的黑子造成影响，使其交换次数发生改变。 这也是我非常不解的地方。想了很久没有想明白。上网搜题解大多也对这一点没有解释。直到我看到了洛谷的一篇题解，有这样的一段...

最小费用最大流，对数乘法换加法，浮点数比较 题意： 这道题看上去很裸，似乎就是一道最小费用流的题目。需要注意的有三点：1.这里面最小费用的计算是乘法，所以我们要对其取对数将其变为加法。2.因为e(u,v)的cost为浮点数，所以再spfa算法中我们便不能再直接比较了。需要加上个eps否则会一直超时的。3.我们注意到第一次走的时候不会产生费用，那么我们直接在该建边的两点间再建一条费用为零，容量为一的边就好了。 前两个雷我都踩了。。。。。。 代码如下： #include<iostream> #include<math.h> #include<queue> #...

网络流，二分、二分图最大匹配 题意： 分析： 这一题出的好啊！！！！正是我能力边缘的题目。有助于提升实力！！！ 我们需要插入m段广告，有n+1个空位我们可以插入。当插入时，我们整体得不流畅度可能会改变。 当我们看到max() 时，我们就应该尝试用二分的思想取考虑一下，a1,a2,a3,a4当我们将b1插入a1,a2时，这里的不流畅度为：max(abs(a1-b1),abs(a2-b1))两头稍有特殊。但大致一样。这就是我们每一条边的代价。 我们很容易想到对着些边权进行二分，将不流畅度大于mid得边都不连。这样我们总体得不流畅度一定小于mid然后连边，左边是广告，右边是空位。最左边一个超级汇...

最大流，反复跑流 题意： 分析： 这题我不会，是看人题解后做的。汗 这题有两个收获：1.网络流建无向图。 void add(int from, int to, int cap) { E[cnt].to = to; E[cnt].cap = cap; E[cnt].rev = cnt + 1; E[cnt].next = head[from]; head[from] = cnt++; E[cnt].to = from; E[cnt].cap = cap; //有向图 为 0 E[cnt].rev = cnt ...

最大流，二分 题意： 分析： 这一题，我刚拿到手是蒙B的。我的第一反应也是最小费用最大流，但是想了一会也是不知道该如何表示X^2这个万恶的东西。迫不得已，展开别的思路： 我们这样建图：源点S与1~n相连，取cap = 1 无cost1~n与n+1 ~ n+m 按照数据相连 cap = 1,无costn+1 ~ n+m 与t 相连，无cost, cap待定 观察函数 X^2 导数2X x越大他增的越厉害。这是常识 那么，在我们建的图中，最终在n+1~n+m向t汇聚时，我们要尽量避免某一条路径的x特别的大。因为总值我们是知道的为n那么最好他们都是相等的，为 n/m 这样最小！！ ...

建图，网络流，最小费用最大流 题意： 分析： 雨神说过，图论题难就难在建图上。这题我觉得建图还是蛮难的。 我们捕捉一下重要信息：从一个额外的点出发，恰好经过每一个点一次，可以进行跳跃，永远是小点连大点。 我们不难明白，所谓额外的点其实就是时空跳跃的中介点，也同时是起点。同时，我们也很本能的想将所有的点向汇点t连一条c=1,d=0的有向边。然后求最小费用最大流。类似这样： 但是，很明显没有这么简单。我们会发现，我们仅仅实现了从S跳到每一个节点上去。我们都知道，在最小费用流算法中，我们是每一次都取最短路的。我们无法保证走了一次的点不会在被取到。也无法保证能够实现点分叉的情况。比如图中e(1,...

最大点权闭合子图 题意： ##题解：这时一道非常模板的最大点权闭合子图问题。 但是，我们不知道最大点权闭合子图是什么。。。。。。 现在，有我来告诉你：有一堆有权值的点，权值可以为正为负为零。这些点有一些如图的相对顺序：即，这个图中会有一些树！图可能原本是这样的：图具体长什么样无所谓，你只要知道这些图是没有圈的就可以了。 而所谓的闭合子图，就是这个图中的以任意一个点为根的树。树可以不唯一，即两个闭合子图加起来还是一个闭合子图。我们要求这个闭合子图节点的最大点权和 注意一点，这里的树，必须一直向下延伸，直到无法再延伸才行！！比如下图中： 所以，清楚最大点权闭合子图的概念了吗？ 那么，最大点权闭合...

最小费用最大流 题意： 分析： 这是我第一次做最小费用最大流的题目。感觉还行，写个题解留作纪念。 意识到这是个关于最小费用最大流问题并不难。但是，关键在于如何建图。拆点是一定的。我刚开始想，对每一个节点，拆成两个。原节点到拆点一条c=1 d=-vi 的路拆点到原节点一条c=inf,d=0的路。但是这时不行的！因为这会造成负圈！这真的太致命了。所以，我们不能这样建图。我们可以这样建图，原节点到拆点建两条边，一条c=1,d=-vi 另一条c=inf,d=0然后原节点到其他节点的边，都变成拆点到其他节点的边。这样我们也可以实现。注意，这里有一个条件1<=u<v<=n 所...