求水淹没每一层的时间。

显然水如果把某一层淹没了，那么它接下来淹没的将会是左边或者右边单调递减序列中最低的一个。而且之前淹没的Level也可以不管。为了加快检索速度，可以建立一个双向链表来维护。

用个变量ans记录到目前为止的总时间，则要淹没当前Level now的时间就是ans+(now->next->lef - now->last->rig)，新的ans += (now->next->lef - now->last->rig) * ((now左右中最矮的)->hgt - now->hgt)。之后，从链表中删除now，now变为now向两边找单调递减序列中的最矮的那个。

具体的看代码。

Read on →

好熟悉的开关灯问题。实际上，要消去某一行，必须要靠下一行，而且下一行的策略恰恰好就是上一行的状态。因此如果我们第一行确定了，下面的所有行也就都确定了。

所以这题的方法就是：枚举第一行按法，接下来根据题意模拟按灯，复杂度为O(2^n*nm)。要注意按灯不完全和异或相同，因此难以用位运算优化。另外一定要注意最后一行按过之后是不是空的，只有当空的时候才是有效状态。 Read on →

题目就是要求将要求的区域连通的最小代价，并且连接只能建立在相邻两个点之间。

先不管环，只考虑一条线的情况，这个时候可以用栈来处理，有点类似于括号匹配，只不过是这个括号是一定匹配成功的。开一个数组b[]，对于每一个区间[st, ed]，++b[st]，–b[ed]。之后，再开一个sum变量记录当前栈的深度，把b数组从前到后扫描一遍，并且sum += b[i]。如果sum > 0说明这一个点有被覆盖，因此答案+1；如果ans == 0说明不被覆盖，不要管它；另外，根据我们给出的都是匹配的括号，所以ans不可能小于0。

接下来断环成链，枚举从i点断开，那么对于一个区间[st, ed]，如果st或者ed比i小，那么就加上n（跑到了另一边），注意这个时候新的st可能比新的ed大，因此有必要判断+交换st ed。 Read on →

被最大流虐了一个星期才做出了五题，效率有点非常的低……既然如此，那就写点总结来弥补吧。

先讲讲构图上的常用技巧：

S-T直接构图

有的题目非常非常的水，水到几乎题目就跟你讲好如何构图了，并且点的数量也少，那就毫不犹豫地按照题目的要求从源点S到汇点T构图。如：上次《最大流3题》里面的pku1459、pku1273

*根据性质优化

有些题目很容易根据题目意思构出朴素的图，但与上面S-T直接构图不同的是，这种朴素的构图法构出来的图点数和边数很大，比方说1000^{2，那根据网络流算法的最差O(n}3)的复杂度，超时是必定的了。这个时候就得根据朴素的图的特殊性质来进行缩点。

比方说pku1149，根据朴素的构图方法会产生约100,000个点，进行如下优化：

1. 如果几个节点的来源完全相同，则可以把它们合成一个。
2. 如果几个节点的去向完全相同，则可以把它们合成一个。
3. 如果从u到v有一条容量为∞的边，并且v除了u以外没有别的流量来源，则可以把这它们合并成一个。

如此优化后可以整理思路重新构图，即可得到只有n+2个点也就是102个点的图。

差值建图 Read on →

用C++重写了一份，Pascal版本在这里。

1. 字符串转高精数组
2. 高精+高精
3. 高精+低精
4. 高精-高精（答案必须为非负数）
5. 高精*高精
6. 高精*低精
7. 高精div低精
8. 高精数之间的<、>、=判断
9. 高精数的输出
10. 以上全都是压4位
11. 一个小小的demo

可以发现操作符重载之后运算符的优先级和结合性不变。 参数表中的const引用很重要，否则复制数组会浪费很多时间。 程序如下： Read on →

把问题拆成两问：

1. 求出当m=1的时候的方案数ans
2. 计算m^ans mod (10^9-401)

先考虑第二问。

显然第一问的ans很大很大，而答案只是要 mod (10^{9-401)的值，而10}9-401刚好是一个质数。由费马小定理知，a^n mod p == a^(n mod (p-1)) mod p。因此我们要求出ans mod (p-1)，之后快速幂处理就好了。麻烦的就是如何求出ans mod (p-1)。

接下来考虑第一问。

考虑每一个盒子放i个球，那么就总共需要n/i个盒子，这种情况下的方案数就是：

C(n, i) * C(n-i, i) * C(n-2i, i) * ... * C(i, i) / P(n/i, n/i)

根据排列组合的定义，可以化简为：

n! / (i!^(n/i) * (n/i)!)

这就是ans的精确值。

现在我们要求的是ans mod (10^9-401-1)的值，就必须用中国剩余定理进行拆分了。 Read on →

求W在T中的匹配次数，完整地KMP之。 Read on →

求所有满足既是S前缀又是S后缀的子串的可能长度。

实际上KMP预处理的时候就是算s[1..j]==s[i-j+1..i]的最小长度，那么当i=len的时候求的p[len]就是既是S前缀又是S后缀的子串的最大长度，因此i=p[i]递归输出p[i]。 Read on →

求构成原串的最短重复子串长度。

KMP的预处理部分即可解决。预处理完，p[len]表示当len匹配失败的时候的回退位置，也就是说p[len]+1..len这部分是构成原串的一个重复子串，子串的长度也就是len-p[len]。题目求的是最多的重复次数，相当于求最短的重复子串，因此答案就是len/(len-p[len])。不过有个特殊点要判断，那就是如果len mod (len-p[len]) != 0，那么原串肯定不是由p[len]+1..len构成的，也肯定不是由任意重复子串连接构成的，因此此时的答案就是1。 Read on →

求构成S[1..i]的最短重复子串重复次数。

和PKU2406一样，只不过将输出改成i/(i-p[i])而已。 Read on →