传送门

「JOI2019 Final」勇者比太郎

看懂题就很简单了,后缀和随便维护一下就好了,别用树状数组强加一个\(\log\)就行。

「JOI2019 Final」画展

显然可以先把所有的画框按大小排序。
然后把所有的画以美观值为第一关键字从小到大排序,大小为第二关键字也是从小到大排。
然后注意一下,贪心的时候要从后往前枚举,也就是先匹配大的画框,因为大的画框也一定能装下小的画,这个肯定不会更差。

「JOI2019 Final」有趣的家庭菜园

这题过于毒瘤,我不会啊。。。

「JOI2019 Final」硬币收藏

首先要知道硬币都是独立且没有差别的,硬币的移动和空格的移动也是无差别的。
我们对所有需要被放上硬币的位置开一个桶,初始化为 \(-1\) ,表示还需要填 \(1\) 个。
然后我们先让所有的硬币以其最短的路线进入目标矩阵,同时更新答案。
然后从左往右扫,对于两行分别开两个变量记录当前有多少个向右移动的硬币(可以为负数)
然后如果扫到某一列时,上下两行变量的正负性不同,就进行一次该列内部的硬币移动,同时更新答案,实现细节有一点,需要耐心和细心。

「JOI2019 Final」独特的城市

坑填上了。
这道题的理论推导有点复杂,不过实现起来还好。
首先要知道一个事情:对于一个城市 \(u\),对于它的任意一个“独特的城市” \(t\),都一定位于一条 \(u\) 到较远的一个直径端点的路径上。
这应该是显然的,因为只有这条路才不会出现可以覆盖掉 \(t\) 的另一个点。
覆盖指的是和 \(u\) 距离相同的点相互重复。
那么我们就可以先把直径抠出来,分别从两个直径端点跑dfs,然后用一个栈来记录符合条件的答案(根据上一条引理,这些点都一定在它到根的路径上),用类似莫队的方式开一个桶来记录最终答案,不断取 \(\max\) 就好了。
那么我们就要考虑如何更新栈内的点。
考虑长链剖分,对于每一次的dfs,我们先用次长链,也就是最长的轻链来覆盖栈内不合要求的点(需要预处理节点的深度),然后优先dfs重儿子,回溯上来时再以类似的方法用重儿子覆盖站内的点,但是要注意一下:如果此时栈顶元素是当前节点那就先把它弹栈,然后在进入轻儿子时再把当前节点入栈,最后退出时再和上方粗体字所述一样弹出当前节点。

05-25 14:11