CF665(EDU12) 题解

zrl123456 · 2025-09-01 22:51:01 · 题解

A. Buses Between Cities：

:::::info[题目基本信息] 考察：数学（\color{yellow}1600）。
题目简介：
有两座名为 A 市和 B 市的城市，它们之间有公交车行驶，公交车每天都从 A 或从 B 发车，始发车时间为 05:00，末发车时间不晚于 23:59，A 市发车间隔为 a 分钟，行驶时间为 t_a 分钟，B 市则分别为 b 分钟和 t_b 分钟。
你驾驶着一辆从 A 市一时刻发出的公交车，求你在 A 市和 B 市之间的道路上（不含 A 市和 B 市）遇到了几辆公交车。
数据范围：

• 1\le a,t_a,b,t_b\le 120

  ::::: 不妨用从 B 市的始发时间代表每一辆公交车，发现我们没必要弄清楚是在公交车是在哪里相遇的，我们只需要弄清楚相遇几次。 也就是说，我们只需要弄清楚这段时间遇到的公交车的始发时间区间即可，后面几辆公交车就好求了。
  时空复杂度均为 \Theta(1)。

  B. Shopping：

  :::::info[题目基本信息] 考察：模拟（\color{orange}1400）。
  题目简述：
  你是一个卖家，售卖 k 种物品，编号从 1 到 k，初始排列为 \{p_k\}，有 n 个买家来你这买东西，每人买了 m 个编号不同的物品，每次购买后你都要一次进行如下操作：

  1. 记 pos 为该物品在 \{p_k\} 中出现的位置。
  2. 花费 pos 的体力将该物品挪到第一位。

问最后花费的体力。
数据范围：

• 1\le m\le k\le 100
• 1\le n\le 100

  ::::: 模拟即可。
  时间复杂度为 \Theta(nmk)，空间复杂度为 \Theta(nm+k)。

  C. Simple Strings：

  :::::info[题目基本信息] 考察：贪心（\color{orange}1300）。
  题目简介：
  给你一个仅包含英文小写字母的字符串 s，每次操作可以将字符串里的一个字符修改成另一个英文小写字母，问经过最少操作后的一种使得相邻字符不同的一种方案。
  数据范围：

• 1\le |s|\le 2\times 10^5

  ::::: 我们可以直接贪心，如果一个字符与它的前一个字符相同我们就直接修改成另一个与前后字符均不相同的字符。
  证明显然。 时空复杂度均为 \Theta(n)。

  D. Simple Subset：

  :::::info[题目基本信息] 考察：数学，质数筛（\color{green}1800）。
  题目简介：
  有一个可重集 A，满足 |A|=n，求它的最大子集满足：元素两两的和均是质数。
  数据范围：

• 1\le n\le 1000
• \forall i\in[1,n],1\le a_i\le 10^6

  ::::: 注意到除了 2 外偶数都不是质数，也就是说除了最终集合内的元素两两除了两个 1 外奇偶性均不同，也就是说，最多只能有 2 个数大于 1，1 同时若能选则尽量全选。那么我们根据以下情况讨论：

  1. 无 1 且无大于 1 的数。
  2. 无 1 且有一个大于 1 的数。
  3. 无 1 且有两个大于 1 的数。
  4. 有所有 1 且无大于 1 的数。
  5. 有所有 1 且有一个大于 1 的数。
  6. 有所有 1 且有两个大于 1 的数。

我们来简化一下分类讨论：

• 以下情况可能会较优，同时它们的合法条件分别是：
  1. 无 1 且有一个大于 1 的数。
     条件任意。
  2. 无 1 且有两个大于 1 的数（设为 x,y）。
     条件为 x+y\in\text{prime}。
  3. 有 1 且无大于 1 的数。
     条件任意。
  4. 有 1 且有一个大于 1 的数（设为 x）。
     条件为 x+1\in\text{prime}。
• 以下情况不优或不合法：
  1. 无 1 且无大于 1 的数。
     由于根据上述，答案至少为 1，所以该情况不优。
  2. 有 1 且有两个大于 1 的数（设为 x,y）。
     考虑反证法： \because x+1,y+1,x+y\in\text{prime},x>1,y>1 \therefore x+1>2,y+1>2,x+y>2 \therefore x+1,y+1,x+y\in\{2k+1|k\in\mathbb Z\} \therefore x+y\in\{2k,k\in\mathbb Z\}

     推出矛盾。

根据上述模拟。
时间复杂度为 \Theta(n^2)，空间复杂度为 \Theta(n)。

E. Beautiful Subarrays：

:::::info[题目基本信息] 考察：trie（\color{green}2100）。
题目简介：
给你序列 \{a_n\}，求满足下列条件的 (l,r) 的个数：

• 1\le l,r\le n
• \displaystyle\bigoplus_{i=l}^ra_i\ge k

数据范围：

• 1\le n\le 10^6
• 1\le k\le 10^9
• \forall i\in[1,n],1\le a_i\le 10^9

  ::::: 显然，我们可以维护一个异或前缀和记作 \{sum_n\}，那么原条件可以转化为 sum_r\oplus sum_{l-1}\ge k，这个显然可以用 trie 树维护。
  时空复杂度均为 \Theta(n\log V)。

F 不会/ll