2023牛客寒假算法基础集训营2 赛时思路+正解_罚时大师月色

大大的周 02-07 3998

A Tokitsukaze and a+b=n (easy) 题意给你两个区间，各从一个区间选一个组成一对，问你有多少对数和为n。 B Tokitsukaze and a+b=n (medium) 题意和A题一样，范围由 2 e 5 2e5 2e5变到 2 e 9 2e9 2e9 思路考虑一个区间需要另一对的数范围在 [ n ? r , n ? l ] [n - r , n - l] [n?r,n?l]，我们直接找 [ n ? r , n ? l ] [n - r, n - l] [n?r,n?l]和另一个区间的交集即可。代码

C Tokitsukaze and a+b=n (hard) 题意 A、B题意中由两个区间改变为 m m m个区间，但是数值范围变为 2 e 5 2e5 2e5。思路数值2e5我们考虑开桶维护，我们可以用二维差分维护区间，变为前缀和操作。暴力遍历每一个区间，找所需要的区间 [ n ? r , n ? l ] [n - r, n - l] [n?r,n?l]与 m m m个区间的交集即可，需要剪掉自己和自己区间组成一对对答案的影响即可。代码

D Tokitsukaze and Energy Tree 题意给定你一颗根为1的树， n n n个能量球有相应的能量，总能量为所有子树的能量球能量和的和，求总能量最大为多少。思路我们可以发现每个能量球对答案的贡献为能量球的深度乘以能量球的能量值。于是我们可以把所有的深度全部求出来，找完全匹配使得能量值*深度总和最大，比较好想的贪心是，大的配对大的，小的配对小的一定会让答案最优，于是对深度和能量分别排序，一一对应计算即可。代码

F Tokitsukaze and Gold Coins (easy) 题意问你放置了 k k k块障碍物，你只能向下向右走的情况尽可能带走多少硬币。思路起点终点都做一次 b f s bfs bfs，我用了 d p dp dp写法，写法更容易，然后考虑一个硬币能不能被起点和终点到达即可。代码

H Tokitsukaze and K-Sequence 题意有一个长度为 n n n的数组 a a a，问你划分成 k k k组的最大价值，每组价值定义为只出现一次的个数。分别输出 k k k为 1 ? n 1 - n 1?n的最大价值。思路考虑贪心，我们对于一个数值，如果他可以一个一个放在 k k k组上，他的价值就是这个数值的个数。如果数值的个数大于 k k k组，答案最优只能为 k ? 1 k-1 k?1我们考虑多出来的一组都放到其中一个组，所以答案最优为 k ? 1 k-1 k?1。在这个贪心的基础上，我们考虑维护这个答案，我们发现这和每个数的出现次数有关，我们先维护每个数的出现次数，已经相应的出现次数对应的数值个数(具体可以看代码)，然后出现次数从大到小枚举，如果有数值的出现次数为 i i i，我们就统计上这个数值 r e s = r e s + c n t [ i ] res = res + cnt[i] res=res+cnt[i]，并且答案相应的减少这个数组 r e s res res，因为答案是 k ? 1 k-1 k?1，所以我们每次遍历都要减去 r e s res res，然后输出答案即可。代码

I Tokitsukaze and Musynx 题意给你 k k k个音符和五个区间，区间形式为 [ ? i n f , a ) , [ a , b ] , ( b , + i n f ] [-inf , a) , [a , b] , (b , +inf] [?inf,a),[a,b],(b,+inf]划分为五个区间 , 如果音符的 x i xi xi值在某个区间上，那么可以获得相应的区间价值 v k v_k vk?，我们可以改变音符的 x i xi xi值，操作为所有的 x i xi xi都加上 h h h，只能操作一次，问你音符的价值和最大为多少？思路我们可以比较容易地发现，每一个往上移动都会修改某个音符，我们可以模拟所有音符从最下面的区间向上移动的过程，考虑某个音符到相应区间所需的区间位移量改动相应价值，我们先把区间位移量排序，从小到大枚举，位移量相同的我们应同时改变，在这里我用了双指针维护。然后暴力模拟即可，一道思维转化的模拟题。代码

J Tokitsukaze and Sum of MxAb 题意给定一个长度为 n n n的 a a a数组,求所有的 ( a i , a j ) (a_i , a_j) (ai?,aj?)对的价值之和，价值定义为 m a x ( ∣ a [ i ] ? a [ j ] ∣ , ∣ a [ i ] + a [ j ] ∣ ) max(|a[i] - a[j]| , |a[i] + a[j]|) max(∣a[i]?a[j]∣,∣a[i]+a[j]∣) [ ∣ ∣ || ∣∣为绝对值 ] 思路分析几次情况可以发现最终所有的数一定是变为正数变成正数加到最终答案上，负数变成正数加到答案上，直接暴力计算所有数的绝对值之和乘以 n n n即可。代码

K Tokitsukaze and Synthesis and Traits 题意给你一个公式为 a b a b ab可以组成高级材料，公式保证不会重复，给定 q q q次询问，每次询问给定 k k k个材料，问有多少相应的公式只用这 k k k种材料， k k k的总和不超过 2 e 5 2e5 2e5， q q q的总和不超过 2 e 5 2e5 2e5,公式的个数不超过 2 e 5 2e5 2e5。每组询问在一行输出。思路一眼看到这题比较好想的方向是离线处理，然后就能想到一个 n s q r t ( n ) l o g n nsqrt(n)logn nsqrt(n)logn的做法，这个时间复杂度是稳稳被卡的，所以我们考虑优化，主要的优化思路是去掉一个 l o g n logn logn，赛时采用了对个数分治，赛后也了解到有更好想的根号分治做法。 1.赛时想法 - 对个数分治我们对查询个数 k k k大于根号n的查询暴力 O ( n ) O(n) O(n)去统计答案，我们可以发现大于根号 n n n的个数一定是不超过根号 n n n的，所以这一部分的时间复杂度为 O ( n s q r t ( n ) ) O(nsqrt(n)) O(nsqrt(n))。考虑查询个数小于等于根号 n n n的查询，我们采取离线+均摊做法，我们采取离线，把所有的 k 2 k^2 k2对组合 ( i , j ) (i , j) (i,j)对应地的放到 j j j上，然后离线我们枚举点，我们枚举他和哪个点可以组成公式，这地方用邻接表以及 v e c t o r < i n t > vector<int> vector<int>类似于存图方式可以实现均摊 O ( m ) O(m) O(m)，然后用桶去维护这个点集，然后开始枚举查询对(i , j)能否组成一个高级公式，能组成当且仅当桶中存在对应的数字，然后这个时间复杂度是在 O ( n s q r t ( n ) + m ) O(nsqrt(n) + m) O(nsqrt(n)+m)的做法，可惜的是内存超限，我们分析一下小于等于根号 n n n时的离线，我们可以发现最坏情况时可以组成 n s q r t ( n ) nsqrt(n) nsqrt(n)个查询对，大概是 8 e 7 8e7 8e7左右的查询，导致空间超限，解决方案很简单，当离线查询个数大于等于 n n n的时候我们就暴力离线一下，时间复杂度不变。 2.更好的做法 - 对度数分治我们考虑对查询点的度数分治，我们可以把公式看成边一样建边，当我们查询某个点对能否组成时，我们看看这条边的两个点是否有一个度数小于等于根号 n n n，有就暴力判断。若是没有，我们考虑离线，离散暴力判断所有度数大于等于根号 n n n的点，我们可以用 O ( n ) O(n) O(n)的任何暴力方式判断即可，复杂度为 O ( n s q r t ( n ) + m ) O(nsqrt(n) + m) O(nsqrt(n)+m) 。赛时代码

L Tokitsukaze and Three Integers 题意给定一个长度为 n ( n < = 5000 ) n(n <= 5000) n(n<=5000)的数组，问你有多少三元组 [ a i , a j , a k ] ( i ! = j ) ( j ! = k ) ( i ! = k ) [a_i , a_j , a_k](i != j) (j !=k)(i !=k) [ai?,aj?,ak?](i!=j)(j!=k)(i!=k)满足 ( a i ? a j + a k ) m o d p = x (a_i * a_j + a_k) mod p = x (ai??aj?+ak?)modp=x 。思路非常明显而且很好想的预处理，首先我们对乘号预处理，预处理所有 ( a i , a j ) (a_i , a_j) (ai?,aj?)对模 p p p对应的模数个数的情况，然后考虑对 a k a_k ak?和 x x x进行 O ( n 2 ) O(n^2) O(n2)暴力。我们从1到 n n n枚举 k k k，然后我们把 k k k与别的数的乘积的模数的影响减掉，然后暴力枚举模数 m m m，然后求乘积相应所需对应的值求出来，然后用桶计数的方式维护答案即可。代码