CF652(EDU10) 题解

zrl123456 · 2025-08-13 23:06:03 · 题解

:::::warning[注释] 除特殊标记外，本文中变量均为整数。
::::: :::::info[闲话] 可能是暑假最后一篇了。
:::::

A. Gabriel and Caterpillar：

:::::info[题目基本信息] 考察：数学，模拟（800）。
题目简述：
小 K 发现了一只毛毛虫，它在第 0 天 14 点位于高度 h_1m，它在每天 10\sim22 点向上以 am/h 的速度爬，其余时间在向下以 bm/h 的速度掉，问第几天的 14 点他的高度会到达 h_2m（高度可以为负），不可能给出 -1？
数据范围：

• 1\le h_1,h_2,a,b\le 10^5

  ::::: 容易发现，若一天内还没有爬上去，且最后位置回到了 h_1 甚至更低，则一定爬不上去。 否则由于数据范围较小，直接模拟即可。 时间复杂度为 \Theta(V)，空间复杂度为 \Theta(1)。

  B. z-sort：

  :::::info[题目基本信息] 考察：数学，构造（1000）。
  题目简述：
  小 X 收到了一个序列 \{a_n\}，现在将其排序，使得（1\le i\le n）：

• 若 2\mid i，则 a_i\ge a_{i-1}。
• 若 2\nmid i，则 a_i\le a_{i-1}。

构造一组合法解，若无解输出 Impossible。
数据范围：

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

  ::::: 容易发现若 \forall i,j\in[1,n],2\mid i,2\nmid j,a_i\ge a_j，则这种序列是满足要求的，直接按照这样排序模拟即可。 时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

  C. Foe Pairs：

  :::::info[题目基本信息] 考察：STL，双指针（1800）。
  题目简述：
  小 I 收到了一个长度为 n 的排列 \{p_n\}，现在给出 m 组限制，第 i 组限制为 a_i,b_i，问有多少组区间 [l,r] 满足：

• 1\le l\le r\le n
• \forall i\in[1,m],j\in[l,r],a_i\ne p_j\lor\forall j\in[l,r],b_i\ne p_j

数据范围：

• 1\le n,m\le 3\times 10^5
• \forall i\in[1,n],1\le p_i\le n
• \forall i\in[1,m],1\le a_i,b_i\le n

  ::::: 首先我们要找到 a_i,b_i 的具体位置，所以我们要开桶（较小的设为 idxa，较大的设为 idxb），然后找到若 l\le idxa\le r，则 r 最少到哪里。
  首先一个点的可以直接预处理，多个点的话先放一边。
  然后我们想到若左端点右移，则右端点的取值范围也会右移，所以我们想到双指针。
  我们回到多个点的右端点的取值范围其实就是取最小值，同时也要支持增加或减少，所以我们想到 multiset，最后直接模拟即可。
  时间复杂度为 \Theta(n\log n+m)，空间复杂度为 \Theta(n)。

  D. Nested Segments：

  :::::info[题目基本信息] 考察：树状数组，线段树（1800）。
  题目简述：
  小 A 收到了 n 条线段，它们都在同一条数轴上，问每条线段各包含几条其他的线段（保证没有线段完全重合）。
  ::::info[包含的定义] 若对于所有的在线段 a 上的点都在线段 b 上，则称线段 b 包含线段 a。
  :::: ::::info[完全重合的定义] 若线段 a 包含线段 b 且线段 b 包含线段 a，则称线段 a 和线段 b 完全重合。
  :::: 数据范围：

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

  ::::: 容易发现若线段 a 的两端为 l_a 和 r_a，线段 b 的两端为 l_b 和 r_b，线段 a 包含线段 b，则 l_a\le l_b\le r_b\le r_a。
  容易发现这就是一个二维偏序问题，将线段端点离散化后按左端点降序排序，用树状数组或线段树统计答案即可。
  时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

  E. Pursuit For Artifacts：

  :::::info[题目基本信息] 考察：边双连通分量，dfs（2300）。
  题目简述：
  小 L 收到一张 n 个点 m 条边的简单无向连通图，边边权为 0 或 1。
  小 L 要在这张图中游走，每条边只能通过一次（两个方向加起来一次），问是否存在一条 a 到 b 的边，满足路径中至少有一条边边权为 1。
  数据范围：

• 1\le n\le 3\times 10^5
• 0\le m\le 3\times 10^5
• 1\le a,b\le n

  ::::: :::::info[闲话] 发现自己的边双连通分量是假的。
  ::::: 容易发现若一个环（一个双联通分量）中存在一个边权为 1 的边，那么经过这个双联通分量的路径一定有方法使路径满足条件。
  上面的性质启示我们用 tarjan 缩点，缩完点后直接 dfs 判断即可。 时间复杂度为 \Theta(n+m)，空间复杂度为 \Theta(n+m)。

  F. Ants on a Circle：

  :::::info[题目基本信息] 考察：数学（2800）。
  题目简述：
  小 Z 发现了一个环，长度为 m，位置编号为 1 到 m，在这个环上有 n 只蚂蚁，它们分别位于不同位置且面向不同方向。
  小 Z 在那里看了 t 秒，每只蚂蚁都会以 1m/s 的速度向自己面向的方向前进，中途遇到其他蚂蚁会调头，由于他忙人多忘事，他忘了最后他们的位置，但是他记得初始状态，他想让你给出终止状态。
  数据范围：

• 2\le n\le3\times 10^5
• 2\le m\le 10^9
• 0\le t\le 10^{18}

  ::::: 我们按照常规套路，先假设这些蚂蚁碰头后会互相穿过去，这样我们就可以求出所有蚂蚁的位置，但无法知道谁是谁的。
  这时候我们注意到由于掉头，所以每只蚂蚁的相对位置一定不会改变，也就是说我们得到一个性质：一只蚂蚁一定一直在另外两只蚂蚁中间。
  那么我们把每秒从位置编号较小的蚂蚁开始编号，那么编号改变只可能有以下情况：

  1. 两只蚂蚁相遇： 这种情况其实根据上面那条性质就可以搞定了，问题在于下面这一种。
  2. 一只蚂蚁从 m 到 1 或者从 1 到 m：
     这种情况由于情况 1 已经解决就比较简单了，每只蚂蚁经过 m 到 1 或 1 到 m 的次数能 \Theta(1) 求出，那么对于不同蚂蚁而言（这里以从 m 到 1 为例，1 到 m 同理）：
     • 对于自己，自己的相对位置编号会减去 n-1。
     • 对于其它蚂蚁，它们的相对位置编号会加上 1。

  那么注意到这两种操作在模 n 意义下是等价的，所以统一处理即可。

所以，将原位置和终止位置排序，记录答案，统一输出即可。
时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。