一眼以为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，所以要找最小的边。将其中一个集合插入 字典树，再让另一个集合的每一个点以常数级别的复杂度去找到最小异或值，再更新答案与边数。 最小生成树的个数只要根据乘法原理将边的数量相乘即可。…
一个三元环计数问题……
当然是转化出来的……
一开始没想到去计数三元环的思路，而是直接搜……
然后发现题目理解错了……
又发现这特么不就跟三元环数量有关么？？
巧的是薛昊之前问过我三元环计数，我还特意去看了几眼。不然真的可能卡不出来。
题意：
给你一张无向图，让你计数这样的子图。
V=(A,B,C,D) ， E=(AB,BC,CD,DA,AC)
思路：
一开始我以为必须是矩形，然后发现同一点的不同三元环都满足条件。
所以我只要找到这个点的所有三元环数量，任意挑出两个即可。记得去重
个人三元环计数方法如下：
首先枚举每一条遍，再判断两个端点，确定度数较少的点，从这个点进行扩展一条边，再判断这条遍的另一端是否有边与第一条边的另一端点相连。
其中有很多细节值得优化，比如说对于( sqrt(m) )为分界进行不同的判定。
AC Code
#include
首先说一下这道题的思路真的是非常巧妙。 但是，出题人脑子进shi了么，难道一定要写法和你一样才能过？？？？ 反正卡的特别紧，我到最后还有一个测试点一直超时。 时间限制是 1200s ，明显就是故意的。这种故意卡常在51Nod里巨特么多。搞不懂他们在想什么。 不觉得会在以后碰到类似的题目会故意卡我，因为很多人都是 1000 ～ 1200 的时间卡过的。 题意： 给你一个有向图，让你任意改动边的方向，使得出入度相同的点数最多。 并输出方案。 思路： 一眼看成上下界网络流。实际上这道题就是用上下界网络流改出来的，但就别想了，正解都卡着过，网络流能过？ 建图方式和无汇源上下界可行流一致，跑一遍最大流即可。 下面是另一种思路。 有入度相同的特征的图还有一种，就是欧拉图，对于度数为奇数的点(以下简称奇点，反之偶点），必然不可能存在一个方案使得其出入点相同。这是必然的，那么反过来对于偶点，如果欧拉路径存在也就必然存在一个方案使得其出入度相同。 直接将所有奇点，顺序两两相连，跑一遍欧拉路径即可。 这里补充两点 1. 奇点数量必然为偶数。因为每一条遍贡献的…
Havel定理判定简单图 被上下界网络流烦傻了，暂时不想写代码太长的题。 虽然是一道水题，但也是建立在一定理论基础上的。 再科普一下简单图，没有重边没有自环的图就是简单图。区别有向图和无向图，也就是说，有向图的反向边不算重边。 给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化 可图化的判定： ( \sum_{i=1}^{n}d_{i} mod 2 == 0 ) 。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。 可简单图化的判定（Havel定理）： 把序列排成不增序，即 ( d_1 \geq d_2 \geq \ldots \geq d_n )，则d可简单图化当且仅当 ( d’ = \left{ d_2-1 , d_…
别多说了，神题。
写不来，看得是大佬的题解
很妙，没想到用二分图染色，但是二分图染色的模型的确很适合这个题目。
不过关键还是那个判定定理。
题意：
给你一个序列，要你用两个栈给它排序，问你这个序列是否能排序成功。
思路：
上面的链接很详细，我这里简单说一蛤。
首先必须注意到判定两个数必须在两个不同的栈的充要条件。
S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i
无汇源上下界可行流的模板题。 说是模板题，其实想让它除了二分以外加点变化也是有点困难的。 关于上下界网络流的问题，以前偷懒没学，本来打算这几天补上，加上今天薛昊这个催化剂又来问我，于是就今天开始补了。 在这里我非常非常非常非常非常推荐这篇博文 总结的非常详细，写的有十分通俗易懂，全文十分连贯，评论也有人说看完给人一种荡气回肠的感觉。 当我看完无汇源上下界可行流的时候，我马上敲了一蛤这道题，就一 A 了。妙啊！ 下面简单说一下无汇源上下界可行流的解法，不详细说明，具体请看上面的链接。 无汇源上下界可行流可用建图+最大流解决，建图方式如下： * 对每个给定的边建边，容量为 up – down * 记录每个点的 down 流量差，这里设 入流量为正，出流量为负。如果总的流量差大于0，建边 src -> 该点，容量为流量差。否则，建边 该点 -> des 容量为流量差的负值。 没了，再跑一遍最大流，如果能满流就说明有可行流，…