JSOISC2022模拟4
前言
时隔一年再次光荣爆零。（机房垫底到底还是垫底）
论签到题的重要性。
T1
考场上一直在想贪心思路，想了两个多小时，结果正解是 dp，这也是导致我爆零的直接原因（根本原因是因为我太弱了）。
（但是听说数据没卡贪心？
设在前 \(i\) 个数字中使得值 \(\leq j\) 的数字不能够组成长度为 \(j\) 的 LIS 至少需要删除 \(dp[i][j]\) 个数字，易推出（？）状态转移方程:
\[dp[i][a[i]]=
\begin{cases}
\min(dp[i-1][a[i]-1],dp[i-1][a[i]]+1) & \text{$a[i] \neq 1$} \\
dp[i-1][a[i]]+1 & \text{$a[i]=1$}
\end{cases}
\]
观察到每次只更新 \(a[i]\) 位置，且 \(dp\) 数组只依赖上一轮的结果，可以优化：
\[dp[a[i]]=
\begin{cases}
\min(dp[a[i]-1],dp[a[i]]+1) & \text{$a[i] \neq 1$} \\
dp[a[i]+1] & \text{$a[i]=1$}
\end{cases}
\]
然后就 \(O(n)\) 求一下就行了。
T2
首先 \(40\) 分的做法比较简单，可以枚举根，设 \(dp[x]\) 表示 \(x\) 的子树中编号最小的节点的编号，求出每个节点 \(x\) 的 \(dp[x]\)，然后按照 \(dp[g[x][i]]\) 的升序遍历 \(x\) 的子节点。
但是其实考场上想到这个做法了。当时为什么没写？（好像是觉得太麻烦了（反正就是脑子不正常（啊啊啊啊啊wssb
正解其实就是要确定根，剩下和 \(40\) 的做法就差不多了。
先找到最小的叶子结点，把初始的根 \(rt\) 设为最小叶子结点的父亲，求出每个节点 \(x\) 的 \(dp[x]\)。
然后考虑向下移动根，找到 \(rt\) 的子树中 \(dp[g[rt][i]]\) 最大的节点，若这个节点的 \(dp\) 值 \(>rt\) ，就将 \(rt\) 移动到这个节点。
找到 \(rt\) 之后直接按子节点 \(dp\) 的升序遍历就行。
（证明啥的真就不想打了）
T3
暴力 \(60pts\) 之后走人。（开摆
T4
先学扫描线 P5490 【模板】扫描线