【VP 记录】ABC291

KSCD_ · 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 更新答案即可。