2017-Sp296-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
=== chenjb ===
只输了dls一个题还行，主要是剩下的题太牛逼了，如果跟着榜，估计K能出，然后D会攻得更坚决一点，C太高论了，如果有榜估计根本不会花时间在上面。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：按题意模拟。

 * B：

 * C：

 * D：

 * E：

 * F：来有限个人相当于+k，来无限个人相当于*2。对于询问2，先得到在当时的下标，然后得到它之后附加了哪些操作，用线段树维护操作。对于询问3，拿出所有*2的位置，在log的时间里可以找到它属于哪两个*2之间，再用log时间二分。

 * G：显然从S出发能走的点一定是能到达t的点，在这个基础上每步贪心走，一旦走到过访问过的点就too long。

 * H：偶数一定是小n/2匹配大n/2，奇数要枚举中间的那个人在较小侧还是较大侧。

 * I：最小直径生成树：找到绝对中心后抠最短路树。

 * J：注意到区间之间关系是树的形态，f[i][j]表示i子树最长的链上取了j的最大值，显然f[i]的逐差是递减的，考虑长链剖分，轻儿子并入重儿子，直接归并加进去即可。父节点在最后直接插入，用multiset维护每个点的逐差数组。


 * K：考虑对两棵树建点分治树，设i，j在两棵点分治树的kca分别为L1,L2，则T1.dis(i,j)+T2.dis(i,j)=T1.dis(i,L1)+T1.dis(j,L1)+T2.dis(i,L2)+T2.dis(j,L2)。由于i只有log个祖先，所有只有log^2^种不同的（L1，L2）对。枚举之后，就是要找到j，满足lca恰好为L1，L2。考虑放宽条件，只满足j的祖先为L1，L2且j不为i。显然，答案一定被我们枚举到了，而且不严格满足lca的计算结果会偏大，所以这个条件下取出的最小值依旧是答案。所以我们有nlog^2^个三元组(L1,L2,T1.dis(x,L1)+T2.dis(x,L2))，我们要做的就是对于每个L1，L2，找到最小值和次小值（用来给最小值做贡献）。为了避免排序的log，我们将所有点和长度插入对应的L1的vector中，并对T2维护每个点的所有的祖先和距离的vector，枚举每个L1之后，再枚举这个L1下的每个点的L2，并插入L2对应的全局变量，然后再取出贡献，每个L1处理完之后再清空全局变量。

流水账

chenjb

只输了dls一个题还行，主要是剩下的题太牛逼了，如果跟着榜，估计K能出，然后D会攻得更坚决一点，C太高论了，如果有榜估计根本不会花时间在上面。

oipotato

subconscious

题解

A：按题意模拟。
B：
C：
D：
E：
F：来有限个人相当于+k，来无限个人相当于*2。对于询问2，先得到在当时的下标，然后得到它之后附加了哪些操作，用线段树维护操作。对于询问3，拿出所有*2的位置，在log的时间里可以找到它属于哪两个*2之间，再用log时间二分。
G：显然从S出发能走的点一定是能到达t的点，在这个基础上每步贪心走，一旦走到过访问过的点就too long。
H：偶数一定是小n/2匹配大n/2，奇数要枚举中间的那个人在较小侧还是较大侧。
I：最小直径生成树：找到绝对中心后抠最短路树。
J：注意到区间之间关系是树的形态，f[i][j]表示i子树最长的链上取了j的最大值，显然f[i]的逐差是递减的，考虑长链剖分，轻儿子并入重儿子，直接归并加进去即可。父节点在最后直接插入，用multiset维护每个点的逐差数组。
K：考虑对两棵树建点分治树，设i，j在两棵点分治树的kca分别为L1,L2，则T1.dis(i,j)+T2.dis(i,j)=T1.dis(i,L1)+T1.dis(j,L1)+T2.dis(i,L2)+T2.dis(j,L2)。由于i只有log个祖先，所有只有log²种不同的（L1，L2）对。枚举之后，就是要找到j，满足lca恰好为L1，L2。考虑放宽条件，只满足j的祖先为L1，L2且j不为i。显然，答案一定被我们枚举到了，而且不严格满足lca的计算结果会偏大，所以这个条件下取出的最小值依旧是答案。所以我们有nlog²个三元组(L1,L2,T1.dis(x,L1)+T2.dis(x,L2))，我们要做的就是对于每个L1，L2，找到最小值和次小值（用来给最小值做贡献）。为了避免排序的log，我们将所有点和长度插入对应的L1的vector中，并对T2维护每个点的所有的祖先和距离的vector，枚举每个L1之后，再枚举这个L1下的每个点的L2，并插入L2对应的全局变量，然后再取出贡献，每个L1处理完之后再清空全局变量。

附加文件

1.png by chenjb