专题训练 - 贪心 I

[CF5C] Longest Regular Bracket Sequence

其实我也不知道这个题目为什么会有贪心的标签，看上去和贪心貌似没有关系。

令 $a_0=0$，有递推公式 $a_i=a_{i-1}\pm 1$，如果 $s_i=\mathtt{(}$，则为 $+1$，否则 $-1$。

我们可以画出 $a_i$ 与 $i$ 的图象，以它结尾的最长的括号串是 $(j,i)$ s.t. $0\le j\lt i$ 且 $a_j=a_i$ 且不存在一个 $j\le k\le i$ 使得 $a_k<a_i$。

既然这是一个一个跳的，类比连续函数的介值定理，如果存在一个 $j\le k\le i$ 使得 $a_k<a_i$，就一定存在一个位置从 $a_i$ 降到 $a_i-1$。

所以我们可以用某种方式每次记录下来 $a_i$，每当遇到 $s_i=\texttt{)}$ 时，就把 $a_{i-1}$ 至为无效，这样每次能够查询到的都是有效的数字。

具体地说，我们可以用 $f_v$ 表示值 $v$ 对应的所有下标，然后把值 $x$ 至为无效就是清空 $f_x$。

当到 $a_i$ 时，我们查询 $f_{a_i}$，如果是空则以不存在这样的 $j$，否则 $f_{a_i}$ 中所有元素都是合法的 $j$。

在这些合法的 $j$ 中，我们需要的是最小的那个值，所以 $f_{v}$ 实际上只需要存无效 / 合法下标的最小值即可，不需要真的存下所有合法的下标。

复杂度 $O(n)$。

[CF1372D] Omkar and Circle

可以看出，答案会被 $2\sim \cfrac{n+1}{2}$ 个位置贡献，那么这里就自然会有一个问题，如果答案是被位置集合 $I$ 贡献得到，其中 $|I|<\cfrac{n+1}{2}$，是否会存在一个 $J$ 使得 $I\subsetneq J$ 并且 $J$ 也是一个合法的序列？

答案是肯定的，考虑在某一步中 $A,B,C$ 三个位置集合相邻，其中 $|B|\ge 2$ 而这一步选择了 $B$，那么会得到一个 $D=A\cup C$。既然 $|B|\ge 2$，那么它被合成出来的上一步一定满足位置关系 $A,B_1,F,B_2,C$，我们显然可以分别选择 $B_1,B_2$ 得到 $E=A\cup F\cup C$。

所以，只要我们选择了某一个 $\ge 2$ 个元素复合形成的元素，就一定存在另一种方式使得我们选择它的不相交子集，并且得到一个不会更劣的答案。

因此这一步贪心可以保证我们每次选择的元素都是在最开始序列中出现的元素，那么我们可以考虑什么样的元素是可以被合并的。

不难看出，如果我们把原来的 $1\sim n$ 重排为 $1,3,5,\dots,n,2,4,6,\dots,n-1$，只有相邻项的元素会被合并，又因为上面阐述的贪心的思路保证了我们不会选择合并之后的元素，所以这一定是连续 $\cfrac{n+1}{2}$ 个元素的和的最大值。

复杂度 $O(n)$。

[CF1307D] Cow and Fields

首先我们通过 BFS 得到 $d_u,D_u$ 表示 $1,n$ 到点 $a_u$ 的最短距离。

强制经过 $(a_u,a_v)$ 的最短路，根据最短路的最优子结构，应当是 $f_{u,v}=\min(d_u+D_v+1, d_v+D_u+1)$。

于是，最终的答案就应当是 $\max_{i,j} f_{i,j}$。

方法1

既然是 $\max \min$ 这种结构，考虑二分答案 $m$，并且检查是否存在一组 $(i,j)$ 使得 $f_{i,j}\ge m$。

对于两个变量 $i,j$，我们可以枚举 $i$，寻找符合条件的 $j$。

检查是否存在一个 $j>i$，使得 $D_j\ge m-1-d_i$ 且 $d_j\ge m-1-D_i$。

这是一个二维数点问题，我们可以把 $a$ 按照 $D$ 的值排序，然后找到第一个 $p>i$ 使得 $D_p\ge m-1-d_i$，然后在 $[p,n]$ 中求出 $d$ 的最大值。

这样做的话是 $O(n\log^2 n)$。

方法2

注意到 $f_{u,v}$ 的式子比较对称，我们尝试比较 $d_u+D_v,d_v+D_u$。

如果 $d_u+D_v\le d_v+D_u$，那么 $d_u-D_u\le d_v-D_v$，那么我们按照 $d-D$ 排序，就有 $f_{u,v}=d_u+D_v+1(u<v)$。

那么 $\max_{i<j} d_i+D_j+1$ 就可以枚举 $i$ 然后求 $D$ 的后缀最大值。

这样做的话是 $O(n\log n)$。

[CF1696D] Permutation Graph

只要是 $1,2,3,\dots,n$ 边的数量就能到达 $n^2$ 量集，所以我们不能建边跑最短路。

我们可以证明，一定存在一个最短路，其中只包含 $i<j$ 的边 $(i,j)$。

首先，让我们来证明下面这个引理：

如果一条路径先后出现 $u\to v$ 及 $p\to q$，其中 $u<p<v<q$，那么一定可以直接走 $u\to q$ 节省掉这一段路径长度。

证明：不妨设 $a_u<a_v$，根据题目要求，不难推出 $a_u<a_p<a_v<a_q$。

然后，$(u,q)$ 中的这一段元素都满足在 $(a_u,a_q)$ 中，所以 $u\to q$ 是合法的。

其次，对于任意的一条 $1\rightsquigarrow n$ 的路径，我们可以下面的分解：

设 $u_1\to v_1, u_2\to v_2,\dots, u_k\to v_k$ 是第一次突破之前到达的点的最大值的一些边。

1. 对于所有的 $i$，满足 $u_i<v_i$，并且 $v$ 是严格单调递增的。
2. 对于所有的 $i>1$，满足 $v_{i-1}\ge u_i$。

这些性质都可以通过反证法来证明。

我们从后往前找一些边，先选 $u_k\to v_k$，其中显然有 $v_k=n$；假设我们当前最后一个选择了 $u_i\to v_i$ 边，那么一定有 $v_{i-1}\ge u_i$；这样，选择最小的 $j$，满足 $j<i$ 且 $v_j\ge u_i$ 作为前一条边，那么我们可以推导出 $u_j\le v_{j-1}<u_i$，那么串起来，就有 $u_j<u_i\le v_j<v_i$，于是我们可以断定，当 $u_i\neq v_j$ 时，这两条边就可以用 $u_j\to v_i$ 代替，否则也是两条可以连在一起的合法的边。

通过上面的构造，我们事实上确定了，对于任意一条路径，我们总能通过这样的方式找到一条不劣的、只有形如 $i\to j(i<j)$ 的边，也就是说，我们可以写出这样的转移：$dp_i=1+\min_{j<i,j\to i \text{ exists}} dp_j$。

接下来，我们要考虑对每一个 $i$，如何快速地求出满足条件的 $j$。

我们不妨设 $a_j<a_i$，另一种情况是对称的。

1. 为了满足 $a_i=\max_{j\le k\le i} a_k$，我们需要满足 $j>L_i$，其中 $L_i$ 是 $i$ 左侧第一个大于 $a_i$ 的元素的位置，如果不存在 $L_i=0$。
2. 为了满足 $a_j=\min_{j\le k\le i} a_k$，我们可以证明，满足这一条件的 $j$ 一定在递增的单调栈中。
   • 如果 $a_j$ 满足它是 $1\sim i$ 的后缀最小值，那么 $a_j$ 一定不可能在遍历 $j+1\sim i$ 时被弹出。
   • 如果 $a_j$ 不是 $1\sim i$ 的后缀最小值，那么 $a_j$ 就会在遍历 $j+1\sim i$ 时被弹出。

所以只要满足 $j$ 在单调栈中，并且 $L_i<j<i$，就可以把 $dp_j$ 贡献到一颗线段树中，当它被弹出时抹掉它的贡献。

复杂度 $O(n\log n)$。