竞赛讨论区 > 【题解】牛客网NOIP赛前集训营-提高组(第一场)
头像
Key酱不是喵
发布于 2019-04-19 15:27
+ 关注

【题解】牛客网NOIP赛前集训营-提高组(第一场)

A中位数
• 对于第一档数据,可以枚举选取的合法的子区间,再重新排序, 直接得到中位数。时 间复杂度O(n^3)。
• 对于第二档数据,可以枚举子区间的左端点,依次往右增加新的数,现在要做的就是 往一个有序列表里加数,然后查询第k小的值。这个可以用平衡树维护。总复杂度就是 O(n^2logn)。
• 对于第三档数据,直接枚举最终可能的答案x。把数字>x的记为1,<=x的记为-1。检 验是否存在和>=0的区间。可以维护一个前缀和的前缀最大值。时间复杂度O(Mn), M为不同的数的个数。
• 正解:发现第三档数据中的x其实是可以二分的。那么二分答案x,用上面的方法检验。 时间复杂度O(nlogAi)。


B数数字
• 第一档数据直接枚举L,R之间的数字,每一个数字的数位乘积可以O(log N)求,所以总 的复杂度是O((R-L)logR)。 
• 第二档数据可以预处理每个数字的数位乘积。设F[n]表示数字n的数位乘积,则 F[n]=F[n/10]*(n mod 10)。预处理复杂度O(R), 查询复杂度O(R-L)。 
• 第三,四档数据和正解类似,都可以使用搜索。 
• 正解可以使用记忆化搜索或者DP。这里介绍DP的做法。
• 由于数位乘积只是由0到9,可以把L1,R1分类讨论,假如区间包含0,则原来的数字分 为包含至少一个零,和完全不包含0两类。前一类可以使用简单的数位DP计算。接下 来介绍后一类。
• 由于只包含1到9,所以只用记录乘积的质因数分解中,出现了多少2,3,5,7。题目 中的L1,R1不超过10^18,可以计算出2最多为59个,3最多为37, 5最多为26,7最多 为21。设F[i][c_2][c_3][c_5][c_7]表示考虑到第i位,乘积状态为c_2,c_3,c_5,c_7的数位 DP情况。接着就是经典数位DP做法。空间可能比较紧,需要用滚动数组。


C保护
• 考虑20%的数据,对于每个询问枚举一个祖先,设这条路径为(u,p)。枚举输入的路径 (x,y),可以通过检验dfs序判断(u,p)是否被(x,y)覆盖。
• 这样复杂度为O(q*n*m)。
• 对于40%的数据,优化检查合法这一步的复杂度。对于查询的一条路径(u,p),相当于 查询有多少条输入的路径(x,y),满足x在u子树,y在p子树外部,反过来也可以。
• 先只考虑一种情况。设q为x,y的lca。那么路径拆分成(x,q),(y,q)。只要(u,p)被(x,q)或 (y,q)完全包含即可。考虑被前面那个包含。
• 在x处放一个dep[q]的标记。那么当查询到(u,p)时,只需要知道,u的子树中,有多少 标记,其对应深度是小于等于dep[p]的。
• 这个可以启发式合并维护棵子树的线段树得到。那么查询复杂度为O(log n)。总复杂 度为O(nqlogn)。 
• 对于60%的数据,发现询问时,不需要暴力枚举祖先。设答案为(u,p)。p是可以二分的。 那么二分p,使用上述方法判断合法性。复杂度O(nlog^2n)。
• 对于100%的数据,询问时可以在维护出来的u的那棵线段树上走,相当于找第k小数。 复杂度O((n+q)logn)。


std

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐