专题训练 - 贪心 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}$ 实际上只需要存无效 / 合法下标的最小值即可，不需要真的存下所有合法的下标。

[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}$ 个元素的和的最大值。