140 Integer Sequences 数论：扩展欧几里得
141 Jumping Joe 枚举142 Keyword 搜索：IDA*
143 Long Live the queen 动态规划：树形DP
144 Meeting 数学：概率题
145 Strange People 搜索：启发式搜索
146 The Runner 数学题
147 Black-white king 区间求交
148 B-station 枚举：堆优化
149 Computer Netowrk 动态规划：树形DP
140 Integer Sequences
线性同余(模方程组)
题意：给定数组A( A[i] <= 2*109 )，求非负整数数组X，使得 (A*X) MOD P == B。
题解：根据题意，对于数组A，X，个数N以及除数P和余数B，可得
(
A[0]*X[0] + A[1]*X[1] + A[2]*X[2] + ... + A[N-1]*X[N-1] ) MOD P = B (1)
稍微做一下变形，可得(2)式：
(
A[0]*X[0] + A[1]*X[1] + A[2]*X[2] + ... + A[N-1]*X[N-1] ) + K * P = B (K为任意整数) (2)
由于K为任意整数，所以我们可以将它拆成K0 + K1 + K2 ... + KN-1，然后分别和前面N项去匹配，得到下面的等式：
(A[0]*X[0]
+ K0*P) + (A[1]*X[1] + K1*P)
+ ... + ... (A[N-1]*X[N-1] + KN-1*P) = B (3)
根据扩展欧几里得定理，ax + by =
GCD(a, b) 必定有整数解，于是(3)式可以转化为
GCD(A[0],
P) * T0 + GCD(A[1], P) * T1 + ... + ...
GCD(A[N-1], P) * T N-1 =
B (4)
令A'[i] = GCD(A[i],
P), X'[i] = Ti，(4)可以简化为
A'[0]*X'[0]
+ A'[1]*X'[1] + A'[2]*X'[2] + ... + A'[N-1]*X'[N-1] = B (5)
这时我们可以发现，(2)和(5)的形式是一样的，只不过(2)有N+1项，(5)有N项，所以根据数学归纳法，进过N次操作之后，最后的等式必定可以转化成
ax = B 的形式，这里的a为所有A[i]的GCD，这个x当且仅当a整除B的时候有解，然后根据x的值可以递推求出上一层的值，经过N次迭代就可以将所有的X[i]求出来了。
注意：迭代过程中，各种乘法有可能会整数越界，所以每次计算出的结果要对P求余，如果值小于零需要再加上P。
141 Jumping Joe 枚举
题意：求满足方程组
P1*x1 - N1*x1 + P2*x2 - N2*x2 = P
P1 + N1 + P2 + N2 = K
的正整数解(P1 , N1, P2, N2)。x1, x2 (0 < x1 , x2 < 40 000), P (-40 000 < P < 40 000) and K(0 <= K < 2*109)
题解：首先将第一个方程变一下形，可以发现：
（P1 - N1）x1 + （P2 - N2）x2 = P 其实是一个模线性方程，而P的范围很小，所以可以考虑枚举（P1 - N1）的值，枚举范围为[-40 000, 40 000]。如果在这个范围内找不到解，那么在更大的范围必定也找不到解。
所以令a = P1 - N1,
1）如果 (P - a*x1) mod x2不等于零，则说明这个枚举的a非法，因为P2 - N2必须为整数;
2）否则，b = P2 - N2 = (P - a*x1) / x2;
3）a + b = (P1 + P2) - (N1 + N2)
K = (P1 + P2) + (N1 + N2)
所以如果 a+b 和 K的奇偶性必须保持一致，否则说明枚举的a非法，继续枚举下一个；
4）令 c = P1 + P2 = （a+b+K）/ 2
5）将四个未知数用P1来表示：
a) P1 = P1
b) P2 = c - P1
c) N1 = P1 - a
d) N2 = c - b - P1
由于四个未知数都是非负整数，所以有
a) P1 <= c
b) P1 >= a
c) P1 <= c - b
d) P1 >= 0
那么P1 的左区间为 Max(a, 0), 右区间为Min(c, c - b),如果左区间小于右区间，则当前枚举的a无解，否则说明找到一个可行解，P1直接取Max(a, 0), 就可以顺势算出N1、P2、N2的值了。
142 Keyword
IDA* + HASH
题意：给定一个长度为N(N <= 5*105)的字符串T（只包含'a'或'b'），求一个最短的字符串S（只包含'a'或'b'），并且S不是T的子串。
题解：可以这么考虑，对于一个长度为N的串，它有长度为L的子串（1
<= L <= N），这种子串的个数为X = N - L + 1, 理论上最大允许的子串种数为 Y = 2L。则 Z = Y - X = 2L -
(N - L + 1) = 2L + L - N - 1, 可得Z为对于自变量L的增函数，当L
= N 的时候 Z = 2N - 1 > 0, 所以实际最大子串种数会远远高于出现的子串数，于是可以通过枚举子串的长度L，然后利用深搜枚举每一位是'a'还是'b'，当枚举完毕一个长度为L的子串后判断是否是原串的子串，如果不是则直接输出解，结束搜索过程。否则继续枚举下一个，当所以长度为L的子串枚举完毕都没有找到解，则枚举L
+ 1的情况。
由于每个字符串只有'a'和'b'两种字符，所以可以将每个字符串压缩成一个二进制的整数，例如： aab 可以表示为 001， bbbaa可以表示为
11100，以此类推...
判断是否是子串的操作也可以不需要进行字符串逐个比较，只要在枚举之前对源字符串的所有长度为L的子串进行一次哈希，然后枚举完毕在哈希数组中查找是否出现即可，每次查找复杂度O(1)。
长度为 500000，结果少看了一个0，将数组开成了
50000，悲剧...；
143 Long Live the Queen
动态规划(树形DP)
题意：给定一颗树，和树上每个结点的权值，求一颗子树，使得权和最大。
题解：用DP[1][i] 表示i这个点选中的情况下，以i为根的子树的权和最大值;
用DP[0][i]表 示i这个点不选中的情况下，以i为根的子树的权和最大值;
DP[1][i] = v[i]
+ sum{ DP[1][v] v是i的直接子结点 && DP[1][v] > 0 }
DP[0][i] = max(
0, max{ max( DP[0][v], DP[1][v] ), v是i的直接子结点 } )
这样，构造一个以1为根结点的树，然后就可以通过dfs求解了。这题题目要求求出的树为非空树，所以当所有权值都为负数的情况下需要特殊处理，选择所有权值中最大的那个作为答案。
144 Meeting
概率题
题意：A和B两个人想要在(X,Y)这个时间段内见面，但是如果某个人先来，他等的时间超过了Z，他就会走，他们就见不到面了。问他们能见面的概率。
题解：面积法。画个图就明白了。
图1
x轴表示A出现的时间，y轴表示B出现的时间，平面坐标的点表示他们出现时间的集合，只有当点在橙色区域内，才能相遇。假设A在t1时刻出现，B在t2时刻出现，那么
只有当 |t1 - t2| <= Z 时才可能相遇，将不等式化简就可以得到上图，所以最后的概率就是图中的六边形区域面积 除上 正方形的面积。
即：
A = 60 * (Y - X)
B = 60 * (Y-X) - Z
P = 1 - B*B / (A*A)
145 Strange People
启发式搜索
题意：给定N(N<=100)个点和M(M
<= N*(N-1))条单向边，以及起点S和终点T，求从S到T的第K(K <= 500)短简单路（每个点只能访问一次）。
题解：首先，利用反向边求出终点T到所有点的最短路d[i]，那么d[S]表示从S到T的最短路。令maxLength =
d[S]，然后利用dfs搜索从S到T，长度不超过maxLength的简单路径，如果找到的路径总数大于等于K，则结束搜索，这时的maxLength表示第K条路径的长度；否则增大maxLength的值，重复上述步骤，直到maxLength为无穷大都找不到K条路径的时候就表示没有第K短路。
在进行搜索的时候，需要加上一些剪枝：
1) 可达性剪枝
假设当前访问到的点为u，之前已经访问过的点的集合为vset。那么利用BFS可以在O(n)的时候内判断u到T是否可以在不经过vset的情况下可达。
2) 启发式剪枝
假设当前访问到的点为u，本次搜索中从S到u的距离已知，为length(S,
u)，而之前已经计算出从u到T的最短估计距离为d[u](即A*中的估价函数，之所以称之为估价，是因为它并不是真正的最短距离，因为在S到u这条路径上可能访问了u到T这条最短路径上的点，所以真正的最短距离肯定大于等于d[u])。如果length(S, u) + d[u] > maxLength，则表明当前这种策略中，从S经过u到达T的最短距离已经大于给定的长度，就不用往下搜索了。
在搜索的过程中，每次搜索到某个点u的时候都可以找到一个值vLength
= length(S, u) + d[u]，我们取所有vLength中满足大于maxLength 的值的最小者作为下一次搜索时的最大长度maxLength，使得maxLength不是以每次加1的方式累加，从而减少了很多不必要的枚举，可以大大加快找到第K短路的速度。
3) 二次启发剪枝
启发式剪枝可以解决大多数随机数据，但是对于某些特殊设计的数据，还是得想更好的剪枝，例如图2所示，起点为S，终点为T，除了起点和终点，其它点形成一个完全图，边的权值均为1。如果采用上面的方法进行启发，最短路d[S]为2，次短路则为10000+1+1 = 10002，但是除了终点以外，任何一个点到达T的最短路都是2，即d[i] = 2 (i
!= T)，这意味着length(S, u) + d[u]不能很好的起到启发的作用，会让maxLength还是以加1的方式逐渐累加，然后就有可能出现这种情况：从S出发，进入到完全图中走了一大圈，然后到达和T相连的那个点发现边权值为10000，远大于maxLength，但是这个状态图是N!的复杂度，等到搜索结束估计花儿都谢了...
可以用d[i][j]来保存从j点到达终点T，并且不经过i点的最短路径，同样可以通过从T点反向一次预处理求得。然后每次访问到u的时候，判断从S到u之间的点中，是否有满足length(S, u) + d[v][u] > maxLength的v，如果存在，直接剪枝，并且用最小的length(S,
u) + d[v][u]作为下一次的启发值。
图2
146 The Runner
精度转化题
题意：一个人在一个周长为L的圆上跑，每个时间段(Ti)的速度(Vi)不一样，问最后他离起点的圆弧距离，周长是个有四位小数的浮点数，其它全是整数。
题解：首先可以考虑如果周长是整数的话，就可以通过取余来求解了，而周长最多只有四位小数，所以可以考虑将周长和(Ti, Vi)都扩大10000倍，全部转化成整数后，只要将总距离Sum{ Ti
* Vi } 模上周长取余数即可。
注意，这里是圆弧，圆弧是有一个优弧和劣弧的概念的，所以要取两条弧之间的最小值。
147 Black-white king
区间求交
题意：在一个N*N(N <= 106)的棋盘上，有三个棋子：黑王、白王、黑白王，它们的行走方式一致，每秒向8个方向中的任意一个行走一步，如图3所示。
图3
现在黑王和白王想要相遇(即占据相邻的格子)，而黑白王需要阻止它们相遇，即抓住其中一个王(走到其中一个王所在的格子)，黑王和白王行走时总是走最短路径，而黑白王走的路径无法被缩短(即能够走斜向的时候，不会走Z字形)，由于黑白王是隐身的，所以黑王和白王无法看见黑白王的走向，但是他们知道有它存在，当黑王和白王走到黑白王所在的格子时不会有任何事情发生。问黑白王是否有可能抓住其中一个王，如果有可能，输出最少步数；如果不可能，输出黑王和白王相遇总共的行走步数。行走顺序为白王、黑王、黑白王。
题解：
如果黑王和白王的y方向差值小于x方向差值，那么将三个棋子的x和y值分别交换。保证黑王和白王的y方向差值大于等于x方向差值，由于黑王和白王总是走他们能够相遇的最短路径，所以每次移动一定要保证在y方向朝对方移动一格，所以两个王的行走区域为朝着对方方向的一个“喇叭”形区域。
如图2所示，两个王的y方向坐标差值为T，黑王坐标(Bx, By)，白王坐标(Wx, Wy)，那么走i步后的黑王的y方向坐标为定值By + i * bDir，其中bDir为黑王到白王的方向；x方向的可行区间为[Bx – i, Bx + i]和[Wx – (T-i), Wx + (T-i)]的区间交集，即图中两个“喇叭”形区域的交集就是黑王和白王的可行区域，最多T-1步后两人相遇。
图4
黑白王的运动区域更加简单，如图3所示，灰色的方形外框表示经过3步后黑白王有可能在的位置，即一个长度为2i + 1的空心正方形区域。
图5
于是，可以枚举步数，判断黑王和黑白王、白王和黑白王的第i步的区间区域是否有交集，如果一旦出现某个王在第i步的时候和黑白王的正方形区域有交集，则表明黑白王有可能在第i步抓住其中一个王，否则当2i >= T-1的时候还没有交集，表明黑王和白王已经相遇，总步数为T-1。总复杂度O(N)。
148 B-Station
枚举 + 堆优化
题意：给定N(N <= 15000)个工作车间，每个工作车间有Wi的水量，能承受Li的水量，如果水量超过Li，第i个车间的所有水就会尽数流入第i+1个车间，同样，摧毁第i个车间，那么它的水量也会流入第i+1个车间，但是摧毁第i个车间是有代价Pi的，现在问要让第N个车间的水全部流出来，最小的代价是多少。
题解：首先，暴力的办法就是枚举第一个被摧毁的车间k，如果存在i使得Wk + Wk+1 +
... + Wi <= Li，那么第i个车间必须也要被摧毁（否则经过第i个车间流不过去，前面的努力就白费了呀），这样就可以把所有需要摧毁的车间枚举出来，比较最小值，复杂度O(N2)，对于15000的数据量来说是行不通的。
那么突破口在哪里呢？还是枚举的思路，假设我们现在从第一个车间开始摧毁，模拟水流往下流，记录所有需要摧毁的车间集合S；那么当我们枚举第二个车间开始摧毁的时候，需要摧毁的车间集合T一定是包含了 S - {1}
的；同样，第三个车间开始摧毁的时候，摧毁的车间集合一定是包含了T - {2}的，原因很简单，起始摧毁车间编号越大，流经某个车间时候的总水流就越小，超过下限的机会越少，越有可能要进行人为的摧毁。为了便于理解，先来看一组数据：
W
L P SumW
SumW - L
1
6
5 1 -5
2
8
3 3 -5
3 4 9
6 2
4 2 7
10 8
3 12 5
13 1
5 15
4 18 3
我们用SumW[i]记录从第1个到第i个车间的水流总和，SumW[i] - L[i]则表示当选定第一个车间摧毁后，水流流经第i个车间后剩余的水量，很明显，当这个剩余水量小于等于0的时候，表明这个车间也要被摧毁，所以在上面这个例子中，如果选定了第一个车间摧毁，那么第二个车间也必须被摧毁。
那么，如果选定第二个车间为起始摧毁车间，其实就是在 { SumW[i] - L[i]-W[1] | i >= 2 }这个集合中找小于等于0的数的下标，于是，算法也就应运而生了。
用preCost记录枚举第k个为起始摧毁车间的最小花费，一个小顶堆RQ存放SumW[i] -
L[i]的值，另外一个小顶堆CQ存放此次的摧毁车间集合，那么当枚举到第k+1个车间的时候：
1) 判断RQ堆顶元素WL；
a) 如果 WL.val -
SumW[k] <= 0 说明第WL.idx个车间需要被摧毁，弹出WL，将 花费累加到preCost上，继续1）。
b) 否则，其他车间均无须摧毁，转到2）（因为这是一个小顶堆，如果某个WL.val - SumW[k] > 0，那么以后弹出的元素至少不会比这个小）。
2) 判断CQ堆顶元素idx；
a) 如果 idx 下标比k+1小，那么弹出idx，将花费从preCost中减去，继续2）。
b) 否则，此时CQ中的元素为当次枚举说需要摧毁的车间，转3）；
3) 将花费 preCost 和最小花费 MinCost 比较，更新最小花费。
这样一来，每个车间最多进队一次，出队一次，插入、弹出复杂度均为O( log(N) )，所以整个算法复杂度为 O( N log(N) )。
149 Computer Network
动态规划(树形DP)
题意：给定一棵树，求这棵树上每个结点的最长路。
题解：
DP[0][i] 表示以i为根结点的子树 中 i到叶子结点的最长路。
Pre[0][i] 表示导致此次最长路的结点编号。
DP[1][i] 表示以i为根结点的子树 中 i到叶子结点的次长路。
Pre[0][i] 表示导致此次最次路的结点编号。
从根结点开始遍历，对于每个结点，
DP[0][i] = max{
edge(i, son) + DP[0][son] son 为i的直接子结点 }
同时保存下
最长路 产生的子结点的编号 Pre[0][i]；
DP[1][i] = max{
edge(i, son) + DP[0][son] son !=
Pre[0][i] son 为i的直接子结点 }
同时保存下
次长路 产生的子结点的编号 Pre[1][i]；
LN[0][i] 表示i到所有点中的最长路。
LN[1][i] 表示i到所有点中的次长路。
然后对于根结点1再进行一次结点遍历，更新LN[0][i]和LN[1][i]的值；
显然，LN[0][i] >= DP[0][i]; LN[1][i] >= DP[1][i](因为DP表示子结点过来的最长路，而LN则包含了从父亲结点过来的最长路，所以计算LN一定要先计算i的父亲u的最长路和次长路)。
所以从1开始，1的最长路和次长路和次长路一定是等于子结点过来的值（因为1为根结点，没有父亲）。然后遍历1的子结点，每次遍历结点u，更新儿子v的最长路以及次长路（包括导致此次路径的前驱编号Pre）：
1) 选取待定最长路；
a) 如果u的最长路来自v，那么待定最长路为 T = LN[1][u]
+ edge(u, v)
b) 如果u的最长路不来自v，那么待定最长路为 T = LN[0][u] + edge(u, v)
2) 将待定最长路和原本v到子结点的最长路、次长路进行比较；
a) 如果待定最长路T 比v本身的最长路LN[0][v]要长，那么：
LN[1][v] = LN[0][v]; // 原本最长路变为次长路
LN[0][v] = T; // 更新原来的最长路为待定最长路
b) 如果待定最长路T 比v本身的次长路LN[1][v]要长，那么：
LN[1][v] = T; // 更新原来的次长路为待定最长路
3) 比较的时候需要将前驱编号也保存下来，因为每次选取待定最长路的时候需要用前驱编号来判断是选最长路还是选次长路。