0%

题解 06

啧。

CF 1504 C Balance the Bits

给定一个长度为 $n$ 的 01 串 $s$,构造两个合法的括号序列 $a$、$b$。
要求:$a_i = b_i$ 当且仅当 $s_i = 1$;$a_i \ne b_i$ 当且仅当 $s_i = 0$。
$2\le n \le 2\cdot 10^5$

先从特殊位置讨论。一个合法的括号序列头尾一定分别是左右括号,若 $s$ 的这两个地方有 0,则不可能构造成功。

考虑数量奇偶。显然,$n$ 应该是偶数,两个括号序列的左括号总数应该是 $n$,接下来,$s$ 每有一个 0,则左括号数量变化一个。为保证仍然是偶数,0 应该有偶数个。

接着回忆一般的括号匹配:我们需要保证栈顶总不为负,而在扫完整个序列后栈顶为零。可以确定的是 1 对应的位置不会改变,那么将前一半的 1 填上左括号,后一半填上右括号,此时栈顶变化是先上升后下降。对于 0 位置的处理,只能是一半“上升”一半“下降”,才能保证总体的“平衡”。可以模拟匹配去填充,但更简单的方法是上升下降交替,先上还是先下都可以。

另外一个只从栈顶变化出发的构造思路:一条开头和结尾都在 $y = 0$ 上的折线,遇到 0 时交替升降,遇到 1 时向上下分叉,我们只记录更高的。最后得到两条折线,它们之间含有合法构造对应的栈顶变化,从尾部向前寻找即可。

CF 1506 D Epic Transformation

给定一个长度为 $n$ 的整数串 $a$,你可以进行任意多次以下操作:

  • 选择两个不同的元素并将它们移除

求操作后 $a$ 的最小长度。
$1\le n\le 2\cdot 10^5, 1\le a_i \le 10^9$

思维题。

统计出现次数最多的那个元素。如果它恰出现 $\frac{n}{2}$ 次,则刚好可以全部移除。如果多于 $\frac{n}{2}$ 次,则至少多出的无法移除。

如果不到 $\frac{n}{2}$ 次,则 $a_i \ne a_{i + \frac{n}{2}}$ 总成立,在 $n$ 是偶数时总能全部移除。

CF 1506 E Restoring the Permutation

对于一个长度为 $n$ 的全排列 $a$,构造一个等长的序列 $b$,使得 $\forall i\in [1, n]:b_i = \max(a_1, a_2, a_3,\cdots, a_i)$
给定一个 $b$,求字典序最小和最大的可能 $a$。
$1\le n\le 2\cdot 10^5$

当 $b_i$ 的值更新时,那个位置只能是那个新值。要构造字典序最小的全排列,只要记录下已确定的值,把剩下的从小到大填空即可。

构造字典序最大的结果时不能从大到小填,因为可能填入更大的值。依次向下扫会超时。用一个栈记录目前可填的所有数,在遇到可以填写的位置时弹出,即可保证字典序尽可能大,且不会破坏 $b$。

2020 CCPC Qinhuangdao E Exam Results

$n$ 个学生参加一场考试,学生 $i$ 的分数只可能是 $a_i$ 或 $b_i$。及格线为 $x\cdot p\%$,其中 $x$ 为最高分。
给定 $a$、$b$、$p$,求可及格的最多人数。
$1\le n\le 2\cdot 10^5, 1\le b_i\le a_i\le 10^9$

尺取,或者说,双指针。先找到可能的最小最高分 $x_{min}$,大于 $x_{min}$ 的所有分数都可能是最高分。此时第二个指针在头部。

从 $x_{min}$ 向后枚举,每次确定及格线,第二个指针向后越过不及格的,同时记录哪些学生掉出了及格区。维护一个最大值即可。考虑用 pair 记录分数和学生的对应关系。

2020-2021 ICPC Brazil A Sticker Album

买贴纸包来填贴纸相册。每张贴纸都一样。
相册的容量为 $n$,每个贴纸包的贴纸数量为 $[a, b]$ 间的随机整数。
给定 $n$、$a$、$b$,求填满贴纸相册所需的贴纸包的期望数量。
$1\le n\le 10^6, 0\le a\le b\le 10^6$

概率的动态规划。

而当 $a$ 可能为 $0$ 时,代入上面的递推式做个变形即可。