CF1827

cf1827 · 浏览次数 : 5

小编点评

## CF1827A Counting Orders 代码解析 **思路 1:利用 ST 表** - 利用 ST 表维护每个点作为右端点,最靠近的左端点。 - 对于每个端点求出最小的合法串的长度。 - 递推式求解最终答案。 **思路 2:逆序处理** - 利用每个中心更新没有更新过的点。 - 考虑使用链表或者并查集维护。 - 设最后的结果为每个端点最小的子树大小。 - 计算最终答案。 **思路 3:维护虚树并树上差分** - 利用 DSU on tree 进行虚树构建。 - 利用树上差分求解最终答案。 **代码分析** - 代码使用了 **ST 表** 和 **并查集** 等数据结构来维护和计算子树大小。 - 在计算子树大小时,使用了 **递推式** 的方法。 - 使用了 **动态规划** 和 **树链剖分** 等算法来优化代码性能。 **优缺点** - **思路 1** 是最直接的算法,但效率可能较低。 - **思路 2** 可以通过逆序处理降低时间,但需要额外的空间来维护并查集。 - **思路 3** 是一种非常高效的算法,但需要对虚树进行构建。 **总结** CF1827A 问题中使用了多种数据结构和算法来解决问题,代码简洁易懂,但由于使用了 **ST 表** 和 **并查集** 等数据结构,效率可能相对低。

正文

CF1827

A. Counting Orders

简单计数。

两个都排序,双指针维护一下 a[i]b[p] 的位置(a[i] <= b[p])。

那么方案数 \(\times (p - i)\)

提交:https://codeforces.com/contest/1827/submission/211387552

C. Palindrome Partition

回文好题

考虑利用 Manacher 求出每一个偶数的回文串。

参考:算法学习笔记(13): Manacher算法 - jeefy - 博客园

观察可以发现:每一个合法的串都可以被划分为多个最小的合法串,并且划分方法是唯一的。

所以考虑如下:

我们需要维护出每一个点作为右端点,最靠近的左端点。

这等价于求出满足 \(i + p[i] \ge x\),求 \(\max i\)

然后,设上面对于端点 \(i\) 求出来的结果为 \(g_i\)

得出最终的递推式:

\[f_i = \begin{cases} 0 &,g_i = 0 \\ f_{i - g_i} + 1 &, g_i \ne 0 \end{cases} \]

其中 \(f_i\) 表示以 \(i\) 结尾的合法的串的个数。

最终的答案为 \(\sum f_i\)

提交:Submission #211396680 - Codeforces

D. Two Centroids

性质好题

重心有如下性质:

  • 最大子树大小 \(\le \lfloor \frac n2 \rfloor\)

  • 新增一个叶子节点,重心最多变化一条边。

  • 重心至多有两个。

那么我们考虑每次加入一个点对于原来重心 \(c\) 的影响,并设当前最小的子树大小为 \(mx\)

  • 如果加入的叶子节点在 \(c\) 的子树 \(t\) 内。更新 \(t\) 的大小,并更新 \(mx\)。如果此时 \(mx \ge \lfloor \frac n2 \rfloor + 1\),那么重心向 \(t\) 移动。并且此时 \(mx\) 更新为 \(\lfloor \frac n2 \rfloor\)不考虑,把图画出来就明白了

  • 由于我们不可能动态维护以每一个重心为根,所以还要考虑其祖先的情况(同理)。

然后就是如何找 \(t\) 的问题。有两种解决方案:

  • 无论如何首先可以通过 dfn 序判断是否在其子树内。

    • 方案1:利用倍增的方法跳祖先。空间复杂度 \(O(n \log n)\),单次 \(O(\log n)\)

    • 方案2:利用 dfn 区间,对于每一个节点保存其子节点的 dfn,每次二分找到叶子的 dfn 所在的区间即可。(我用的这种方法)空间 \(O(n)\),单词 \(O(\log n)\)

  • 实测第二种要快一点点(也快不了多少,主要是常数够好)

提交:Submission #211401150 - Codeforces

E. Bus Routes

差点没用 dlang 卡过去

思路1

考虑更严的限制(等价):叶子节点间两两可以在两次内到达。

于是考虑对于每一个叶节点,求出其能到达的最高的祖先 \(high(x)\)

也就是求一个 LCA 即可。

那么满足条件的必要条件是每一对 \(high(x), high(y)\) 满足祖先/子节点关系。

如果不是,那么至少需要三条路径。

如果满足上述条件,那么所有的 \(high\) 满足在一条链上。

那么可以通过 dfn 序判断。

这并不充分。

考虑找到最低那个 \(high(x)\),并以 \(high(x)\) 作为根。

此时重新求一次 \(high\),如果所有的 \(high\) 都为 \(high(x)\),那么就是 \(ok\) 的,否则,如果有 \(high(y) \ne high(x)\),那么 \(x, y\) 不可达。

不要写倍增求 LCA,利用 ST表 \(O(n \log n) \sim O(1)\) 或者 树链剖分 \(O(n) \sim O(\log n)\) ,甚至是离线 \(O(n)\) 求。倍增太慢了,dlang 卡不过去。

思路2

参考 Alex_Wei 的博客:https://www.luogu.com.cn/blog/_post/575397

利用 DSU on tree

思路3

维护虚树并树上差分。非常的高效。

参考:CF1827E Bus Routes - Kubic 的博客 - 洛谷博客

与CF1827相似的内容: