JOI 2019 Final 选做.
「JOI 2019 Final」勇者比太郎
枚举 $(i,j)$ ,合法的 $k,l$ 的数目用预处理的后缀和算一下就行了,时间复杂度 $O(n^2)$ .
「JOI 2019 Final」画展
容易发现,若最多有 $k$ 幅画展出,那么一定存在一组解,满足使用的画框是大小前 $k$ 大的.
将画框按大小从大到小排序,画按照美观度为第一关键字,大小为第二关键字从大到小排序.
贪心匹配即可,若当前画能放入未被使用的最大画框中,就将其放入,时间复杂度 $O(n\log n)$ .
「JOI 2019 Final」有趣的家庭菜园 3
对最后的序列 dp ,设 $dp(i,j,k,lst)$ 表示红,绿,黄分别已经用了 $i,j,k$ 个,上一个元素的颜色是 $lst$ 时的最小花费.
显然将原序列移动到最终序列后,同一种颜色的叶子相对顺序不会改变,于是可以 $O(1)$ 计算出每次转移的花费.
时间复杂度 $O(n^3)$ .
「JOI 2019 Final」硬币收藏
首先可以把每个硬币都移动到最近的在矩形中的点,再考虑通过移动使得每个位置恰有 $1$ 个硬币.
记 $d$ 表示各个位置还需要多少硬币,从左往右考虑每一列,若该列的两个 $d$ 一正一负,就移动到其中一者为 $0$ .
然后将多余的 $d$ 分给下一列即可,时间复杂度 $O(n)$ .
「JOI 2019 Final」独特的城市
记树的某条直径为 $S-T$ ,则对于一个点 $x$ ,能对它造成贡献的点,一定都在 $x$ 到 $S,T$ 中较远的那个点的路径上.
否则,若还有其他点能对 $x$ 造成贡献,那么它到 $x$ 的距离一定大于 $x$ 到 $S,T$ 的距离,可以构造出更长的直径.
以 $S$ 为根做一次 dfs ,对每个 $x$ ,统计一下 $S\to x$ 路径上有几个点能对 $x$ 造成贡献,再以 $T$ 为根做一次同样的 dfs .
对于同一个 $x$ 的两次 dfs ,假设 $x$ 到 $S$ 更远,那么 $T$ 那一次的 dfs 计入贡献的点就是 $S$ 那一次计入贡献的点的子集.
那么把两次的答案取 $\max$ 就是实际的答案.
dfs 时,用一个栈维护根到当前节点路径中,能造成贡献的点,开一个桶记录每种权值出现次数.
往栈中加点或者删点的时候,更新桶,并且更新当前答案,类似于莫队增加或删除端点时的操作.
假设当前已经处理了 $x$ 的答案,需要继续向下 dfs .
为了保证栈中点都是有贡献的,要先把栈中与 $x$ 距离小于等于 $x$ 到其它子树中最深的点的所有点删掉.
先往最深点的方向走,再往其它儿子走,删除操作就不用被撤销掉了.
每个点只会对它的父亲贡献 $O(1)$ 次进出栈操作,时间复杂度 $O(n)$ .