CF612(EDU4) 题解

zrl123456 · 2025-07-23 17:18:26 · 题解

依然没有计算几何题。

A. The Text Splitting:

考察：字符串，模拟。
题目简述：
给你一个长度为 n 的字符串 s 以及两个正整数 p,q，现在让你把 s 分割成若干个子串，使他们的长度为 p 或 q。
最后以原来顺序输出子串个数及子串自身，多解任意输出，无解输出 -1。
数据范围：

• 1\le p,q\le n\le 100

  首先我们发现先分割长度为 p 还是 q 的字符串是无所谓的，所以我们可以默认先分割长度为 p 的字符串，枚举子串个数，计算长度为 q 的字符串个数，有解直接输出即可。
  时间复杂度为 \Theta(n)，空间复杂度为 \Theta(n)。

  B. HDD is Outdated Technology:

  考察：模拟。
  题目简述：
  有一排列 \{a_n\}，定义从位置 i 走到位置 j 的代价为 |i-j|，求从排列上的值为 1 的位置走到值为 2 的位置，一直走到值为 n 的位置的总代价。
  数据范围：

• 1\le n\le 2\times 10^5

  我们要快速找出值为 i 的位置就要在读入后直接记录下来，然后直接模拟即可。
  时间复杂度为 \Theta(n)，空间复杂度为 \Theta(n)。

  C. Replace To Make Regular Bracket Sequence:

  考察：栈，数学。
  题目简述：
  给你一个由 <，>，(，)，[，]，{，} 的字符串 s，定义 <，(，[，{ 为左括号，反之为右括号，每次操作可以将一个左括号改为其它左括号，也可以将一个右括号改为其它右括号。
  求将其变为合法括号匹配的最小操作数，无解输出 Impossible。
  数据范围：

• 1\le|s|\le 10^6

  我们可以先按普通括号匹配去做，先判断是否有解，然后统计匹配的不同左右括号对数，这就是答案。
  时间复杂度为 \Theta(n)，空间复杂度为 \Theta(n)。

  D. The Union of k-Segments:

  考察：数学，差分，离散化。
  题目简述：
  在一条坐标轴上，给你 n 条线段，再给你一个整数 k。如果一个点至少被 k 条线段覆盖，那么这个点是符合条件的。
  求在坐标轴上仅包含所有符合条件的线段的最小数量。
  数据范围：

• 1\le k\le n\le 10^6

  注意到一条线段就是在给一段区间区间加 1，最后就是在查询权值大于等于 k 的点集合，这让我们想到差分。
  查分前我们需要先将点离散化，但我们发现若相邻的两点分别为两条线段的一个端点且中间没被线段覆盖，但两条线段仍认为是一条线段。
  那么我们想到我们在离散化时不只把线段端点离散化，还要和线段右端点加 \displaystyle\frac{1}{2} 和左端点减 \displaystyle\frac{1}{2} 一起离散化，都乘 2 可以避免小数（最后别忘除回去就行）。
  然后普通地进行差分即可，根据题意模拟输出。
  时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

  E. Square Root of Permutation:

  考察：图论。
  题目简述：
  给你一个排列 \{p_n\}，求一个排列 \{q_n\}，使得 \forall i\in[1,n]\cap\mathbb Z,q_{q_i}=p_i，若无解输出 -1。
  数据范围：

• 1\le n\le 10^6

  如果我们给这个排列按照 i\rightarrow p_i 的方式连边，发现形成了若干个环。
  对于一个环（x_1\rightarrow x_2\rightarrow\cdots\rightarrow x_m\rightarrow x_1），如果它是奇环，那么它会变成 x_1\rightarrow x_3\rightarrow\cdots\rightarrow x_{m-1}\rightarrow x_2\rightarrow x_4\rightarrow\cdots\rightarrow x_m\rightarrow x_1，如果它是偶环，它会变为两个环（x_1\rightarrow x_3\rightarrow\cdots\rightarrow x_{m-1}\rightarrow x_1 和 x_2\rightarrow x_4\rightarrow\cdots\rightarrow x_m\rightarrow x_2）。
  由于排列 \{p_n\} 中的偶环只可能由分割得到，故相等大小的偶环数量一定是偶数，这就是有解的判定。
  然后根据上述还原回环即可。
  时间复杂度为 \Theta(n)，空间复杂度为 \Theta(n)。

  F. Simba on the Circle:

  考察：dp，模拟，离散化。
  题目简述：
  在一个圆上顺时针标着编号为 1 到 n 的 n 个整数，第 i 个数字大小为 a_i。
  现在从位置 s 顺时针或逆时针移动的同时选择数字，选择的数字产生的序列需要不降且所有数字都要被选择，设移动 1 个单位长度花费 1 的代价，选择数字不花费代价，求最小代价及方案。
  数据范围：

• 1\le s\le n\le 2000
• \forall i\in[1,n]\cap\mathbb Z,-10^9\le a_i\le 10^9

  先设 dp 状态，设 dp_i 为最后选择的数字是 a_i 且当前在位置 i 上的最小花费，f_i 为所有 a_i 已被选择且当前在位置 i 上的最小花费。
  下面分两个步骤：

  1. 由 f_{i-1} 转移到 dp_i：
     这个很简单，在预处理时将所有 a_i 离散化，将相同的 a_i 封装到一个名叫 idx_{a_i} 的 vector 里，然后枚举 idx_{i-1} 和 idx_i 中的数，直接转移即可。
  2. 由 dp_i 转移到 f_i：
     很显然，在 a_x=a_y 的情况下从 x 绕整个圆一圈回到 x 旁边的 y 是最优的，那么直接枚举 x 以及 y 是在 x 的顺时针还是逆时针方向即可。

这样就可以求出最小代价，方案在 dp 过程中记录即可。
时间复杂度为 \Theta(n^2)，空间复杂度为 \Theta(n)。