首页 > 其他 > 详细

洛谷暑期课期末考试

时间:2018-08-11 01:03:29      阅读:65      评论:0      收藏:0      [点我收藏+]

标签:长度   dfs   每次   方便   给定   答案   如何   一个点   技术   

有点舍不得。。

dwj的声音真好听/// (逃
仓鼠的声音也好好听/// (转头又逃

T1

给定长度为n的序列A和B,定义序列Ci = max{A1, A2, A3, ... Ai}
并定义当前价值为 min(B1, C1) * min(B2, C2) * ... * min(Bn, Cn)
如果opt=0 表示对序列 A 操作,如果 opt=1 则是对序列 B 操作,
把序列中第 x 个元素变成 y ,保证 y 不小于原来的元素
答案对1e9 + 7取膜

我的想法 :
很明显要给C建单调栈
每次修改A只用考虑x后边的序列就行
如果找位置的话二分查找就行
但修改的话。。。平衡树吧
修改B更方便
但是连乘积如何统计?
好麻烦 过

正解
好像到平衡树那里都没问题
然后连乘是。。。二位偏序?!

T2

题意:
技术分享图片

我的想法:
看到“到各个点距离相等”
想到数轴上的类似问题 -> 取中位数
那么树上。。。重心咯
计算路径长度的话 lca + 差分
找根。。没时间了 暴力吧

然鹅
就死在找根的暴力上了

正解:
然后考虑到进来一个点 它会影响从自己到根的size(都加一
所以每次插一个点 重新心只会在原重心与新点的路径上
所以二分那条路径【dfs序 找重心就行了

T3

求有多少个n个节点的基环树

我的想法:
懵 什么鬼

正解:
【然鹅并没有懂】
基环树的性质 : 存在刚好两种点和边一一匹配的方案
如果dp的话
f( n ) 表示n个点的连通图 每个图点和边一一匹配的方案数之和
g( n )表示n个点的图 每个图点和边一一匹配的方案数之和
【仓鼠哥哥说这是套路 orz
显然 g(n) = (n - 1) ^ n
用g( n ) 算 f( n ) 可以考虑容斥
枚举1号点所在的连通块
f(n) = \sum_{i = 2}^{n - 1}(f(i) * g(n - i) * (C_(i - 1)^(n - 1)))
【仓鼠哥哥说这是套路 orz

技术分享图片

【仓鼠哥哥说这是套路 orz
于是神仙操作NTT
(分治,合并时用NTT

这次模拟考【第一次哎!
迟到了半小时【平时都是8点半嘛qvq
考试的时候也几乎被自己的菜蠢死
嗯 就是比较妄自菲薄 这种心态并不好
然后就是不那么认真 总有种恐惧心理
希望以后能多参加模拟赛吧
p.s.考完了发现 思维上还过得去?
就是数学太垃圾

然后 暑期课完结撒花



QwQ



舍不得



好矫情///。。。

洛谷暑期课期末考试

标签:长度   dfs   每次   方便   给定   答案   如何   一个点   技术   

原文:https://www.cnblogs.com/hjmmm/p/9457702.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号