Codeforces Round 888 (Div. 3)

C. Tiles Comeback

题意：给出一个标出颜色的序列，要求找出一个子序列，从第一个开始，到最后一个结束，满足长度是 $k$ 的倍数，每 $k$ 个是一种颜色，且相邻段颜色不同。求是否存在合法的子序列

当时看到题有点蒙了，赛后再看发现就是简单的分类讨论 因为就只是判断是否存在就可以了，所以可以尝试找最短的满足条件的序列，如果第一个和最后一个是相同的颜色那么有 $k$ 个就可以，不同的话前 $k$ 个同颜色的和后 $k$ 个同颜色的能满足条件即可，要是算方案数应该就要 $O(n^2)$ 了

D. Prefix Permutation Sums

题意：给出一个排列的前缀和数组去掉其中任意一项之后得到的数组，判断其对应的排列是否合法

分类讨论。首先尝试差分，如果有超过 $2$ 个 $1 \sim n$ 的数能组合出的数显然不合法，这样所有的数就都在 $1 \sim 2n-1$ 之间了 然后考虑 $1 \sim n$ 中出现了 $0$ 次的数的个数，分三种情况： - 超过两个或没有：显然不合法 - 有两个：分两种情况，有一个 $3 \sim n$ 的数出现了两次或有一个 $n+1 \sim 2n-1$ 的数出现了一次 - 有一个：前 $n$ 个出现了 $n-1$ 个，注意还有一种特殊情况 $n=2,a[1]=3$ 也是合法的（对应排列 $[1,2]$）

直接分类讨论即可，复杂度 $O(n)$

G. Vlad and the Mountains

题意：一张无向图，每个点有一个高度。一个人从 $a$ 到 $b$ 移动，在边 $(u,v)$ 上移动的代价为 $h_v-h_u$（可以是负的），要求途中到达每一个点时的代价和都不大于 $e$，求能否从 $a$ 走到 $b$，$q$ 次询问

首先仔细观察，可以发现每次旅行可以完成 $\Leftrightarrow$ 路径上点高度的最大值 $\leq h_a+e$，然后就变成了路径最大值的模板题，边权赋值为 $\min(h_u,h_v)$，由于不用在线离线跑看 Kruskal 即可，复杂度 $O(m\log m)$