210218 考试小记

发布于 2018-02-21  12.19k 次阅读


题面&官方题解:

[ttl2v]

2018-02-21

Solution1

[/ttl2v]

T1

题意略,首先不管是通过观察还是推理,必须要有这个结论:

$$\sum_{i=1}^{n} f_i=f_{n+2}-f_2$$

接着,对于一维的前缀和,就可以用上式搞定。

对于二维的前缀和,如果算出来了前两行的前缀和,那么后面的和就可以用如下递推式算出,就像斐波那契数列的递推一样:

$$F_{k,i}=F_{k,i}+F_{k,i-2}$$

考虑边界情况:

$$F_{k,1}=\sum_{i=1}^{n} F_{k-1,i}$$

$$F_{k,2}=\sum_{i=2}^{n+1} F_{k-1,i}$$

代到上面的式子里,把加减法分开,分别递推。

答案的矩阵就是T*((A^(n+1)-A)^k),其中T是斐波那契数列的前两项,A是斐波那契数列的转移矩阵。

 

T2

给出一颗有边权的树,询问整棵树中所有路径中边权中位数的最大值。

类似HEOI2016排序那道题,二分中位数的大小,把大于等于x的边权置为1,其余置为0。如果存在一条路径满足边权和非负,则答案大于等于x。

之后就是点分判断,路径长度的限制用线段树解决即可。

 

T3

给出一个序列,每次查询给出区间[L,R],求序列中有多少个与[L,R]等长且第i项之和等于第1项之和的区间,要求区间不能与[L,R]重叠。

转化到差分序列上,其实就是查询与查询区间相反数序列相等的区间,但是+1-1边界好恶心(我都快吐了)。把原序列化成差分序列,再后面插一个特殊字符,然后再插入原差分序列的相反数序列,离散,建立后缀数组(不能理解为什么“某些人”还是愿意用后缀自动机来做这道题)。对原序列中每个元素建立主席树,主席树的下标为rank,叶子权值为1或0,这样利用主席树的差分可以解决重叠的问题。接着,每次查询时二分rank上的左右端点,表示rank在[ql,qr]范围内的后缀能满足相等的要求,在差分后的主席树上区间求和即可。

这道题最坑的就是+1-1的边界啊啊啊。

 

 

感觉今天考的不太理想,第一题暴力因为数组开大了又没算内存,惨遭MLE爆零,第三题想到了正解却不敢打,写的和正解差不多的暴力,拿了80滚粗。


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974