吉老师出过最水的一套的题了吧。

除了我大家都 AK 了呢。


正睿 OI 官网又 GG 了,那就坑着吧。

A. 巡逻

题意概述

给定 1-n 排列的一个子序列,求可能的字典序最小的原始排列。

思路

贪心地完善排列,没什么好说的。

B. 矿石

题意概述

给定 n 个区间和 m 个定点,问有多少种可能的区间子集覆盖了至少一个定点。

思路

区间和定点分别排序后依次考虑每一个定点,使用优先队列维护覆盖这个点的所有区间,对于每一个新加入的区间单独计算其对答案的贡献。

代码

C.括号序列

题意概述

对于一个小写字母构成的字符串,询问满足形态为括号序列的连续子串个数。

  • 结果的括号序列必须要是合法的,即左右括号必须要是相匹配的。
  • 对于一对相匹配的左右括号,他们所在的位置原来的小写字母必须相同。

思路

直接用栈维护,加入的字母和栈顶元素相同则弹出栈顶元素。令 $s_i$ 为考虑到第 $i$ 个元素时栈的状态,区间 $[i,j]$ 合法当且仅当 $s_{i-1} == s_j$。用哈希值计数即可。

代码