1.P6891 [JOISC2020] ビルの飾り付け 4
本题如果按照最直接的方式dp时空都是 \(O(n^2)\)。可以用一个常用的优化：交换下标和值，用dp数组维护一个集合（可以证明是一个区间，于是用左右端点表示）。
2.P7216 [JOISC2020] 美味しい美味しいハンバーグ
正解是2-SAT，但是太麻烦，码量大难想。其实可以随机化解决，在暴力的基础上将第一个不满足条件的向前随机交换。
3.P7215 [JOISC2020] 首都
暴力枚举每一个颜色可以做到 \(O(n^2)\)，考虑点分治，将枚举的颜色换成重心，即可 \(O(n\;log\,n)\)。
4.P7219 [JOISC2020] 星座 3
由题目形式可以想到笛卡尔树，然后线段树优化dp（没调出来）。还有一个更简单的方法，从下往上合并区间，每次更新贡献，用树状数组维护差分数组。
5.P7217 [JOISC2020] 収穫
根据题意，可以对于每一个人求出一个 \(f_i\) 表示 第 \(i\) 个人拿完后下一个拿的人的编号。那么可以从 \(i\) 向 \(f_i\) 连一条权值为 \(i\) 和 \(f_i\) 距离间隔的边，于是构成一个内向基环树森林。基环树可以分成树的部分和环的部分分别求解，转化成二维数点和三维数点问题。
6.P7214 [JOISC2020] 治療計画
这道题感染者的状态在时间轴上的变化不好处理，于是新加入一个时间维度分析。问题转化之后建图，由于跑点权最短路每个点最多松弛一次，松弛后删去可以让复杂度与边数无关做到 \(O(n\;log\,n)\)。
标签：总结,一个,可以,JOISC2020,20230628,数组,习题,dp From： https://www.cnblogs.com/dks-and-xiao-yu/p/17512707.html