CF620(EDU6) 题解
不说闲话。
A. Professor GukiZ's Robot：
考察：数学。
题目简述：
在一平面直角坐标系上，小 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 我们分三种情况讨论：
- 不进行操作，此时最小值就为
\displaystyle|(\sum_{i=1}^na_i)-(\sum_{i=1}^mb_i)| 。 - 进行
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| 。 - 进行
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里，然后按要求模拟即可。
时间复杂度为
E. New Year Tree：
考察：线段树，状态压缩。
题目简述：
小 Z 一棵树，它由
数据范围：
-
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) 。