资料文本课件分析slide

1、CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D杂题选讲绍兴市第一中学2014 年 3 月 28 日CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DGhd 11Source: Codeforces Round #213 (Div. 1) Problem D数据范围1 n 106 , 1 ai 1012。题目大意给出 n 个数 ai ，求一个最大的 g ，使其能整除至少一半的数。CF364DCF392DCF392E

2、historyCF398CCF380DCF232ECF396EarchitectREMOVECF398D设 g 为最终，假设我们已知 ar 被 g 整除，那么就在 ar 的约数中。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D设 g 为最终，假设我们已知 ar 被 g 整除，那么就在 ar 的约数中。枚举约数后计算能整除的个数，设约数个数为 d ，则复杂度为 O(nd) 。如何优化？标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Earc

3、hitectREMOVECF398D设 g 为最终，假设我们已知 ar 被 g 整除，那么就在 ar 的约数中。枚举约数后计算能整除的个数，设约数个数为 d ，则复杂度为 O(nd) 。如何优化？先预处理出所有约数，然后把 ai 按约数中。(ai, ar) 统计到各个标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D设 g 为最终，假设我们已知 ar 被 g 整除，那么就在 ar 的约数中。枚举约数后计算能整除的个数，设约数个数为 d ，则复杂度为 O(nd) 。如何优化？先预处理出所有约数，然后

4、把 ai 按约数中。(ai, ar) 统计到各个最后从小到大枚举所有约数，从它的倍数中累加，就能得到 被该约数整除的数的个数。复杂度 O(n log ar + d2) 。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D设 g 为最终，假设我们已知 ar 被 g 整除，那么就在 ar 的约数中。枚举约数后计算能整除的个数，设约数个数为 d ，则复杂度为 O(nd) 。如何优化？先预处理出所有约数，然后把 ai 按约数中。(ai, ar) 统计到各个最后从小到大枚举所有约数，从它的倍数中累加，就能得

5、到被该约数整除的数的个数。复杂度 O(n log ar + d2) 。因为 g 要整除至少一半的数，所以随机选一个数被 g 整除11的概率为，即错误概率。22标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D设 g 为最终，假设我们已知 ar 被 g 整除，那么就在 ar 的约数中。枚举约数后计算能整除的个数，设约数个数为 d ，则复杂度为 O(nd) 。如何优化？先预处理出所有约数，然后把 ai 按约数中。(ai, ar) 统计到各个最后从小到大枚举所有约数，从它的倍数中累加，就能得到被该约数整

6、除的数的个数。复杂度 O(n log ar + d2) 。因为 g 要整除至少一半的数，所以随机选一个数被 g 整除11的概率为，即错误概率。22随机选 k 个数，错误的概率就会降到。 12k标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D设 g 为最终，假设我们已知 ar 被 g 整除，那么就在 ar 的约数中。枚举约数后计算能整除的个数，设约数个数为 d ，则复杂度为 O(nd) 。如何优化？先预处理出所有约数，然后把 ai 按约数中。(ai, ar) 统计到各个最后从小到大枚举所有约数，从

7、它的倍数中累加，就能得到被该约数整除的数的个数。复杂度 O(n log ar + d2) 。因为 g 要整除至少一半的数，所以随机选一个数被 g 整除11的概率为，即错误概率。22随机选 k 个数，错误的概率就会降到。 12k【时间复杂度】O(k(n log ar + d2)。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DThree Arrays 22Source: Codeforces Round #230 (Div. 1) Problem D数据范围1 n 105 , 1 ai, bi,

8、ci 109。题目大意有三个长度均为 n 的数组，找出三个数 u, v, w ，使 a, b, c 中所有数的并集与 a 中前 u 个， b 中前 v 个， c 中前 w 个数的并集相等。最小化 u + v + w 。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D为方便处理，把 a, b, c 均补全为所有数的并集（把缺少的部分加到数组末尾，即 n+1 处）。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF39

9、8D为方便处理，把 a, b, c 均补全为所有数的并集（把缺少的部分加到数组末尾，即 n+1 处）。所有数在 a, b, c 中最早出现的位置。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D为方便处理，把 a, b, c 均补全为所有数的并集（把缺少的部分加到数组末尾，即 n+1 处）。所有数在 a, b, c 中最早出现的位置。初始 u 设为最大，随着 u 的减小，一些数需要出现在 b 或 c 数组中，而且这样的数越来越多。标准算法CF364DCF392DCF392EhistoryCF39

10、8CCF380DCF232ECF396EarchitectREMOVECF398D为方便处理，把 a, b, c 均补全为所有数的并集（把缺少的部分加到数组末尾，即 n+1 处）。所有数在 a, b, c 中最早出现的位置。初始 u 设为最大，随着 u 的减小，一些数需要出现在 b 或 c 数组中，而且这样的数越来越多。对于二元组 (x, y) ，若那么 (x, y) 是无效的。(x1, y1) 满足 x x1 且 y y1 ，标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D删去所有无效二元组后

11、，将其按 x 递增排序，则 y 递减。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D删去所有无效二元组后，将其按 x 递增排序，则 y 递减。第 i 个的 x 和第 i + 1 个的 y 可组成一个合法方案。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D删去所有无效二元组后，将其按 x 递增排序，则 y 递减。第 i 个的 x 和第 i + 1 个的 y 可组成一个合法方案。用 set 来维护

12、这个二元组序列，一个二元组时，先其是否无效，否则删去变成无效的二元组。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D删去所有无效二元组后，将其按 x 递增排序，则 y 递减。第 i 个的 x 和第 i + 1 个的 y 可组成一个合法方案。用 set 来维护这个二元组序列，一个二元组时，先其是否无效，否则删去变成无效的二元组。用堆或 map 来存所有相邻二元组组成的合法方案，并取最小值。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Ea

13、rchitectREMOVECF398D删去所有无效二元组后，将其按 x 递增排序，则 y 递减。第 i 个的 x 和第 i + 1 个的 y 可组成一个合法方案。用 set 来维护这个二元组序列，一个二元组时，先其是否无效，否则删去变成无效的二元组。用堆或 map 来存所有相邻二元组组成的合法方案，并取最小值。【时间复杂度】O(n log n)。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DDeleting Substrings 33Source: Codeforces Round #230

14、 (Div. 1) Problem E数据范围1 n 400 , 0 |vi| 2000 , 1 wi 109。题目大意在一个长度为 n 的数组上进行若干次删除操作，每次可以删除一个子串 l, r ，得到的价值为 vrl+1 ，要求该子串满足|wi wi+1| = 1 ，对于所有 l i r 。2 wi wi+1 wi1 0 ，对于所有 l i r 。最大化得到的总价值。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析删去的子串需要满足的两个条件，可以发现其一定是先递增再递减，且相邻的两数差为 1。

15、标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析删去的子串需要满足的两个条件，可以发现其一定是先 递增再递减，且相邻的两数差为 1。考虑区间 DP，用 fi,j 表示将 i, j 区间内的所有数删除后能得到的最大价值。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析删去的子串需要满足的两个条件，可以发现其一定是先 递增再递减，且相邻的两数差为 1。考虑区间 DP，用 fi,j 表示将 i,

16、 j 区间内的所有数删除后能得到的最大价值。转移为枚举分割点 k ， fi,j = maxfi,k + fk+1,j。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析删去的子串需要满足的两个条件，可以发现其一定是先 递增再递减，且相邻的两数差为 1。考虑区间 DP，用 fi,j 表示将 i, j 区间内的所有数删除后能得到的最大价值。转移为枚举分割点 k ， fi,j = maxfi,k + fk+1,j。同时，还有一种转移，就是最后删去的区间以 i 为开头， 以 j 结束。标准算法CF36

17、4DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析删去的子串需要满足的两个条件，可以发现其一定是先 递增再递减，且相邻的两数差为 1。考虑区间 DP，用 fi,j 表示将 i, j 区间内的所有数删除后能得到的最大价值。转移为枚举分割点 k ， fi,j = maxfi,k + fk+1,j。同时，还有一种转移，就是最后删去的区间以 i 为开头， 以 j 结束。由于删除的子串可以明显地分为两个部分，均为公差为 1的等差数列标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF2

18、32ECF396EarchitectREMOVECF398D分析删去的子串需要满足的两个条件，可以发现其一定是先 递增再递减，且相邻的两数差为 1。考虑区间 DP，用 fi,j 表示将 i, j 区间内的所有数删除后能得到的最大价值。转移为枚举分割点 k ， fi,j = maxfi,k + fk+1,j。同时，还有一种转移，就是最后删去的区间以 i 为开头， 以 j 结束。由于删除的子串可以明显地分为两个部分，均为公差为 1的等差数列在枚举最高点位置 k 以及知道两端的值后，可以直接得到删去子串的长度。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF23

19、2ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 区间删到只剩下 ai 至 aj 的等差序列能得到的最大价值。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 区间删到只剩下 ai 至 aj 的等差序列能得到的最大价值。那么 f 的另一种转移为fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk)标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF39

20、6EarchitectREMOVECF398D用 gi,j表示把 i, j 区间删到只剩下 ai 至 aj 的等差序列能得到的最大价值。那么 f 的另一种转移为fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的转移为枚举满足|wi wk| = 1 且 |wk wj| + 1 = |wi wj| 的 k ，标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 区间删到只剩下 ai 至 aj 的等差序列能得到的最大价值。那么 f

21、的另一种转移为fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的转移为枚举满足|wi wk| = 1 且 |wk wj| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 区间删到只剩下 ai 至 aj 的等差序列能得到的最大价值。那么 f 的另一种转移为fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj w

22、k) g 的转移为枚举满足|wi wk| = 1 且 |wk wj| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j所有转移可以使用记忆化搜索，相用来实现。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 区间删到只剩下 ai 至 aj 的等差序列能得到的最大价值。那么 f 的另一种转移为fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的转移为枚举满足|wi wk| = 1 且 |w

23、k wj| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j所有转移可以使用记忆化搜索，相边界条件 fi,i = v1, gi,i = 0 。用来实现。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 区间删到只剩下 ai 至 aj 的等差序列能得到的最大价值。那么 f 的另一种转移为fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的转移为枚举满足|wi wk| = 1 且 |wk w

24、j| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j所有转移可以使用记忆化搜索，相边界条件 fi,i = v1, gi,i = 0 。用来实现。得到 f 数组后再进行一次简单的 DP 即可。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 区间删到只剩下 ai 至 aj 的等差序列能得到的最大价值。那么 f 的另一种转移为fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的转移为枚举满

25、足|wi wk| = 1 且 |wk wj| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j所有转移可以使用记忆化搜索，相边界条件 fi,i = v1, gi,i = 0 。用来实现。得到 f 数组后再进行一次简单的 DP 即可。【时间复杂度】O(n3)。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dhistory44Source: POJ Challenge Round 5 Problem D数据范围点数 n、操作数 m 3 105。题目大意在无支持两

26、种操作：添加一条连接某两点的边。询问某一过去时刻某两点是否连通。强制。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D由于只有加边和询问连通性，所以只需维护森林。在询问时求两点之间时间最迟的边即可。伪标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D由于只有加边和询问连通性，所以只需维护森林。在询问时求两点之间时间最迟的边即可。用数据结构优化刚才的，需要支持维护森林和求两点间的最大值，直接套用动态树 (Li

27、nk Cut Tree) 即可。数据范围较大，可能需要优化常数。伪标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D由于只有加边和询问连通性，所以只需维护森林。在询问时求两点之间时间最迟的边即可。用数据结构优化刚才的，需要支持维护森林和求两点间的最大值，直接套用动态树 (Link Cut Tree) 即可。数据范围较大，可能需要优化常数。【时间复杂度】O(m log n)。伪标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Earchitect

28、REMOVECF398D如果只要求询问当时的情况，那么并足矣，但如果要查询之前的情况呢？一种是 O(mn) 的了。的思想是全部存下来，但空间就标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D如果只要求询问当时的情况，那么并足矣，但如果要查询之前的情况呢？一种是 O(mn) 的了。的思想是全部存下来，但空间就但是，把每次修改前的结果存下来是不是太浪费了？很多信息是可以共用的。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Earchitect

29、REMOVECF398D如果只要求询问当时的情况，那么并足矣，但如果要查询之前的情况呢？一种是 O(mn) 的了。的思想是全部存下来，但空间就但是，把每次修改前的结果存下来是不是太浪费了？很多信息是可以共用的。由于路径压缩修改的信息较多，我们采用另一种并化：按秩合并。的优标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D这种优化即在并的根节点上再多一个值表示这个森林中的最大深度，由于并询问和深度有关，所以在合并时要尽可能减小森林的深度，把深度小的合并到深度大的即可。标准算法CF364DCF392D

30、CF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D这种优化即在并的根节点上再多一个值表示这个森林中的最大深度，由于并询问和深度有关，所以在合并时要尽可能减小森林的深度，把深度小的合并到深度大的即可。那么这样并的合并只修改了一个节点的父亲，而且这个节点的父亲一旦确定就再修改，所以可以直接下这个节点父亲确定的时间。而在询问时，若询问时间大于该父亲确定的时间，则说明此时这条边还没有连上，当前节点就 是当时的根。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectR

31、EMOVECF398D这种优化即在并的根节点上再多一个值表示这个森林中的最大深度，由于并询问和深度有关，所以在合并时要尽可能减小森林的深度，把深度小的合并到深度大的即可。那么这样并的合并只修改了一个节点的父亲，而且这个节点的父亲一旦确定就再修改，所以可以直接下这个节点父亲确定的时间。而在询问时，若询问时间大于该父亲确定的时间，则说明此时这条边还没有连上，当前节点就 是当时的根。这样就得到了一个可以处理历史询问的并了。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D但是再仔细想想这个并，觉得似乎这

32、已经不像并了，它维护的就是森林，但是这里的树的形态却和原来的树不同，但这没有。所以，忽略树的形态后，我们可以按我们想要的方式合并两棵树，而不一定要按给出的边合并。 同时，按秩合并就像启发式合并，有效地使树高降低到了 log n 的级别。也就是说，从最开始的算法出发，用启发式合并来维护森林，也可以到达这里。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D但是再仔细想想这个并，觉得似乎这已经不像并了，它维护的就是森林，但是这里的树的形态却和原来的树不同，但这没有。所以，忽略树的形态后，我们可以按我们

33、想要的方式合并两棵树，而不一定要按给出的边合并。 同时，按秩合并就像启发式合并，有效地使树高降低到了 log n 的级别。也就是说，从最开始的算法出发，用启发式合并来维护森林，也可以到达这里。【时间复杂度】O(m log n)。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每个点维护其第 2i 个祖先，以及这段路径上的最迟的合并时间。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每个点维护其第

34、 2i 个祖先，以及这段路径上的最迟的合并时间。在后启发式合并该数组。时利用该数组倍增求出lca，以及路径上最迟的时间。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每个点维护其第 2i 个祖先，以及这段路径上的最迟的合并时间。在后启发式合并该数组。时利用该数组倍增求出lca，以及路径上最迟的时间。【时间复杂度】O(n log2 n)。数据不够强，没把这个卡掉。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOV

35、ECF398D每个点维护其第 2i 个祖先，以及这段路径上的最迟的合并时间。在后启发式合并该数组。时利用该数组倍增求出lca，以及路径上最迟的时间。【时间复杂度】O(n log2 n)。数据不够强，没把这个卡掉。用表每个节点不同时间的根。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每个点维护其第 2i 个祖先，以及这段路径上的最迟的合并时间。在后启发式合并该数组。时利用该数组倍增求出lca，以及路径上最迟的时间。【时间复杂度】O(n log2 n)。数据不够强，没把这个卡掉。用表每个节点不同

36、时间的根。在后启发式合并，只修改小树所有点的根。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每个点维护其第 2i 个祖先，以及这段路径上的最迟的合并时间。在后启发式合并该数组。时利用该数组倍增求出lca，以及路径上最迟的时间。【时间复杂度】O(n log2 n)。数据不够强，没把这个卡掉。用表每个节点不同时间的根。在后启发式合并，只修改小树所有点的根。时两点当时的根是否相同。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Earchit

37、ectREMOVECF398D每个点维护其第 2i 个祖先，以及这段路径上的最迟的合并时间。在后启发式合并该数组。时利用该数组倍增求出lca，以及路径上最迟的时间。【时间复杂度】O(n log2 n)。数据不够强，没把这个卡掉。用表每个节点不同时间的根。在后启发式合并，只修改小树所有点的根。时两点当时的根是否相同。【时间复杂度】O(n log n)。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DTree and Array 5题目大意对于一棵点数为 n 的带若有一条连接 x, y(x y) 的

38、。为 z 的边，则给 tx, tx+1, . . . , ty1, ty 都加上 z 。y i=x若 x, y(x yti ，则称 x, y 为一对 good) 在树上的距离 =pair 。 n要求构造这样一棵树，使其 good pair 的数量至少为。25Source: Codeforces Round #233 (Div. 1) Problem C数据范围5 n 105，为不超过 105 正整数。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D(4, 5), (5, 6), (5, 7) 为 goo

39、d pair 。样例CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D先考虑怎么构造一对 good pair 。构造一对CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D先考虑怎么构造一对 good pair 。以 4 个点为例， 1 3 4 2 的链，t1 + t2 = z1,3 2 + z2,4 ,dist1,2 = z1,3 + z3,4 + z2,4。构造一对CF364DCF392DCF392Ehistory

40、CF398CCF380DCF232ECF396EarchitectREMOVECF398D先考虑怎么构造一对 good pair 。以 4 个点为例， 1 3 4 2 的链，t1 + t2 = z1,3 2 + z2,4 ,dist1,2 = z1,3 + z3,4 + z2,4。设为 1 即若要两者相等，则 z3,4 = z1,3 。将三条边的可得到一对 good pair 。构造一对CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D构造顺着刚才的想法下去，如果要构造 1 号点和其他很多点的 good

41、pair ，那么只需套用上述结构，从 1 连出去很多条链，重新计算一下。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D构造顺着刚才的想法下去，如果要构造 1 号点和其他很多点的 good pair ，那么只需套用上述结构，从 1 连出去很多条链，重新计算一下。n对 good pair 。1这样可以构造出3CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D构造顺着刚才的想法下去，如果要构造 1 号点和其他很多点的

42、good pair ，那么只需套用上述结构，从 1 连出去很多条链，重新计算一下。n对 good pair 。1这样可以构造出3但这样的浪费比较多，如果合并一些，使其均摊用两条边构成一对大概就能满足要求了。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D标准算法n2设 m =。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dn设 m =。2由于题目要求的是至少 m 对，所以考虑把点分两组，其中一组 (1 m) 用

43、来构造树上，另一组 (m + 1 n) 形成 good pair 。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dn设 m =。2由于题目要求的是至少 m 对，所以考虑把点分两组，其中一组 (1 m) 用来构造树上，另一组 (m + 1 n) 形成 good pair 。一个前半部分挂一个后半部分的点， i 到 m + i 的给后半部分的 t 数组造成等差的影响，而 (1 m) 之间的半部分有影响。后标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232E

44、CF396EarchitectREMOVECF398Dn设 m =。2由于题目要求的是至少 m 对，所以考虑把点分两组，其中一组 (1 m) 用来构造树上，另一组 (m + 1 n) 形成 good pair 。一个前半部分挂一个后半部分的点， i 到 m + i 的给后半部分的 t 数组造成等差的影响，而 (1 m) 之间的后半部分有影响。构造后半部分相邻两个组成一对 good pair ，为方便构造， 可直接把前半部分连成一条链。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dn设 m =。

45、2由于题目要求的是至少 m 对，所以考虑把点分两组，其中一组 (1 m) 用来构造树上，另一组 (m + 1 n) 形成 good pair 。一个前半部分挂一个后半部分的点， i 到 m + i 的给后半部分的 t 数组造成等差的影响，而 (1 m) 之间的后半部分有影响。构造后半部分相邻两个组成一对 good pair ，为方便构造， 可直接把前半部分连成一条链。具体奇偶两种情况讨论。其中偶数会多出来一对 (n 2, n) ，而奇数可以把 n 挂到 n 1 上（观察样例），形成一对 (n 2, n) 。标准算法CF364DCF392DCF392EhistoryCF398CCF380DCF2

46、32ECF396EarchitectREMOVECF398Dm + in 1n. . .111 2m2i1/ . . . 3 / m 1 1/ m im+in-2n-1ntn+1-m-i321m,n+1+1+1+1m-1,n-1+1+1+1m-2,n-2+1+1 k ,m+k+1偶数CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dm + in 2n 1 1/ n. . .111 2m2i1/ . . . 3 / m 1 2/ mim+in-3n-2n-1ntn-m-i3221n-1,n+1+1m,n-1

47、+1+1+1+1m-1,n-2+1+1+1m-2,n-3+1+1 k ,m+k+1奇数CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DSereja and Cinema 66Source: Codeforces Round #223 (Div. 1) Problem D数据范围1 n 105。题目大意一排 n 个座位，两端和相邻座位间都有槽（比如放水杯的）。每个人就坐后会占用与其相邻未占用的槽。给出每个人是第几个就坐的（0 表示未知），求每个人都能得到至少一个槽的方案数 mod 109 + 7 的结果。

48、CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D考虑什么时候有人会没有槽，就是他就坐时两边都有人。DPCF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D考虑什么时候有人会没有槽，就是他就坐时两边都有人。所以，为了保证每个人都有槽，在边界上的人应该最后坐下。而去掉边界上的人，缩小规模后又变成原。DPCF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectRE

49、MOVECF398D考虑什么时候有人会没有槽，就是他就坐时两边都有人。所以，为了保证每个人都有槽，在边界上的人应该最后坐下。而去掉边界上的人，缩小规模后又变成原可以发现，某一时刻已就坐的人应该是一段区间。DPCF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D考虑什么时候有人会没有槽，就是他就坐时两边都有人。所以，为了保证每个人都有槽，在边界上的人应该最后坐下。而去掉边界上的人，缩小规模后又变成原可以发现，某一时刻已就坐的人应该是一段区间。然后就可以使用 DP， fi,j 表示已就坐 i 个人，且区间的开头是 j 的方案数。DPCF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREM