CF1730

· · 个人记录

cnblogs

感觉这场的题目出得很好啊，让人忍不住想记录下来！

赛时通过 ABCD，rank 76。

A

把每一种数的出现次数和 c 取个 \min 再求和即可。

B

记 l = \min_i \{a_i - t_i\}, r = \max_i \{a_i + t_i\}，答案即 \frac{l + r}{2}。

C

直接贪心即可。具体地，最后的串肯定是不减的，所以我们只需要求出每种数字的出现次数即可。发现一个位置的数会被 +1 当且仅当存在一个小于它的数 x，使其位于最后一个 < x 的数右侧、最后一个 x 左侧；否则这个数可以不用被 +1。

D (\texttt{Easy} \ 3 / 0)

可能写得比较混乱。

假设 s_1 = \texttt{1234567}, s_2 = \texttt{abcdefg}，我们手模一种情况，比如最终的串为 s'_1 = \texttt{4ef5g67}, s'_2 = \texttt{ab1c23d}，我们发现 s'_1[i] = s_p[j] \to s'_2[n - i + 1] = s_{3 - p}[n - j + 1]，其中 p = 1, 2。进一步地，我们把 s_2 反转，并考察 s'_1[i], s'_2[i], s'_1[n - i + 1], s'_2[n - i + 1]，其必然由 s_1, s_2 两个位置上的字符构成，设为 i, j，因为它们可以匹配，所以无序对 (s_1[i], s_2[i]) = (s_1[j], s_2[j])，我们把所有无序对求出来并把相同的进行匹配，可以证明答案为 YES 当且仅当全部匹配完或者最终剩下一个形如 (c, c) 的对。

E (\texttt{Easy} \ 3 / 4)

其实不难想，但是比赛的时候想复杂了，赛后冷静下来就会了。

有许多种 \mathcal{O}(n \log n \max d(\omega)) 的做法，但对于我这个大常数 sb 来说这个复杂度肯定过不去，我们需要寻求时间复杂度更低的做法。

从左到右枚举 i，钦定最大值为 y = a_i（如果有多个，钦定最大值为最左侧的）并枚举其约数 x。y = x 的情况是容易的，这里仅考虑 x < y 的情况。此时我们再枚举 x 在 y 的左侧还是右侧，以左侧为例，我们现在来考虑什么样的 l, r 是能被这种情况计入答案的：

右侧是类似的。

我们需要 \mathcal{O}(1) 地回答。发现我们只需要处理每个数出现的所有位置和每个 a_i 左侧 / 右侧第一个小于 / 大于它的位置即可，所以跑四遍单调栈就能解决问题。

但是其实这么做的话细节很多，在此不一一赘述了，有问题可以看看又臭又长的代码，欢迎大家关注 BraveXuZhiJieGoGoGo 这个号。

时间复杂度 \mathcal{O}(n \max d(\omega))，其中 \omega = 10^6。

F (\texttt{Easy} \ 3 / 3)

感觉比 E 好想又好写啊！

首先把问题转化为求最少的交换相邻两数的次数，使得交换完成后对于 \forall i < j 有 p_i \le p_j + k。

发现对于一个前缀 i，其中的数肯定 \le i + k，并且 1 \sim i - k 肯定已经全部出现了，剩下的是 i - k + 1 \sim i + k 这 2k 个数，搜一下发现有 2^k 种状态满足条件，这很好啊！于是直接设 f_{i, j} 表示前 i 个数的状态第 j 种的最小交换次数即可。转移考虑填 i - k 或者填 i - k + 1 \sim i + k 的数。

还有一个问题是初值 f_{k, j} 的预处理。事实上因为只有 k 个数，直接枚举排列并暴力计算即可！

时间复杂度 \mathcal{O}(n 2^k k^2)。