题解
P5018 [NOIP2018 普及组] 对称二叉树 题解
这是一篇关于求解最大对称子树节点数的指针解题总结。文章指出虽然暴力枚举看似 $O(n^2)$,但在处理满二叉树场景下,其实际复杂度可优化至 $O(n\log n)$,从而轻松通过 $10^6$ 的数据规模。作者分享了自己通过暴力迭代成功 AC 的体验,并简要复述了题目背景及优化分析过程。
ARCHIVE · 静默记录
这是一篇关于求解最大对称子树节点数的指针解题总结。文章指出虽然暴力枚举看似 $O(n^2)$,但在处理满二叉树场景下,其实际复杂度可优化至 $O(n\log n)$,从而轻松通过 $10^6$ 的数据规模。作者分享了自己通过暴力迭代成功 AC 的体验,并简要复述了题目背景及优化分析过程。
本文分享了一道原题设为拓扑排序但实际使用广度优先搜索(BFS)进行暴力求解的解题经验。文章详细讲解了如何通过模拟手动计算分数的加减乘除及约分,并列出相关代码片段。作者指出利用乘法分配律将多股水流分开计算最后求和即可避免复杂依赖关系。最终代码虽因超时卡点(`unsigned long long`)仅获 80 分,但因测试数据较水而 AC。文末还提及了非标准类型 `__int128` 在新竞赛中的应用。
本题考验图论思维,核心是将零件生产转化为图中两点间路径长度问题。若 A 生产第 L 阶段零件需经过 B 生产 L-1 阶段,则实质取决于 A、B 间是否存在长度为 L 的路径。由于可行路径长度具有奇偶性规律(存在长度 X 的路径必存在长度 X+2n 的路径),只需分别记录从起点到各点的奇数和偶数最短路径,通过 BFS 求解后,若最短路径小于等于 L 且奇偶性匹配,则输出 Yes。