zhuo & Wen_kr 的数据结构复习专题

DarkMoon_Dragon · 2019-10-27 21:33:20 · 个人记录

CF Data~Structure专题笔记

• 只记了些好题

• 还混了些Wen_kr的杂题

  CF1061D TV Shows

题意

• 有 n 个区间[l_i,\ r_i]，现在要把区间分为 m 组（m 为 [1,\ n] 中的整数，任意选定），满足每组的区间互不相交。设在某一组的区间中，最小的 l_i等于 a，最大的 r_i 等于 b，则该组的花费为 x + y \times (b - a)。求最小总花费，答案对 10^9 + 7 取模。

Solution

• 这么大的数据，不能dp，考虑贪心
• 先按照左端点排序
• 新加一段区间时，要么新开一组，要么与上面某一组合并。
• 新开一组代价显然。
• 与上面某组合并，肯定是选择左边界最右的那一组合并。
• 最小花费费用即为min(x+(r_i−l_i)∗y,(r_i−now)∗y)

CF1070C Cloud Computing

题意

• 有很多个活动，每个活动有持续天数，每个活动会在每天提供C_i个CPU每个CPU价格为P_i，问需要工作N天，每天需要K个CPU的最少花费。

Solution

• 每天肯定是选价格前K小的CPU。
• 对于每个新活动，记录哪一天加入，哪一天结束。
• 维护一个价值为节点下标的线段树(题面中限制价格的原因)。
• 每次更新(或者删除)单点修改就相当于update(C, +-P, 1, MAXC, 1)
• 查询就查询区间前K个数，线段树二分。
• 返回就返回个数乘单价。

CF960F

题意

• 给你一张n个点m条边的带权有向图，可能有重边和自环。边会按照顺序给出。让你求出一条最长的路径，使得路径上的边满足边权和出现的时间严格递增。路径可以重复经过同一个点。

Solution

• 类比最长上升子序列的线段树做法，记f[i]表示以节点i为终点的最长上升路径长度，然后对图中每个点都维护一棵动态加点线段树（像trie树一样），以边权作为区间，以f为值。每插入一条边在起点的线段数中统计答案，之后再把算出来的答案插入到终点对应的线段树中。

CF1196D2 RGB Substring

题意

• 有个RGB无限循环的长母串，q组样例，每组一个n\leq2*10^5长的字符串，让你通过更改n长串的某个字符构造一个长度为k的，既是母串的子串，也是n长串的子串。求满足要求的最少更改次数。

Solution

• 母串只有三种字母很特殊
• 只有三种循环位移情况
• 考虑对于某种循环位移，当前一位不同是一定要交换的，就可以前缀和统计

  母串t：BGGGG（3种）
  样串s：RBGRBGRBGRBGRBGRBG
  贡献a：11011 (不同贡献为1，循环3种贡献)

• 要求长度为k前缀和\Theta(n)判断即可

CF1140C Playlist

题意

• 每个数有两个参数，一共n\leq3*10^5个数，定义一段数的价值为其第一个参数的和乘上所有选订数的第二个参数的最小值。求选定最多k\leq n个数的最大价值。

Solution

• 对于这种一维要取到最小最大的问题，通常是将那一维排序，然后这样一个数之前或者之后的都可以选了。
• 先按照第二参数从大到小排序，那么一个数上面的数都可以选，那第一参数取前k大即可，优先队列维护。

CF1208D Restore Permutation

• ☆☆

题意

• 现在有一个从1到n的一个全排列，但是你不知道这个排列到底是什么，但是你有一个sum[i]。
• sum[i]=\sum_{j=1}^{i-1}\ (a_j<a_i)\ ?\ a_j\ :\ 0
• 现在给你sum数组，求出这个排列。

Solution

• 可以倒过来考虑每个数的贡献
• 对于最大的数来说，一定不会被别的数加到，然后最后一位一定是从1加到某个数，二分即可把最后一位的数求出来，然后最后一位确定了，前面的前缀和就要减去最后一位的数（也不会再产生贡献了）
• 然后就可以确定倒数第二个数，一直这样二分下去即可
• 不用树状数组当然也可以线段树二分，显然树状数组好写又好想
• 复杂度\Theta(n\log^2n)

luoguP2345 奶牛集会

• ☆（这是没有星）

题意

• 这是下一道题的弱化版，作为引入
• 每头牛有坐标X_i，音量V_i，定义两头牛的贡献
• f(i,j)=max\{V_i, V_j\}\times |X_i-X_j|
• 求每对奶牛的贡献和

Solution

• 对于这种一维要取到最小最大的问题，肯定是先把一维排序（把限制拆掉），然后再来搞第二维
• 所以考虑先将所有牛按照V_i排序，依次加入牛，那么当前牛对于之前牛的贡献乘的都是自己的V
• 维护距离之和考虑树状数组

CF1167F Scalar Queries

• ☆☆☆

题意

• 有一个不重的数列
• 定义
• f(l,r)\ =\ \sum ^r _{i=l} a_i*rank_{i,l,r}
• 求所有f(l,r),1\leq l\leq r\leq n 模 10^9+7 的和。

Solution

• 有了上一道题的铺垫，现在来考虑这道题
• 把这个式子化简一波
• 得到
• ans\ = \ \sum ^n _{i=1}a_i*sum_i
• 即每一个元素乘它所在区间内比它小的数的个数加 1, 最后再相加所得的和。这个可以类比上面的求法个桃子
• 考虑对于任意两个数a_i,a_j，先钦定a_i>a_j,i<j（大于小于都可以），这样包含这两个数的区间个数为i*(n-j+1)，对答案贡献a_j\times (n-j+1)\times i。
• 因为后面那段a_j\times(n-j+1)是固定的，那么考虑用树状数组瞎搞维护二维偏序
• 当然先得离散化
• 这样只算了顺着来的，还有倒着来的，倒着按照相同方法瞎搞一遍
• 但是这样并没有完，比如1,2,5，5的rank是3，但是按照前面的方法算出5的rank为2，因为5本身还有一位rank
• 那咋办嘛？？？
• 手糊样例发现本身rank每个存在区间都少算了一次，加上本身乘上当前数存在的区间数就过样例了
• 这种连乘的题还是每个乘都取模吧，要不贼容易爆掉
• 然后就A掉了升级版

AT2300 Snuke Line

题意

• 有一趟列车有 ????+1 个车站，从 0 到 ???? 编号。
• 有 ???? 种商品，第 ???? 种只在编号 [????_????,????_???? ] 的车站出售。一辆列车有一个预设好的系数 ????，从 0 出发，只会在 ???? 的倍数车站停车。对于 ???? 从 1 到 ???? 的列车，求对于每个 ???? 能买到多少种商品。
• ????≤3∗10^5,????≤10^5

Solution

• 考虑枚举系数d
• 对于一种商品，如果其区间长度\geq当前枚举系数d，那么这种商品一定能被买到
• 对于区间长度<当前枚举系数d的商品，d在区间内出现的次数\leq1
• 那么久枚举系数d，将长度严格小于系数d的区间加入数据结构，查询d的倍数中有多少区间，加上长度大于等于系数d的区间个数就是答案。因为d在区间内出现的次数\leq1，所以这样计算是不重不漏的。
• 区间修改，单点查询。树状数组差分实现。
• 因为
• \frac{n}{1} +\frac{n}{2}+\frac{n}{3}+\frac{n}{4}+… \frac{n}{n}=???? \log ⁡????
• 总复杂度\Theta(n\log ^2 n)
• 常数巨小

AT2581 Meaningful Mean

题意

• 给定一串长度为 ???? 的数列，询问有多少个区间的算数平均数大于等于 ????.
• ????≤2∗10^5,????,????_????≤10^9

Solution

• 这种题一般都考虑推一下式子
• 区间和转化为前缀和
• 对于区间(l,r)，转化成前缀和
• \frac{sum[r]-sum[l-1]}{r-l+1}\geq K
• sum[r]-sum[l-1]\geq(r-l+1)\times K
• 前方高能，原式等价于
• sum[r]-K\times r\geq sum[l-1]-(l-1)\times K
• 化简思路？寻找通项，或者说左右移项搞一搞
• 问题转化成了C[i]=sum[i]-K\times i前面比后面小于等于的对数
• 树状数组离散化搞搞，或者归并搞搞即可
• 注意这里并不是逆序对，所以理论上来说树状数组瞎搞好做一些

luogu\ P2471 [SCOI2007]降雨量

题意

• 我们经常会说这样的话：“X年是自Y年以来降水量最多的”，就是对于任意Y<Z<X，有Z年的降水量严格小于X年，且X年的降水量小于等于Y年。
• 给定 ???? 个指定年份的降水量数据，???? 组询问，每次询问给出 ????,????，询问 ???? 是否是自 ???? 年以来降水量最多的，输出 ????????????????,???????????????????? 或者 ????????????????????
• 年份编号 <10^9，n≤50000,m≤10000

Solution

• 再见，数据结构