牛客OI周赛7-提高组 题解与代码(出题记录)

A.小睿睿的等式

题目分析

送温暖题
注意不要对每个数暴力拆分算,对于每个数预处理即可
时间复杂度:\(O(n)\)

题目分析

送温暖题++
ST表\(O(1)\)即可解决
为了鼓励多种写法,特意在生成数列时限制各数的大小\(<100\)
时间复杂度:\(O(nlogn+m)\)

C. 小睿睿的方案

题目分析

总方案数易求,考虑不合法的方案数:

每对情侣对方案的负贡献:

当两个结点非祖先-后代关系时,两个结点的子树间的路径方案数

当两个结点为祖先-后代关系时,贡献为后代的子树与(整颗树除祖先子树的部分+祖先子树除 祖先含后代的子树)间的路径方案数

考虑用一\(n*n\)的矩阵里的三角形来表示方案数,矩阵上\((i,j)\)或\((j,i)\)点表示\(i\)与\(j\)的方案是不合法的,那么用dfs序来映射点,一个点的子树的dfs序连续,每个贡献可以表示为若干矩形区域,那么用线段树+扫描线即可计算出不合法的方案数

注意与矩阵对角线对称的点应同时更新

\(A\)点在\(B\)点的子树内当且仅当\(dfn[B] \leq dfn[A]<dfn[B]+size[B]\),其中\(dfn\)为dfs序,\(size\)为子树大小

时间复杂度:\(O(nlogn)\)

 

5 1 vote
Article Rating
Subscribe
提醒
guest
5 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
11
11
3 年 之前

B题标程函数调用写反啦

123
123
3 年 之前

C题从哪看出来两个结点非祖先-后代关系啊???

tmp
tmp
1 年 之前