2017-Sp328-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== chenjb ===
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：推式子计算。

 * B：奇数直接L型，偶数，2显然无解，否则把n-1的构造加上(2,2)。

 * C：枚举对称轴上有几个点，最多sqrt个，两边对称是限定数量的拆分数，可以nsqrtn求，dp。

 * D：只有k个起点有用，k^2^求出后缀数组，直接算。

 * E：统计每种信件涉及到的最深回信个数，求得最小信件数比较即可。

 * F：预先计算大小为i的联通块里，2^i^个子树出现次数的和，容斥计算之后除以贡献即可。

 * G：搞个栈随便匹配。

 * H：二分最大值那个人分到多少。

 * I：询问1 1 2 2...n/2 n/2，从前往后扫，每次遇到重复数字就能断定一个数组，这样做一遍就能确定一半的数字，最多再做一次，问下第n个数组。

 * J：对于a到b，显然a要先达到他们之间最高的管子的高度，接下来就是这根管子到b这一段再做相似的事情，将管子高度从小到大排序后，建kruskal重构树，a到b的答案就是b往两者lca跳的过程中，每一个a方向的子树*当前点的高度值，注意到a另一边有可能漏过去的水也会被这样统计进去，所以是正确的；用跳表或者动态链分治维护都可以。

 * K：

 * L：先分成每一块42连红色的边，再分成每一块42*42连蓝色边，再连绿色边(42*42*42>n)。

流水账

chenjb

oipotato

subconscious

题解

• A：推式子计算。
• B：奇数直接L型，偶数，2显然无解，否则把n-1的构造加上(2,2)。
• C：枚举对称轴上有几个点，最多sqrt个，两边对称是限定数量的拆分数，可以nsqrtn求，dp。
• D：只有k个起点有用，k²求出后缀数组，直接算。
• E：统计每种信件涉及到的最深回信个数，求得最小信件数比较即可。
• F：预先计算大小为i的联通块里，2ⁱ个子树出现次数的和，容斥计算之后除以贡献即可。
• G：搞个栈随便匹配。
• H：二分最大值那个人分到多少。
• I：询问1 1 2 2...n/2 n/2，从前往后扫，每次遇到重复数字就能断定一个数组，这样做一遍就能确定一半的数字，最多再做一次，问下第n个数组。
• J：对于a到b，显然a要先达到他们之间最高的管子的高度，接下来就是这根管子到b这一段再做相似的事情，将管子高度从小到大排序后，建kruskal重构树，a到b的答案就是b往两者lca跳的过程中，每一个a方向的子树*当前点的高度值，注意到a另一边有可能漏过去的水也会被这样统计进去，所以是正确的；用跳表或者动态链分治维护都可以。
• K：
• L：先分成每一块42连红色的边，再分成每一块42*42连蓝色边，再连绿色边(42*42*42>n)。