题解：P11356 [eJOI 2023] Opening Offices

Monomial · 2025-08-12 10:24:39 · 题解

考虑在原来的网格图上我们的最优策略是什么。容易发现，我们一定有一种情况不会走回头路。但是在树上，我们一定要走回头路，我们就要考虑什么样的路径等价于在网格图上不走回头路。

我们考虑上图的情况。在网格图上，我们会走一个长方形的轮廓，但是在树上我们会多走一次下方的黑色线。在类似的情况，即同一行或同一列有 \geq 2 条边时，树上的路径肯定是更劣的。可以证明，不含这种情况的 S 必定是合法的。

思考如何计数，首先考虑比较简易的 \mid S \mid = 2。

这两个点之间的路径只有这两种情况，我们按两个方向做下前缀和即可，然后对同一行或同一列的情况去重。

接下来我们考虑如何做 \mid S \mid = 3，对比 \mid S \mid = 2 只多了四种情况（下图旋转可以得到）。

我们在红点处计数即可，同样注意去重直接向三个方向延伸的情况。

最后我们考虑 \mid S \mid \geq 4 的情况，对比 \mid S \mid = 3 只多了两种情况（下图旋转可以得到）。

那么我们现在无法在红点直接计数这个东西，因为同时出现了两个红点。那么我们可以尝试记录右下角红点的信息，然后带到左上角的红点计数，依然要注意去重直接向四个方向延伸的情况。

最后说一下第一问具体如何实现，其他两问是类似的。我们对边进行分类，即区分不同方向来的边，同时设 dp_{i,j,S} 为我们走到点 (i,j)，且经过的边类型集合为 S 的方案数，那么可以 \mathcal{O}(n^{2}2^{k}) 转移并计算答案，其中 k=4。对于两个红点的情况，我们可以再设 f_{i,j,S} 表示有红点，且经过的边类型集合为 S 的方案数，这个和 dp 一起算即可，总复杂度还是一样的。代码细节比较多，建议想好再写。