做题笔记

本篇会记录笔者一些做题时的思路，更多为个人记录。

CF1077D

题意：给定长度为 \(n\) 的序列 \(a\)，请求出长度为 \(k\) 的子集 \(b\) 在 \(a\) 中出现的尽可能多。

思路：一眼贪心，每次输出出现次数最多的数，并再记录多次出现的情况（第一次数量除二，第二次除三……），执行 \(k\) 次操作。

复杂度：输入 \(O(n)\)，优先队列 \(O(log\ n)\)，处理为 \(O(k)\)，总时间复杂度为 \(O(n+k\ \log\ n)\)。

CF1077E

题意：给定长度为 \(n\) 的序列 \(a\)，一开始自拟一个 \(x\)，第 \(k\) 次选择一个 \(a_i\) 要求其大于 \(k \times x\)，选过的不能再选，问最多能选多少次。

思路：从大到小开始枚举，每次将数量除以二，同时记录答案。

复杂度：排序 \(O(n\ \log\ n)\)，处理 \(O(n)\)，总时间复杂度为 \(O(n\ \log\ n)\)。

CF1077F1

题意：给定长度为 \(n\) 的序列 \(a\)，请你选出 \(m\) 个数并且保证任意连续 \(k\) 个数都至少选中一个，求选出来的数最大和。

思路：三层循环暴力 DP。设 \(f_{i,j}\) 表示选到第 \(i\) 个数，已经选了 \(j\) 个数，并且第 \(i\) 个数一定选。状态转移方程：\(f_{i,j}=f_{\max\{0,i-k\}\ldots i-1,j-1}\)。

复杂度：处理 \(O(n^3)\)。

CF1077F2

题意：与 CF1077F1 相同，不同在于数据范围无法使用 \(O(n^3)\) 过，需优化至 \(O(n^2)\)。

思路：相比 CF1077F1 加个单调队列优化。

复杂度：处理 \(O(n^2)\)。

P1311

题意：给定长度为 \(n\) 的序列和一个整数 \(p\)，每个数都有一个 \(a_i\) 和 \(b_i\)，请你求出有多少对 \(i,j,k\) 满足 \(i ≤ k ≤ j,i ≠ j,a_i = a_j,b_k ≤ p\)

思路：扫一遍，记录一个前缀数组 \(sum\)，如果当前 \(b_i ≤ p\) 就让 \(sum_i+1\)。对于任意 \(j\)，若满足 \(j<i,a_j=a_i,sum_i-sum_{j-1}>0\) 则 \(ans\) 加一。

复杂度：总时间复杂度 \(O(nk)\)。

ARC149_b

题意：给定 \(n\) 对数，你可以将它们进行排列，并构成两个数列。求两者 \(lis\) 之和最大值。满足两个序列都是 \(n\) 的排列。

思路：因为是 \(n\) 的排列，也就是说你可以让没对数在至少一个序列中的答案产生贡献。所以，对于最优解，所有数都将对答案产生贡献。那么我们可以将 \(n\) 对数按第一关键字排序，使得第一个序列 \(lis\) 长度为 \(n\)，在求第二个序列的 \(lis\) 即可。

复杂度：排序 \(O(n\ \log\ n)\)，求 \(lis\) \(O(n\ \log\ n)\)。

CF407B

题意：给定长度为 \(n\) 的迷宫，第 \(i\) 个迷宫有两个通道，分别前往 \(i+1\) 和 \(p_i\)（\(1 \le p_i \le i\)）。一个人会从第一个房间开始走，第奇数次经过会前往 \(p_i\)，偶数次会前往 \(i+1\)。问走多少次会到达终点（\(n+1\))。

思路：不难想到模拟的方法，进一步可以得到记忆化的方法，再进一步得到动态规划的方法。设 \(f_i\) 表示从点 \(1\) 走奇数次到 \(i\) 的最少次数。从若不在意这一步的奇偶，那么 \(f_i\) 为 \(f_{i-1}+1\)。但是从 \(i-1\) 第一次到达 \(i\) 必然为奇数次，所以还要加上 \(f_{i-1}-f_{p_{i-1}}+1\)。故 \(f_i=2 \times\ f_{i-1} - f_{p_{i-1}}+2\)。

复杂度：时间复杂度 \(O(n)\)。

ARC152_b

题意：给定一条长度为 \(l\) 的小路，路上有 \(n\) 个休息站。两个人各选择一个点，同时出发，碰到端点后返回。但是两人不能同时在同一个非休息站的点（包括但不限于相遇，随从……），同时两人可以在休息站调整方向或等待。问两人都回到自己的出发点时总时间最少。

思路：不难发现，两人一开始在同一个休息站出发、背向而行才有可能出现最优解，同时这个在休息站换方向纯粹就是障眼法。那么，假设没有不能同时在非休息点的地方相遇，那么答案为 \(2\ \times\ l\)。否则，我们先考虑其相遇位置，先要到达此地者会在最近的休息站等待另外一人与他相遇后再走，此过程消耗时间为 \(2\ \times\ abs\{l-x-y\}\)（\(x\) 为出发点，\(y\) 为距离原相遇点最近的休息站）。注意细节，你不能在端点处的休息站等待。

复杂度：确定最近的休息站 \(O(\log\ n)\)，枚举出发点为 \(O(n)\)，总时间复杂度 \(O(n\ \log\ n)\)。

ARC150_c

题意：给定序列 \(B\) 和一张 \(n\) 个点 \(m\) 条边的图，每个点有一个点权，问所有从 1 到 \(n\) 的路径上依次经过的点的点权形成的序列都含有 \(B\) 作为子序列。

思路：\(f_i\) 表示从 1 点出发到达 \(i\) 点时，其点权序列已经将 \(B\) 的前 \(f_i\) 个数字作为子串，做一遍 Dijkstra 即可。

复杂度：Dijkstra 的复杂度。

ARC149_d

题意：给定 \(n\) 个点，第 \(i\) 个初始位于 \(x_i\)（\(1 \le x_i \le 10^6\)）。你要进行 \(m\) 次操作，第 \(i\) 次操作给定 \(d_i\)，接下来对于第 \(i\) 个点：

• 若点 \(i < 0\)，则 \(i\) 往右方向移动 \(d_i\) 个距离。

• 若点 \(i > 0\)，则 \(i\) 往左方向移动 \(d_i\) 个距离。

• 若点 \(i = 0\)，则不动。

问操作完之后每个点是否在 0 处。若在，输出第几次操作时他到达了点 0.否则，输出最后这个点在哪.

思路：既然移动每个点太麻烦，干脆移动原点。一开始所有点都在正方向，也就是所有点都在原点的一侧，然后每个点将会朝原点移动。此时，到达原点的点就不用再管了，接下来有些点还在原点的原来的一侧，有些点到达了另一侧。我们可以把原点两边点少的那一侧“折”到另一侧对应的位置。例如当前原点为 5，那么 3 对应的位置就是 7。这样，所有的点就有都在原点的一侧了。设某一次操作时点 \(p\) 被折叠到了 \(p'\)，不难发现，\(p\) 最终的答案就是 \(p'\) 的相反数。我们折叠的时候记录一下，建一条从 \(p'\) 到 \(p\) 的有向边，最后会形成一个森林，从每一棵树的根开始更新答案即可。

复杂度：时间复杂度 \(O(m+\max\{x_i\})\)