手速场 - ABC435 A~F Solution

难度：红红橙黄绿蓝

\(\text{A}\)

根据求和公式，\(1+2+\cdots +n=\frac{n(n+1)}{2}\)，因此直接输出即可。

时间复杂度 \(O(1)\)。

\(\text{B}\)

按照题意模拟。

时间复杂度 \(O(n^3)\)。

\(\text{C}\)

我们发现倒下的点总是一段前缀，因此记录 \(r\) 表示最大的倒的点，初始 \(r=1\)，随后从 \(i=[1,n]\)：

• \(i>r\)，退出遍历。
• \(i\leq r\)，令 \(r=\max(r,i+a_i-1)\)。

倒下的牌个数即为 \(\min(r,n)\)。

时间复杂度 \(O(n)\)。

\(\text{D}\)

我们考虑建反图，从染黑的点出发染黑其可以到达的点，如果到达的点已经被染黑，则终止遍历。最后直接判断点是否被到达过即可。

时间复杂度 \(O(n+m)\)。

\(\text{E}\)

动态开点线段树模板题。

时间复杂度 \(O(n\log n)\)。

\(\text{F}\)

我们注意到猫只会从高的点跳到矮的点，因此设计 \(dp_i\) 表示跳到 \(i\) 的最大价值。如果 \(j\) 可以跳到 \(i\)，令 \(a_i=x\) 则 \(p_x=i\)，则若 \(p_j<p_i\)，需要满足：

\[i>\max_{k=p_j+1}^{p_i} a_k \]

否则若 \(p_i<p_j\)，则：

\[i>\max_{k=p_i+1}^{p_j}a_k \]

令 \((i,j)\) 可以转移时 \([i,j]=1\)，否则 \([i,j]=0\)。

则有转移方程：

\[dp_i=\max_{k=i+1}^n [i,j]dp_k+|p_i-p_k| \]

随后我们考虑分类讨论 \(p_i<p_k\) 的情况与 \(p_i>p_k\) 的情况：

我们注意到 \(dp_k\) 可以转移到的 \(i\) 即 \([k,i]=1\) 是可以表示的，我们用单调栈维护在 \(a_{p_k}\) 左边第一个大于其的位置 \(f1\) 和右边第一个大于其的元素 \(f2\)。则我们可以考虑主动转移，将 \(dp_i\) 转移到 \([f1,f2]\)，不难发现转移方程中：

• 若 \(p_i<p_k\)，则 \(dp_i+p_k-p_i\) 中，\(dp_k+p_k\) 需要最大化。
• 若 \(p_i>p_k\)，则 \(dp_i+p_i-p_k\) 中，\(dp_k-p_k\) 需要最大化。

由此维护 \(dp_k+p_k\) 与 \(dp_k-p_k\)，使用线段树维护动态规划即可。

时间复杂度 \(O(n\log n)\)。