题目都比较简单，OJ 和评测机很坑。应该是有若干台评测机，但只有一台是正常速度，最后一题交了 34 发才过。
A 洞穴
考虑每轮找到当前距离最远的一对点，他们必定都是叶子，任意选其中一个点 \(x\) ，找到与 \(x\) 距离最近的点 \(y\) ， \(x\) 仅与 \(y\) 直接有边，记录后删掉 \(x\) ，做 \(n-1\) 轮即可。
B 小度养小猫
\(-i^2*c_i\) 这部分的贡献是固定的，只需要最小化 \(t_i^2*c_i\) 。贪心地依次考虑 \(k+1\sim k+n\) 这 \(n\) 个时间点，每个时间点选择当前能喂食的猫中 \(c_i\) 最大的进行喂食即可。
C 简单题
设 \(dp(i,0)\) 表示只考虑前 \(i\) 个数，将第 \(i\) 个数分到不下降子序列时，不上升子序列末尾的数的最大值。相应地，设 \(dp(i,1)\) 表示只考虑前 \(i\) 个数，将第 \(i\) 个数分到不上升子序列时，不下降子序列末尾的数的最小值。计算时只需要讨论第 \(i-1\) 个数和第 \(i\) 个数分别分到哪个子序列中即可。
D 小度吃雪糕
二分答案后用二维前缀和检查是否存在 \(k\times k\) 的全 \(1\) 正方形即可。
E 积木
预留出一小部分高度做背包，其余部分贪心地尽可能放最大的。
F 光线谜题
看一下图就可以发现答案就是 \(({\text 辗转相减次数} -1)\times 2\) 。
G 防AK题
给每种颜色开一棵动态开点线段树即可。
H 小水题
以所有高度为 \(0\) 的点为起点 bfs 即可。
标签：个数,初赛,times,即可,2022,序列,之星,dp From： https://www.cnblogs.com/jklover/p/16630852.html