Posts tagged with ACM


emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易想到是最小割了,但是没想到具体的建图方法。 题意: 有n个点,m条边,要你分成两个集合,使得两个集合的导出子图各自权值和的和最大。 两个导出子图中,可选择其中一个,若导出子图中存在有两个点 (i,j) 相连,则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反,只有存在两个点没有边相连,才会增加权值。 思路: 题目的主要目的就是将点集分成两部分,这很容易想到二分图染色,但这是不现实的,因为这是一个最值问题,不存在必然关系。…

对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。 题意: 给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。 思路: 首先询问很多,有$4\times10^5$个询问,直接一个一个找肯定是不行的。 但是值得注意的是,…

一道二分图性质的应用 + 树形DP ? 看博客里都说是树形DP,但我觉得应该是树上前缀和更加合适一些 题意: 给你一个图,让你删除一条边,使得剩下的图是二分图。 输出可删边数并顺序输出边的序号。 思路: 首先你必须知道判定二分图的充要条件 —— 不存在奇环。 如果只是让你判定二分图的话,倒是随便搜一遍就可以解决的问题。 但是这里必须让你删掉一条边…… 写不来……感觉不好写,最后无奈去看题解了…… 先整理一下判断思路: 如果不存在奇环,那么原图本来就是一张二分图,每一条边都满足条件 覆盖了所有的奇环,并且不能覆盖偶环的所有边 为什么同时不能覆盖偶环,…

后缀数组 + 单调栈好题 网络赛时的后缀数组可以用这个思路解,但是我并不是很会,今天补上。 题意: 给你两个串,问你长度不小于 k 的重复子串的数量。 思路: 若只是对于一个字符串,问它长度不小于 k 的重复子串数量,那么考虑对height根据 k 分组,然后记录一下就可以了,将 height 去重后,每个 height 的贡献为…

这种题目就是专门针对我的…… 思路简单,所需注意细节多。 题意: 给你每个元素所在集合,问你有多少个,分割,聚集,映射关系。 思路: 首先很直接的思路就是把每个集合的元素都表示出来,进一步的说hash一下,但集合元素多,集合数量也不少,hash有点困难。 考虑将不同集合的所有相同元素用一个元素表示 (这个只要排序去重即可) 那么对于两个存在这个相同元素的集合 A, B,有如下四种讨论情况: A有若干个元素而B没有 —-> 聚集…