是瑶瑶呀

2020-07-20 17:22 已编辑运营

关注

【题解】2020牛客暑期多校训练营（第三场）

A – Clam and Fish

•算法类别：贪心

•时间复杂度：O(N)

•主要观察：有鱼的时候就钓鱼一定是最好的策略之一

•用鱼饵钓鱼会多浪费一个鱼饵。

•若该时间拿来制作鱼饵，顶多之后用该鱼饵掉一条鱼，还多占用未来的时间，不如现在就直接钓鱼。

•于是我们只需再考虑有无蛤蜊的情形作为子题。

•只考虑蛤蜊的子题这里提供两种方法

1.从时间早考虑到时间晚

•有蛤蜊就做鱼饵，没蛤蜊就就尝试用鱼饵钓鱼。最后若发现还剩x 包鱼饵，就把制作比较晚的x / 2 包鱼饵的时间拿来钓鱼。

2.从时间晚考虑到时间早

•若时间i 有鱼饵，且时间i 之后还留有没做鱼饵也没钓鱼的时间点，就在时间i 做鱼饵，否则该时间就预留着，等着用小于i 的时间点做的鱼饵钓鱼。

B – Classical String Problem

•算法类别：数据结构平衡树指针维护

•时间复杂度：O(|S|+Q)

•参考做法：想像成字符串是头尾接在一起的，只需维护一个指针指向当前第一个字符的位置，就能以O(1) 的时间复杂度进行每个操作。

•以Sample 为例

•初始时指针在n 的前面|nowcoder

•操作1 询问指针右边第1 个字符，答案是n

•操作2 把4 个字符搬到右边，相当于把指针向右移4 个字符nowc|oder

•操作3 询问指针右边第6 个字符，答案是o

•操作4 把右边3 个字符搬到右边，相当于把指针向左移3 个字符n|owcoder

•…

C – Operation Love

•算法类别：計算幾何- 顺/逆时钟判断

•时间复杂度：O(N) (N 是顶点数)

•若要做正统的两个多边形判断也可以，但由于此题保证输入只可能是题目里的左手印或右手印，于是我们可以先把多边形的点转为逆时针顺序，再判断是否有连续两个边长为9 和8 的pattern 即可。

•要注意此题输入给的是不精确的福点数，在做数值判断的时候要容许一些误差(例如两条边长度差不超过0.1就当作相等) 。

D – Points Constructive Problem

•算法类别：数学、构造

•时间复杂度：O(n+m)

无解判断

•首先观察到m 是奇数时一定无解

考虑从某行无穷远的左端往右端通过，一定是白点->黑点->白点->黑点->白点的顺序交错，且起始和最终都一定是白点，所以每一行一定有偶数个相邻的相异色点对。对于列来说也是同要道理。

•m > 4 * n 一定無解

因为每个黑点至多有4 个相邻的白点。

•m 的下界见下页

无解判断

•m 的下界判断

•假设这n 个黑点共出现在相异的a 行和b 列，每行及每列都至少有2 个异色点对，所以至少有2(a+b) 个异色点对，且此下界能够构造出来。

•这a 行b 列的交集至多有a x b 个黑点。

•所以我们要找到a, b 满足a x b >= n 且2(a + b) 最小ㄒ

•于是暴力枚举a, b 即可求出m 的最小可能值(有个更强的性质：极值一定发生在abs(a-b) <= 1) 。

无解判断

•m 的下界判断

•以n = 10 为例，a = 3, b = 4 时满足a x b = 12 ≥ 10 且2(a+b) = 14 的值最小，故m 最小可能值为14。

•n = 10, m = 14 的其中一组解如下：

解的构造

•m 恰为下界

•找出符合下界的a, b 后，选定任意连续的a 行b 列，先由左而右，再由下往上依序涂成黑点即可。

•m > 下界

•当目前相邻相异色点对数仍小于m，就把最右上角的黑点丢到远处，相邻相异色点对数就会增加2 or 4，一直做此操作。

•若全部操作完时相邻相异色点对数超过m，必定只超过2，此时只要移动某个四周都是白点的黑点到恰与另一个黑点相邻的位置即可。

E - Two matchings

•算法类别：图论、贪心、动态规划

•时间复杂度：O(n)

•观察一：此题等价于找一些长度为偶数的环使得这些环恰通过每个点一次，且所有边的总权重最少。

•观察二：2k 个点所构成的环的权重和的最小值为最大的权重减最小的权重。

•观察三：先把所有点的按照权重排序，最佳解一定是出现在每个环都是由排序后连续的点构成。

•观察四：若某个环长度≥ 8，总是可以拆成一些长度为4 或6 的环且总边权更小。

•于是我们就可以把点的权重排序后，对于前2k 个点当作子题来动态规划啦，转移时只要枚举最后一个点所在的环长度是4 还是6 即可。

F - Fraction Constructive Problem

•算法类别：数学、扩展欧几里得算法

•时间复杂度：预处理: O(V) ，每个询问O(log V) (V 是a,b 的上界)

•状况1：a 和b 不互质

•令g 为a 和b 其中一个大于1 的公因数，a/g+1, b/g, 1, b/g 就是答案。

•状况2：b 的相异质因数不超过1 个

•无解(为什么呢?下页再解释) 。

•状况3：b 的相异质因数个数超过1 个

•先找到d, f，满足d × f = b 且d, f 互质。

•c/d-e/f=a/b 通分后可推得(c×f-e×d)/(d×f)=a/b，，也就是要找到c 和e 满足c×f-e×d=a"。"

•这不就是扩展欧几里得算法在解的问题吗？

•Codeforces 上差不多感覺的構造題：1366D

•a, b 互质且b 的相异质因数不超过1 个时无解的证明

•假设b = P^K，由于a, b 互质，所以 c/d-e/f 化为最简分数后必须是a/b，但d 和f 的质因数分解中p 的指数都小于k，得到矛盾。

G – Operation on a Graph

•算法类别：数据结构(并查集、链表)

•时间复杂度：O(Nα(N)+M)

•重要观察：在所有操作过程中，对于每个点，至多只会有一次把相邻的点和自己变为同一种颜色的操作，经过该次操作后，就永远和相邻的点同色了。

•参考做法：

1.对于每个颜色都维护一个点的链表，储存该颜色中尚未把所有相邻点变为自己颜色的点。

2.用并查集纪录每个点属于哪个颜色。

3.每次操作就会把颜色oi 的链表中所有相邻的点所属的颜色都变为oi ，就直接把对应的链表合并以及在并查集上做对应的操作。

H – Sort the Strings Revision

•算法类别：栈、笛卡尔树、动态规划

•时间复杂度：O(N)

•参考做法：

•令si 排序后的位置为posi，方便起见，这里都假设di != pi mod 10

•先考虑所有字串的第一个字符，不妨假设是pk = 0，那么s0~sk 都是0，而sk+1~sn 都是dk (假设dk 不为0) 。于是我们就知道s0~sk 和 sk+1~sn 之间的大小关系。于是我们就可以把所有字符串分成s0~sk 和sk+1~sn 两组，把两组都视为子问题递归求出答案，由於0 < dk, pos0~posk 的值會和s0~sk 的子问题一样，posk+1~posn 的值會是s0~sk 的子问题答案中每个值都加上k+1。

•如果有某些行满足di = pi mod 10，直接忽略那些行即可。

•递归的过程中，每次对pos 数组的操作都是把连续某段加上某个值，且我们并不需要在过程中知道某个子题的实际答案，所以就可以用连续和的dp技巧以O(n) 的时间复杂度维护答案！

•但递归时，我们还需要在每个子问题中(假设是sl~sr在做排序)，找到k 满足pk 是pl~pr 间值最小的数。

•哎，好像有个东西叫做笛卡尔树就是在解这个问题。

I – Sorting the Array

•算法类别：数学、数据结构

•时间复杂度：O(log k∑▒n)

•各种观察

•根据sort 的性质，我们可以知道，ret[i] 是是b[i.. min(i+m-1,n)] 中扣除ret[0] ~ ret[i-1] 中最小的数。

•对于一个j，若存在某个ret[i] > ret[j] 且i < j，那么b[j+m-1] 一定是ret[j]

•扣除上一个观察中满足条件的所有ret[j] 后，假设只剩下x 个数字，我们要解的问题相当于输入的m 和k值不变，n 改成x，而ret = [0,1, ...,x-1]。

•现在我们就当作input 中的ret 数组中ret[i] = I

•先考虑一个相对简单的问题：求出数组b 的可能个数

•再一个观察，按照以下算法可以产生出所有可能的数组b：

•依序从0 至n - 1 枚举i ，在b[0] ~ b[min(n-1,i+m-1)] 中，选一个尚未给定数值的数设为i。

•根据上述算法，决定i 的在数组b 中的位置的时候恰有min(m,n-i) 个位置可以选择，所以可能的数组b 的个数就是∏_(i=0)^(n-1)▒〖min(m,n-i)〗。

•又一个观察：我们可以找到一个尽可能大的数v，满足∏_(i=v)^(n-1)▒〖min(m,n-i)〗≥k，则字典序第k 小的b 中，对于所有i < v 必定有b[i] = i。

•最后数组b 只剩下至多min(n, log k) = s 个位置还不确定数值，我们可以对每个位置枚举要放那个数字，并按照类似上页所列的排组方式以O(s) 的时间计算该位置摆该数字时b 数组含有多少种可能性，有O(s) 个位置，每个位置至多枚举O(s) 个数，每次花O(s) 的时间计算，于是我们就得到一个单笔数据O(s3) 的方法。而所有数据实际是时间复杂度分析出来会是O(n log2 k)。

•若常数写的不高，此方法已经能够通过此题。

•实际上，仔细分析排列组合公式就会发现，枚举一个位置所有可能摆放的数时，从一个数换成另外一个数，可以只用O(1) 的时间复杂度算出答案。所以此题可以做到O(n log k)。