csp-s 模拟 12

csp-s模拟12

T 小 h 的几何

whk

我能说什么呢...

T 小 w 的代数

仙人掌，DP，计数题

本题部分分较有启发意义

• 考虑是一棵树怎么做
  注意到 \(n\) 比较小，直接想想比较暴力的做法，可以用 \(O(n^2)\) 的复杂度枚举起点和终点，而由于是一棵树，两点之间的路径是唯一的，并且本题要求点集不重，所以这样就变为了序列问题，即给定一个序列，求给定起始、最终数的上升序列个数，这样就得到了 \(O(n^4)\) 的做法。注意到枚举终点是一个比较傻的行为，这浪费掉了一些性质，即 \(DP\) 的继承，所以枚举起点然后 bfs（或dfs） 全局转移。时间复杂度为 \(O(n^3)\)。

• 考虑是一棵基环树怎么做
  回到上一部份做法，暴力枚举起点和终点，然后发现当起点和终点都在同一棵子树内时和上一档无差，而起点和终点不在同一棵子树时路径变得不唯一，即在环上有分叉，对于现在这个做法当然也就是多枚举一遍的事，但是注意两次转移都会有不选环上其他的点直接选终点的转移，而这样的转移实际上是多转移了一次，用环上起点转移一次减掉即可。还是想想怎么 bfs 优化，注意到从路径本质上是 一棵子树 \(\to\) 环 \(\to\) 另一棵子树，在进入另一棵子树前将两条路径的状态合并即可。具体的，先枚举起点，当 bfs 到环上时先将环上的点全部转移完毕再继续，关于转移可以正反跑两圈，每到达一个点就将 \(O(n)\) 状态记录下来，这样一个点就有正反两个状态，考虑合并，注意到包含了环上起点的状态两次，直接 \(O(n)\) 合并后 \(O(n)\) 减掉即可。
  这样时间复杂是 \(O(n^3)\)

• 考虑是一颗仙人掌怎么做
  将环看作点仙人掌本质上是一棵树，可以套用上面的做法，而环上就特殊转移（将环上的点两遍转移完后再进行下一步）就行。具体的，先枚举起点，点转移是平凡的，当到一个环上时和处理基环树一样正反转移两次、合并状态、去重即可。
  时间复杂为 \(O(n^3)\)。

T 小 y 的数论

结论题，树论，st表

• 结论 1：两个点集合并后直径的两个端点一定是属于原来两个点集直径共四个点中的。
  证明：考虑反证法以及 dfs 找直径。

• 结论 2 ：定义一个点集选 \(k\) 个点构成虚树的边权最大值的这 \(k\) 个点为前 \(k\) 优点，两个点集合并后的前 \(k\) 优点一定是属于原来两个点集的前 \(k\) 优点的。
  证明：和结论 3 一起证明。

• 结论 3：前 \(k\) 优点一定是包含前 \(k-1\) 优点的。
  证明：先考虑对于一个点集怎么怎么获得这前 \(k\) 优点，首先这个点集的直径一定是会被选入的，然后钦定直径的一个端点为根对这个点集进行长链剖分，（算上重链顶部的轻链）从大到小选择前 \(k-2\) 大即可，依据贪心这样肯定是对的。这个地方就能证明出结论 3 了。现在考虑对于两个点集的合并，根据上述方法，新点集的直径一定是会被选择的，如果 k>2 ，则接下来的两条边一定是优先选择以原直径为端点的长链，那么剩下的链就变成了原来的形态了（原两个点集的重链），则剩下的一定在这些中选择，证毕。

根据结论 2、3，我们能得到一个显然的线段树做法，即每个区间维护这个区间的前 \(k_{max}\) 优点，合并就长剖按照上述方法即可（不懂题解为什么能 \(O(n)\)，不排序就能求前 k 长链吗？求教教）。时间复杂度为 \(O((n+q)lognk_{max}logk_{max})\) ，并且这个做法常数巨大会 GG。考虑优化，注意到合并两个点集的前 k 优和区间取最小值、最大值、\(\gcd\) 是一个道理（即可重复贡献类问题），所以可以 \(st\) 优化。具体的每 \(k_{max}\) 分成一个块，共有 \(O(\frac{n}{k_{max}})\) 块，预处理是 \(O(nlogk_{max}log\frac{n}{k_{max}})\) 可以接受。而查询可以将散块合并成一个块再和 st 表中的两个块合并即可，这部分的时间复杂度为 \(O(qklogk)\) 的。

但是这样的话可能还是不太好过，可以将 st 表中的 k 个点有序放置，这样合并的时候就能归并省去一次排序，然后建虚树时用单调栈能再省去一次排序，这样就能过了。
总时间复杂度为 \(O(nlognlogk+qklogk)\)。

T 小j 的组合

签到题

以直径的两个端点分别作为起点和终点即可，证明略。

时间复杂度 \(O(n)\)。