CF620(EDU6) 题解

zrl123456 · 2025-07-30 19:08:38 · 题解

不说闲话。

A. Professor GukiZ's Robot：

考察：数学。
题目简述：
在一平面直角坐标系上，小 X 要从 (x_1,y_1) 移动到 (x_2,y_2)，每次他可以使得所在坐标的横纵坐标加上或减去 1 或不改变（由于小 X 智商没有问题，所以他不能也显然不会完全不移动），求他移动的最少步数。
数据范围：

• -10^9\le x_1,x_2,y_1,y_2\le 10^9

  我们先假设他只能上下左右移动，那么他会先向上或下移动 |x_1-x_2| 步，再向左或右移动 |y_1-y_2| 步。
  现在他能向八个方向移动，故向左或右和向上或下的各 \min(|x_1-x_2|,|y_1-y_2|) 就会合并，减少了 \min(|x_1-x_2|,|y_1-y_2|) 步，所以最后答案就是 |x_1-x_2|+|y_1-y_2|-\min(|x_1-x_2|,|y_1-y_2|)=\max(|x_1-x_2|,|y_1-y_2|)。
  时间复杂度为 \Theta(1)，空间复杂度为 \Theta(1)。

  B. Grandfather Dovlet’s calculator：

  考察：模拟。
  题目简述：
  小 I 在等红绿灯时想到了一个问题，如果他从红绿灯还剩 b 秒等到了还剩 a 秒，问任一秒红绿灯亮起的小灯（每个数位各有 7 个小灯）根数的总和。
  数据范围：

• 1\le a\le b\le 10^6

  定义 \{a_{10}\} 为每个数字的亮起的小灯数，枚举 a 到 b 的每一秒，逐位统计亮起小灯数的总和即可。
  时间复杂度为 \Theta((b-a)\log b)，空间复杂度为 \Theta(1)。

  C. Pearls in a Row：

  考察：贪心，STL。
  题目简述：
  小 K 拿到了一个数列 \{a_n\}，他定义合法的连续子序列 [l,r] 是 \exists l\le i<j\le r,a_i=a_j 的连续子序列，问该序列最多分割成多少个连续子序列并给出一种方案，无解输出 -1。
  数据范围：

• 1\le n\le 3\times 10^5
• \forall i\in[1,n]\cap\mathbb Z,1\le a_i\le 10^9

  我们开一个桶判断这个数是否出现过，由于数据范围较大要开一个 map，贪心地，每次遇到重复出现的数就分割成一段，别忘了合并最后不符合条件的一段。
  时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

  D. Professor GukiZ and Two Arrays：

  考察：二分，STL，贪心。
  题目简述：
  小 A 拿到了两个数列 \{a_n\} 和 \{b_m\}，他最多可以拿出两个数列中的各一个数交换两次，他想知道最后两数列的和的差的绝对值的最小值是多少并给出一种方案。
  数据范围：

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

  我们分三种情况讨论：

  1. 不进行操作，此时最小值就为 \displaystyle|(\sum_{i=1}^na_i)-(\sum_{i=1}^mb_i)|。
  2. 进行 1 次操作，此时预处理两序列的和为 suma,sumb，假设确定了交换的 i 和 j 后交换后变为了 suma-a_i+b_j 以及 sumb+a_i-b_j，直接枚举，最小值为 \displaystyle\min_{i=1}^n\min_{j=1}^m|suma-sumb-2a_i+2b_j|。
  3. 进行 2 次操作，假设确定了交换的 i_1,i_2,j_1,j_2 则最后答案为 |suma-sumb-2(a_{i_1}+a_{i_2})+2(b_{j_1}+b_{j_2})|，所以 2(b_{j_1}+b_{j_2}) 要尽量接近 sumb-suma+2(a_{i_1}+a_{i_2})，所以将所有的 2(b_{j_1}+b_{j_2}) 扔进 set 里，然后按要求模拟即可。

时间复杂度为 \Theta((n^2+m^2)\log m^2)，空间复杂度为 \Theta(m^2)。

E. New Year Tree：

考察：线段树，状态压缩。
题目简述：
小 Z 一棵树，它由 n 个点组成，最初第 i 个点的颜色为 c_i，后来有 m 次操作，可以将一个子树中的颜色全部修改为一个颜色或查询一个子树内的不同颜色数。
数据范围：

• 1\le n,m\le 4\times 10^5
• \forall i\in[1,n]\cap\mathbb Z,1\le c_i\le 60

  注意到 1\le c_i\le 60，所以我们可以将 60 种颜色是否出现过压缩到一个 long long 中，然后用 DFS 序将树拍到序列上，最后就是普通的区间修改区间查询了。
  时间复杂度为 \Theta(n+m\log n)，空间复杂度为 \Theta(n)。