本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-06 12:03:34

记录

ABCDE 顺利切了，F 罚了一堆，最后过了。G 紫的，Ex 点分树不会，不补了。

题解

A - camel Case

基本循环判断题，略过不表。

B - Trimmed Mean

基本排序题，略过不表。

C - LRUD Instructions 2

模拟，用 map 记录访问情况。

D - Flip Cards

发现每一张卡片只与其左右相邻的卡片有关，因此依次处理时只需要知道前一张卡片的状态即可转移，考虑 dp。

设 $f_{i,0/1}$ 表示前 $i$ 张卡片处理完，第 $i$ 张卡片不翻面/翻面的方案数，只需要从 $f_{i-1}$ 且与这一位不同的状态转移过来即可。

E - Find Permutation

考虑把大小关系转化成一张图，由较小的元素向较大的元素连边，那么：

• 若图中有环则无解，但保证有解所以不用考虑。
• 若有多个无入边的元素则一定有多解，因为这些元素都可以作为 $a_1$。
• 之后便有唯一的 $a_1$，若从 $a_1$ 开始的最长链长度为 $n$，则有唯一的排列，否则没有。

最长链用拓扑排序即可。

F - Teleporter and Closed off

由于要删掉每一个元素并询问，很容易想到处理前缀和后缀答案，删除 $k$ 时只特殊处理 $k-m$ 到 $k+m$ 的答案，把前后缀维护的值加上即可。

所以设 $f_i$ 表示从 $1$ 走到 $i$ 的最少步数，$g_i$ 表示从 $i$ 走到 $n$ 的最少步数，分别顺序和逆序 dp 即可。统计答案时枚举 $i\in [k-m,k-1],j\in[k+1,k+m]$，若从 $i$ 能到 $j$，则用 $f_i+1+g_j$ 更新答案即可。