P10220 [省选联考 2024] 迷宫守卫 题解

· · 题解

题目传送门

思路

考虑对于一棵子树，如果我们确定了探险者 Bob 第一个取到的符文，那么接下来他必须按从深到浅的顺序进入与路径相连的节点为。那么我们考虑贪心，对于一棵子树，找到探险者 Bob 能取到的符文中最小编号最大是多少。

考虑什么情况下一个符文不能第一个取到，当且仅当唤醒了该符文的一个祖先 p 上的守卫，使得该符文在节点 p 的右子树内。

考虑对于整棵树，我们如何确定 Bob 第一个取到的符文。我们按编号从小到大枚举符文，对于每个符文，我们先看它是否处在某个已被唤醒的守卫的右子树内，如果是，那么考虑下一个符文，否则我们找到他的祖先中 w_{p}-sumw_{rs_{p}} 最小的祖先 p（sumw_{p} 表示以 p 为根的子树内，所有已被唤醒的守卫的 w 之和），唤醒节点 p 位置的守卫，再把以 rs_{p} 为根的子树中所有的守卫敲晕，直到 k < w_{p}-sumw_{rs_{p}}。这么做正确性显然，因为每个符文都不可能有更优的方案。

那么我们就知道了 Bob 第一个选择的符文了，然后我们考虑模拟 Bob 的行动，每次进入到一颗新的子树就重复上述操作。

然后你写出来了，然后你交了，然后你只得了 25 分，然后你自闭了。

考虑这样做有哪些花费是有损耗的。考虑我们在某子树中让一些守卫守住了一些符文（让这些符文不能被第一个选到），但这些符文在更大的子树内，也都被另一些守卫守住了，那么这个时候只需要保留深度深的守卫守住这些符文即可，更大子树中的那些守卫是被浪费了的。

所以我们考虑在递归到某个子树时，如果这个子树的根是其父节点的右儿子，且其父节点守卫已被唤醒，那么尝试将这个守卫守住的符文分给子树内多个守卫守住，如果可以，那么就敲晕这个守卫，再递归到子树内。考虑这么做的正确性，由于是字典序，所以按 Bob 行动的顺序操作，在递归前尝试拆守卫，显然正确。

考虑时间复杂度，每个符文可能在以它的任一祖先为根的子树内被尝试加入，一次加入是 O(n) 的，所以总复杂度 O(n^{2} 2^{n})

code

我们需要知道某子树中，比某个符文大的最小符文，考场写的是主席树，其实可以使用类似归并排序的方法，记录每个符文在每个子树内的 next。

把守卫敲晕，可以使用类似线段树懒标记的操作。

主席树实现（这个是暴力敲晕守卫，复杂度错误但是能过）

归并实现