17.4.18 考试小记

发布于 2018-04-17  4.77k 次阅读


T1 #6032. 「雅礼集训 2017 Day2」水箱

感觉搜索不是很好写,于是直接来写60分的DP。设f[i]为前i个位置,从某个位置到i的水位相同,且不能没过h[i]的最大收益。先预处理出每个位置每个水位的左边界,之后每次枚举当前高度,就可以O(1)转移了,复杂度O(n*(n+m)),60分很容易。

之后,如果想延续这个做法,就要换个状态定义了。设f[i][j]为前i个位置且最后一个位置的高度为j的最大收益,不用考虑当前的h[i]。我们可以使用线段树对这个玩意进行整体转移。首先,假设我们已经有了i-1的线段树,那么由于存在h[i-1]的边界,我们可以将[1,h[i-1]]的答案直接设为这个区间的最大值。之后,考虑新加入的点的贡献,也就是转化成区间加的操作即可,总复杂度O((n+m)logn),常数略大。

 

T2 #6033. 「雅礼集训 2017 Day2」棋盘游戏

做过原题,题解就在这里

但是考试的时候没(bu)有(hui)写暴力拍一拍,把一个地方的m写成n了,挂了20。。。

T3 #6031. 「雅礼集训 2017 Day1」字符串

因为查询串的长度和为1e5,所以可以按照查询串是否大于sqrt(n)来分类做。

首先可以建出SAM,把询问串也插进去,这样可以O(logn)进行一次查询,对于长查询串就可以直接这样搞了。

之后,如果是很多小串,就可以直接枚举每个串的所有子串出现了多少次,然后可持久化数组(主席树)或者莫队就可以搞了,这部分事实上可以去掉倍增的log,因为每个节点都会用到。

假设nm同阶,那么总复杂度O(n^1.5 logn),没错就是在凭着信仰做题。

 

感觉做原题的考试好无聊啊。


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