emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易想到是最小割了，但是没想到具体的建图方法。 题意： 有n个点，m条边，要你分成两个集合，使得两个集合的导出子图各自权值和的和最大。 两个导出子图中，可选择其中一个，若导出子图中存在有两个点 (i,j) 相连，则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反，只有存在两个点没有边相连，才会增加权值。 思路： 题目的主要目的就是将点集分成两部分，这很容易想到二分图染色，但这是不现实的，因为这是一个最值问题，不存在必然关系。 而跟二分图相关的只有网络流了，将图分为两半是割的概念，当然只存在最小割，正面去想的话，就是总权值和-最小割。 然后……思路就断了，找不到有效的建图方法。 可以先这么想，我们假定与源点相连的点集为相连增加权值的集合，并称之为，与汇点相连的点集则相反，称之为汇点集。 那么我们先将每个点都与源点相连，其容量为将该点加入源点集所能增加的权值。 再将这个点与汇点相连，其容量为将该点加入汇点集所能增加的权值。 此时直接跑最小割是不对的，因为这些点并不是独立的。…
对Tarjan的算法理解有点要求的题，之前看了一下思路，敲了一下结果没过，照着博客改动了一下但并没有搞懂，今天补上。 题意： 给你一个有向图，若干询问，询问为从 s 到 t 的最小字典序路径中，第 k 个点是哪个点。 思路： 首先询问很多，有$4\times10^5$个询问，直接一个一个找肯定是不行的。 但是值得注意的是，点数比较少，只有$3000$个，假如我们固定起点，遍历全图来获得路径，在遍历的同时，对每一个点来记录答案。理想复杂度为$O(N^2)$，时间上满足条件。 一个问题是如何保证字典序最小，emmmm 用vector记录整张图，对于每个点的边进行排序，因为每个点访问一次，解决之。 这题还有一个合理的大坑，如果在遍历的时候，在之前已经出现了一个环，那么之后的所有点就都不会被访问。 当然你不能在找到一个环后，后面的点就不再遍历，…
一道二分图性质的应用 + 树形DP ？ 看博客里都说是树形DP，但我觉得应该是树上前缀和更加合适一些 题意： 给你一个图，让你删除一条边，使得剩下的图是二分图。 输出可删边数并顺序输出边的序号。 思路： 首先你必须知道判定二分图的充要条件 —— 不存在奇环。 如果只是让你判定二分图的话，倒是随便搜一遍就可以解决的问题。 但是这里必须让你删掉一条边…… 写不来……感觉不好写，最后无奈去看题解了…… 先整理一下判断思路： 1. 如果不存在奇环，那么原图本来就是一张二分图，每一条边都满足条件 2. 覆盖了所有的奇环，并且不能覆盖偶环的所有边 为什么同时不能覆盖偶环，这个我还真没想到，但是在纸上画一画就是很显然的了，同时覆盖奇环和偶环的边删去后，两个环会变成一个新的环，偶数+奇数 还是奇数。所以不能覆盖偶环。 因此得出如下具体实现，随便生成一棵生成树，用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。 如果奇环数量大于 1 ，那么非树边必定不可能是满足条件的，因为非树边最多只能覆盖一个环，两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的…
后缀数组 + 单调栈好题 网络赛时的后缀数组可以用这个思路解，但是我并不是很会，今天补上。 题意： 给你两个串，问你长度不小于 k 的重复子串的数量。 思路： 若只是对于一个字符串，问它长度不小于 k 的重复子串数量，那么考虑对height根据 k 分组，然后记录一下就可以了，将 height 去重后，每个 height 的贡献为 ( max ( 0, height – k +1 ) ) 个人猜测，后果不计 但这题是两个字符串，我们可以将两个字符串用一个特殊字符连接，并将后缀通过第一个字符串长度区分开来，对于同一个 height 组中，当前的 height 只能跟另一个 height 组相比求 lcp 。 一个可行的方法是，将组内不同的height都记录下来，再对于每一个当前height，我把它跟另一个height组一一求贡献。但是这个复杂度为 ( O…
这种题目就是专门针对我的……
思路简单，所需注意细节多。
题意：
给你每个元素所在集合，问你有多少个，分割，聚集，映射关系。
思路：
首先很直接的思路就是把每个集合的元素都表示出来，进一步的说hash一下，但集合元素多，集合数量也不少，hash有点困难。
考虑将不同集合的所有相同元素用一个元素表示 (这个只要排序去重即可)
那么对于两个存在这个相同元素的集合 A, B，有如下四种讨论情况：
1. A有若干个元素而B没有 —-> 聚集
2. B有若干个元素而A没有 —-> 分割
3. A,B各自存在不同元素是另一个集合不存在的 —–> 不参与讨论
4. 不存在相异的元素 —-> 映射
顺便提示一下集合编号在 int 范围内， 要离散化……
淦
AC Code
#include
一眼以为KMP能解，上去就是一WA…… 但是我还不知道KMP的错误点……可惜看不了提交的代码了…… 这道题因为我在比赛的时候被一道煞笔树形DP卡到了，因为图没清空，所以没什么时间去看，虽然最后还是有一个小时给我，但我还是没有做出来。 比赛的时候天海的解法用到了单调栈，但我看了题解还有另一个非常巧妙的做法。 题意： 给你一个字符串，问你刚好出现 k 次的子串数量。 思路： 看了大佬的题解，只给了一个方程。枚举区间为 k – 1 的 height 数组，也就是 k 的 sa，贡献为 $ max(0, lcp( i , i + k – 1 ) – max(height[ i ], height[ i + k ]) $ 一开始听蒙蔽的，略加思考就察觉到了方程的正确性，对于每个区间的 LCP ，如果跟区间外的后缀一旦有重复的，那么这个公共部分就不能算及在内。因为这个部分就不是刚好出现…
思维题，老实说我并没有想出来，应该说是我想歪了……
看了一个大佬的代码，真的是超整洁，这是我目前见过最整洁的代码。值得借鉴。
题意：
每个点距源点有几条单项路径，路径有个花费和另一个时间。要你买构造来回路径使得中间间隔时间不小于 k 。
思路：
首先按照日期排序，菜鸡第一想到的是按照花费权值排序
在相同日期的路径中找出所有花费权值最小的加入集合并维护其最小。如果集合已满就记录当前日期的花费。
一个道理在正向前往目的地来一次，反向返回来一次。
就得到了当前日期正向的的最小值，当前日期反向返回的最小值。
再正向找出当前日期之前的最小值，当前日期之后返回的最小值，使得中间区间尽可能大，越往中间花费越小。
再枚举间隔区间，将往返花费相加找出最小值就是答案。
AC Code
#include
分治+字典树+MST 综合好题 标题即题意，但是不一样的是边权是点权的异或。 不可能会出什么边权也是给定的完全图最小生成树计数的啦，现在看来，也算是套路题了。 当然点数不能太多………… 不卡常才是一个好题的前提条件。写 Trie 习惯性用了类，虽然慢了一些，但也不至于太慢。 题意： 给你 n 个点的点权，边权为其异或值，要你求出最小生成树，以及最小生成树的个数。 思路： 这道题的核心思想还是分治。 我们对给定区间的点权进行处理，并假设这个区间的前面 k – 1 位全部相同。那么对于第 k 位，我们根据 01 将其划分为两个集合，这时候两个集合的前 k 位分别相同，再对这两个集合分别进行同样的处理。 其正确性不言而喻。 在处理的过程中，我们需要将两个集合之间建边，因为是MST，所以要找最小的边。将其中一个集合插入 字典树，再让另一个集合的每一个点以常数级别的复杂度去找到最小异或值，再更新答案与边数。 最小生成树的个数只要根据乘法原理将边的数量相乘即可。…