2017-Sp187-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门yzc上机'''B1y11'''，cjb上机'''F1y20'''，yzc上机'''D1y25'''，cjb上机'''G1y45'''，三人讨论了一下，cjb给了个结论，yzc上机'''L1y73'''，sub上机'''J1y86'''，cjb和yzc讨论H，yzc上机'''H2y100'''，cjb上机'''C2y112'''，三人一起讨论I，yzc上机'''I3y163'''，然后三人开始讨论A，yzc上机刚A，GG了。
== 总结 ==
=== chenjb ===
刚了两小时的A，硬核点分治不太擅长啊.....
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：因为选定的集合点不区分方案，如果只考虑每个人距离不超过L的组合数，则可能存在重复统计。考虑每个点只统计这个点可以作为集合点，但父亲不行的方案，重复的方案只会在深度最浅的点被统计。于是剩下的问题就是一个点出发距离不超过L的点的个数和两个相邻点距离均不超过L的点的个数。第一个问题用点分治树统计即可，后者等价于统计和两点之间的边（设距离为x）的中点距离不超过L-x/2的点的个数，将所有边长倍长之后即相当于第一个问题。跳表在深度比较深的树上表现不佳，可使用树链剖分求lca得到两点距离。
         PS：对于第二种方法，一个更优秀的做法是去掉子树中距离为(L-x,L]的点的贡献，用主席树即可实现，这样就不需要倍长所有边，常数较小。

 * B：枚举n的约数检查即可。

 * C：枚举长度不超过9的所有子串。

 * D：显然横竖每一刀都是切出有k个点的块，所以切法基本唯一，切完之后check即可

 * E：

 * F：不是回文串则1，为aaaaa,ababa,aabaa三种之一则-1，否则2。

 * G：所有数字mod (A+B)，然后若A=B，奇偶判断；若A>B，枚举第一步交换先手规约到A<B；A<B时若没有有效操作则先手败，否则存在一步之内控出一个B不能取而A能取得块，就先手胜，也就是存在x<B或者x>=2*A。

 * H：按花费从大到小，给每支青蛙安排没有花费的线路，安排方式是每次从终点往回跳，每次跳尽量远的石头，如果一条安全线路都不存在则让花费最小的青蛙去把这k个石头都解决掉，其他人一次跳到终点。

 * I：枚举每个箱子，计算假如第一次选择这个箱子，你的步数是多少，计算方法是枚举这个箱子里的颜色，计算仍然包含这个颜色的箱子，步数最少的是谁，将所有颜色的步数从大到小排序，排名第i个的贡献是步数+i-1。

 * J：每个点取边权最小的边即可，可以证明永远是对的。

 * K：考虑一个已经完成移动的点集S，最优划分显然是分成连续的几个区间，我们将最优划分的每个区间内的点集补满，则代价不变，但是每个划分都是连续的。于是S的最优值是所有包含点集S的集合T的代价的最小值，其中，我们定义集合T的代价为(a-b)*段数+b*|T|，其中，段数即为T中连续的段的数量。我们将所有点坐标减去d，每次操作即为不动或是+2d。为了方便讨论，下面将用d来代替2d。显然，不满足条件的集合T满足存在一个原来有点的位置x，x和x+d都不在T中。考虑状压DP，为了满足条件，显然我们需要保存最近的d个位置的状态，转移也很显然。但是这在d大的时候无法进行。于是当d较大时，我们采取另一种方法。因为位置上填数字的限制只发生在模d同余的位置之间，于是我们按照模d的结果依次处理所有位置。处理方式为，先枚举模d余0的位置的所有状态，然后从1依次推到d-1，再枚举d-1的最终状态来计算模d余0的位置的贡献。这里有一个小的实现技巧，当从i推到i+1时，假设当前在推第j*d+i+1个位置，则当前状态S的低j-1位表示模d余i+1的状态，剩余表示i的状态，推到S‘状态之后，低j位表示i+1的状态，剩余表示i的状态。第一部分d的阈值取20时，第二部分的状态位数大约是11，可以通过此题。

 * L：暴力扫描每一个矩形里的每个点是O(n^3^)，统计即可，注意常数。

流水账

出门yzc上机B1y11，cjb上机F1y20，yzc上机D1y25，cjb上机G1y45，三人讨论了一下，cjb给了个结论，yzc上机L1y73，sub上机J1y86，cjb和yzc讨论H，yzc上机H2y100，cjb上机C2y112，三人一起讨论I，yzc上机I3y163，然后三人开始讨论A，yzc上机刚A，GG了。

总结

chenjb

刚了两小时的A，硬核点分治不太擅长啊.....

oipotato

subconscious

题解

A：因为选定的集合点不区分方案，如果只考虑每个人距离不超过L的组合数，则可能存在重复统计。考虑每个点只统计这个点可以作为集合点，但父亲不行的方案，重复的方案只会在深度最浅的点被统计。于是剩下的问题就是一个点出发距离不超过L的点的个数和两个相邻点距离均不超过L的点的个数。第一个问题用点分治树统计即可，后者等价于统计和两点之间的边（设距离为x）的中点距离不超过L-x/2的点的个数，将所有边长倍长之后即相当于第一个问题。跳表在深度比较深的树上表现不佳，可使用树链剖分求lca得到两点距离。

PS：对于第二种方法，一个更优秀的做法是去掉子树中距离为(L-x,L]的点的贡献，用主席树即可实现，这样就不需要倍长所有边，常数较小。

B：枚举n的约数检查即可。
C：枚举长度不超过9的所有子串。
D：显然横竖每一刀都是切出有k个点的块，所以切法基本唯一，切完之后check即可
E：
F：不是回文串则1，为aaaaa,ababa,aabaa三种之一则-1，否则2。
G：所有数字mod (A+B)，然后若A=B，奇偶判断；若A>B，枚举第一步交换先手规约到A=2*A。
H：按花费从大到小，给每支青蛙安排没有花费的线路，安排方式是每次从终点往回跳，每次跳尽量远的石头，如果一条安全线路都不存在则让花费最小的青蛙去把这k个石头都解决掉，其他人一次跳到终点。
I：枚举每个箱子，计算假如第一次选择这个箱子，你的步数是多少，计算方法是枚举这个箱子里的颜色，计算仍然包含这个颜色的箱子，步数最少的是谁，将所有颜色的步数从大到小排序，排名第i个的贡献是步数+i-1。
J：每个点取边权最小的边即可，可以证明永远是对的。
K：考虑一个已经完成移动的点集S，最优划分显然是分成连续的几个区间，我们将最优划分的每个区间内的点集补满，则代价不变，但是每个划分都是连续的。于是S的最优值是所有包含点集S的集合T的代价的最小值，其中，我们定义集合T的代价为(a-b)*段数+b*|T|，其中，段数即为T中连续的段的数量。我们将所有点坐标减去d，每次操作即为不动或是+2d。为了方便讨论，下面将用d来代替2d。显然，不满足条件的集合T满足存在一个原来有点的位置x，x和x+d都不在T中。考虑状压DP，为了满足条件，显然我们需要保存最近的d个位置的状态，转移也很显然。但是这在d大的时候无法进行。于是当d较大时，我们采取另一种方法。因为位置上填数字的限制只发生在模d同余的位置之间，于是我们按照模d的结果依次处理所有位置。处理方式为，先枚举模d余0的位置的所有状态，然后从1依次推到d-1，再枚举d-1的最终状态来计算模d余0的位置的贡献。这里有一个小的实现技巧，当从i推到i+1时，假设当前在推第j*d+i+1个位置，则当前状态S的低j-1位表示模d余i+1的状态，剩余表示i的状态，推到S‘状态之后，低j位表示i+1的状态，剩余表示i的状态。第一部分d的阈值取20时，第二部分的状态位数大约是11，可以通过此题。
L：暴力扫描每一个矩形里的每个点是O(n³)，统计即可，注意常数。

附加文件

1.png by chenjb