啧。
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}$ 次，则 $ai \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$ 时，代入上面的递推式做个变形即可。