ACM竞赛解题策略：能量采集、移动过程与圆的包含关系

"电子科技大学第二十一届ACM程序设计竞赛初赛题解" 这篇文档包含了三个编程竞赛题目及其解法，分别涉及动态规划、数据结构（笛卡尔树）以及几何算法（圆的包含关系处理）。以下是这三个问题的详细解析： ### A. 能量采集 这是一个基于动态规划的问题。目标是计算在给定的二维网格中，当容器收集到$K$个能量A时的方案数。题目中提到的状态$f(i, j, p)$表示当前位于位置$(i, j)$，且队列中连续的能量A有$p$个。状态转移方程为： 1. 当$p=0$时，$f(i, j, 0)=\binom{i+j-2}{i-1}$，这表示到达$(i, j)$的方案数。 2. 如果当前位置$(i, j)$为能量A，那么$f(i, j, p+1)$可以通过从$(i-1, j, p)$和$(i, j-1, p)$转移得到，即$f(i, j, p+1)=f(i-1, j, p)+f(i, j-1, p)$。 最终的答案是所有位置$(i, j)$满足$f(i, j, K)$的方案数乘以从该位置返回起点的路径数，然后除以所有可能路径的数量。时间复杂度为$\mathcal{O}(nmK)$。 ### B. 考虑移动过程 这个问题涉及到最大值分治和笛卡尔树。在移动过程中，每次移动都需要确保当前强度可以覆盖接下来的路径。通过建立笛卡尔树，可以方便地处理这个问题。对于每个询问，我们需要找到第一个大于给定强度$v$的边，其子树的贡献就是答案。使用树上倍增或树链剖分等数据结构可以高效地完成查询。总的时间复杂度为$O(n\log n)$。 ### C. 往日重现 这是关于圆的包含关系处理的几何问题。圆之间的关系可以构建成一棵树，查询两个点所属最小圆在树上的距离。通过扫描线算法，可以处理圆的上半圆和下半圆的包含关系。当扫描线遇到圆的左边界时，更新包含关系并记录最近的半圆。如果遇到上半圆，更新该圆的父圆；如果遇到下半圆，更新其父圆的父圆。对于查询点，同样使用扫描线更新树结构。在圆的右边界时，从树中移除对应的半圆。这样就构建出了一棵反映圆包含关系的树，可以高效地处理查询。 这些题目的解法展示了动态规划、数据结构和几何算法在解决实际问题中的应用，对于提高编程竞赛解题能力非常有帮助。