第一题:藤藤的生日
定位是签到题,抬走,下一题
第二题:藤藤的队列
这题比签到题难一点点,这玩意叫做对顶堆
我们搞两个优先队列,q1
存储最大的 k
个元素,但是 q1
是小根堆, q2
存储剩余的其他元素,q2
是大根堆。
对于查询,显然 q1
的堆顶就是答案,并删除之,查询时间复杂度 , 然后从 q2
那里拿一个最大的放回到 q1
中
对于插入一个元素,如果q1
不足 k
个元素,显然插入到q1 中, 如果 q1 等于 k
个元素,那么我们可以把这个元素先插入 q1
, 然后找出 q1
中最小的元素放入q2
所以本质就是维护一下这两个堆就可以了,pq用的习惯么,不习惯的话 用 multiset 。注意multiset删值会删除重复的数,所以建议使用删除迭代器。
类似题:洛谷 黑匣子
第三题:藤藤的纪念品
反悔贪心,cls最喜欢贪心了 23333
首先我们可以从对配置要求最高的纪念品开始考虑,对于一个纪念品有三种决策:
-
从满足能力且没被卖掉的纪念品中找一个最便宜的卖
-
对已经完成的纪念品中利润最低的那笔进行反悔,替换成当前纪念品
-
放弃这个买卖
因为我们规定了纪念品的顺序,所以反悔回来的纪念品一定是满足要求的。
我们只需要从上面三种决策中贪心地选择最赚的那个即可。
为了能快速找到满足能力的电脑中最便宜的和利润最低的纪念品,只需要两个小根堆即可。
时间复杂度 O(nlogn)
第四题:藤藤的约数和
考察点 倍增,约数和计算
根据约数和的性质 ,cls的数论基础课里有讲过的哦
其实我们需要知道 (u, v)
中 质因子2 出现的总和次数,于是我们可以倍增求LCA,然后用倍增/树上差分直接计算出 u 和 v 分别到 LCA路径上 2, 3, 5, 7, 11的质因子的个数。
然后使用约数和公式计算一下即可。
约数和公式不会的同学先看一下这题:https://www.luogu.com.cn/problem/U274440
第五题:藤藤的数列分段
你是不是觉得跟数列分段 II 这题很像:https://www.wikioi.cn/problem/30014
然后你是不是过了样例 然后只有20分,哈哈哈
本题 可以为负数,显然原来的贪心策略就假掉了
首先有一个重要结论:如果我们要求每段的和 不超过 的情况下,最少可以划分成 段, 最多可以划分成 段,那么这个数组每段和不超过 的情况下,我们可以划分出 中的任意段。
如果上述结论正确,那么显然我们可以继续 二分答案 , 因为 不超过成包含关系,每次二分答案只需要计算出最少的段数 和 最多的段数 ,
最后只需要判断 是否满足要求即可, 求最少的段数 和 最多的段数 可以做一个线性DP,然后用 线段树/树状数组 优化到 O(nlogn), 结合二分,最终时间复杂度带2个log
接下来说明上述结论的正确: (信息学更多需要猜出正确的结论,虽然这个结论第二眼看看很假)
考虑一个dp的过程,假设为原数组, 为前缀和
归纳假设已经知道了表示前个元素构成的子序列可以划分的段数范围
假设我们已经求出了
现在求
如果要让最终结果 不是一个区间 (最终我们会证明这个并不成立)
那么假设我们dp枚举从到枚举的话,肯定会出现一个,使得并上之前还是一个区间,并上去之后不是了
假设当前是
并且这个 是由某个 () 提供的, 这个s[k]应该要满足 , 否则肯定可以把最后一段合并,找到更小的。
如果的话,
那的最多是的
也就是说我们当前的是"k的L"+1,也就是最多的+2
然后这次更新的是的, 刚好连起来了
然后你再仔细想想,因为这个结论的说明cls也是问人的,有点糊了,如果你理解了,记得给cls来解释一遍。
第六题:藤藤的树上数数
这题是原题,非常原的题,本来想留到暑假里放进提高组模拟赛里的