Codeforces Round 757 (Div. 2)

C

D

E

一些杂题

构造杂题

Crane
题目大意就是，你能够交换长度为偶数的一个区间，交换前一半与后一半，比如 $(1, 2, 3, 4, 5, 6) \to (4, 5, 6, 1, 2, 3)$
要求你用不超过 $9^6$ 的操作，将序列变成升序
序列是 $[1\to n]$ 的一个排列，输出操作次数和每一次操作需要变换的区间

贪心策略，对于已经排序好的区间 $[1, i-1]$ 可以不用去管他
假设 $i$ 这个点还没有归位，在序列中找到 $i$ 这个元素位于下标 $p$ 处，最好希望能一步到位
那么交换区间的半径是 $p-i$，实际上，是交换 $[i, p-1]$ 和 $[p, p+(p-i)-1]$ 两个半段
此时要求 $i + (p-i) \cdot 2 - 1 \leqslant n$，如果满足，那么交换 $[i, i+2\cdot(p-i)-1]$

否则，我们需要让 $p$ 离 $i$ 尽可能近，注意，$i$ 这里指下标位置
如果 $[i, p]$ 之间的数为偶数，那么从 $[i, p]$ 中间切开，交换两个半段，那么交换后 $p$ 和 $i$ 位置处于前半段中
能够满足 $i+(p-i) \cdot 2 - 1 \leqslant n$ 的条件，只需要一步变换即可

如果 $[i, p]$ 之间的数为奇数，那么从 $[i, p+1]$ 中间切开，同样交换两个半段，交换后也只需要一步变换即可
特别地，如果 $p = n$，那么 $p+1$ 越界了，这也很好解决，将 $p = n$ 这个位置的元素和 $n-1$ 这个位置的元素互换
然后转为以上情况处理即可

区间杂题

选择不相交的区间
给定 $n$ 个开区间 $(a_i, b_i)$，选择尽量多的区间，使得这些区间没有公共点
贪心策略如下

• 如果区间 $x$ 完全包含 $y$，选 $x$ 不划算，因为选 $y$ 的话，之后可能还可以选其他区间
  选 $x$ 的话，和 $x - y$ 相交的这部分区间选不了，不划算，也就是说，覆盖的话，选子区间
• 对区间按右端点排序，即按 $b_i$ 排序，排序之后，记录上一个被选择的区间 $p$
  一开始 $p = 1$，排除所有和 $p$ 相交的区间，那么 $j$ 就是 $p$ 之后第一个和 $p$ 不相交的区间
  将 $j$ 放入答案中，并更新 $p \leftarrow j$，接着往下扫描，就得到了答案

区间选点问题
给定 $n$ 个闭区间 $[a_i, b_i]$，选择尽量少的点，使得每个区间至少含有一个点，不同区间可以含有同一个点
贪心策略如下

• 选的点应该被更多的区间所包含，可以根据区间右端点 $b_i$ 排序，$b_i$ 相同的时候按照 $a_i$ 排序
• 第一个区间取右端点 $b_1$，然后记一下 $p \leftarrow b_1$，接下来考虑之后的区间，所有满足 $a_i \leqslant p$ 的都跳过
  然后第一个满足 $a_j > p$ 的区间，选 $b_j$，并记录一下 $p \leftarrow b_j$，以此类推，就得到了答案

区间覆盖问题
给定 $n$ 个闭区间 $[a_i, b_i]$，选择尽量少的区间，覆盖 $[s, t]$
贪心策略

• 首先预处理每个区间，剔除每个区间在 $[s, t]$ 之外的部分，贪心策略是，选择的区间应该要尽量长
  对区间按左端点排序，左端点相同按右端点排序，如果 $a_1 > p$，那么无解
• 记录起点 $p \leftarrow s$，考虑之后的区间，如果有 $a_j = p$，那么找到 $a_j = p$ 并且 $b_j$ 最大的区间 $j$
  选择区间 $j$，接下来令 $p \leftarrow b_j+1$，应该考虑的区间是所有 $a_{j'} \leqslant p$，再在这些区间中
  选择 $b_{j'}$ 最大的那个，令 $p \leftarrow b_{j'} + 1$，以此类推

滑动窗口杂题

Smallest Sub-Array
给定 $n$ 个值为 $[0, m-1]$ 的整数组成的序列，输入 $k, (k \leqslant 100)$，找出一个尽量短的连续子序列
$(x_a, x_{a+1}, \cdots, x_{b-1}, x_b)$，使得子序列包含 $[1\cdots k]$ 的所有整数

不难想到用滑动窗口，假设窗口为 $[i, j]$，这里的要求是尽量短，所以大致采取的思路是
先不去动 $i$，遍历 $j$ 同时在窗口添加 $a_j$，如果窗口满足条件，就用 $[i, j]$ 更新答案
此时区间可能有冗余元素，尝试用 $\textbf{while}$ 循环缩小窗口，看一下满不满足，缩小的过程
实际上就是 $i \leftarrow i+1$

具体来说，添加元素 $a_j$ 的时候，如果 $1 \leqslant a_j \leqslant k$ 并且 $++\text{cnt}[a_j] = 1$
就令 $tot++$，删除的时候类似，这样当 $tot = k$ 的时候，窗口就满足条件，可以用 $[i, j]$ 更新答案

在编程实现的时候，当 $j$ 遍历到一个新的位置的时候，先在窗口中添加 $a_j$，然后执行 $\textbf{while}$ 判断
$\textbf{while}$ $tot = k$，用 $[i, j]$ 更新答案，接着尝试缩小窗口，如果 $i \leqslant j$ 就尝试删除 $a_i$ 并令 $i++$