wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共3篇）

bzoj2086 Blocks

题目链接题面思路可以发现其实就是询问一个最长的区间，使得这个区间的平均数大于等于k。所以将区间内所有数字减去k，然后做一遍前缀和。只要是前缀和之差大于等于0的区间。就是满足条件的。所以现在问题就成了对于前缀和上的每个数字，找到一个最靠前的比他小的数字。这个可以用单调栈。可以发现如...

动态规划dp 单调栈

2019-01-24

0 458

bzoj2086 Blocks

题目链接题面思路可以发现其实就是询问一个最长的区间，使得这个区间的平均数大于等于k。所以将区间内所有数字减去k，然后做一遍前缀和。只要是前缀和之差大于等于0的区间。就是满足条件的。所以现在问题就成了对于前缀和上的每个数字，找到一个最靠前的比他小的数字。这个可以用单调栈。可以发现如...

动态规划dp 单调栈

2019-01-24

0 420

bzoj3238 差异

题目链接思路观察题目中的式子，可以发现前两项是定值。所以只需要求出最后一项就行了。然后题目就转化为了求字符串中所有后缀的\(lcp\)长度之和。可以想到用后缀数组。在后缀数组上两个后缀的\(lcp\)长度表现为两个后缀排名之间的\(height\)的最小值。所以现在问题就又转化为了在\...

后缀数组单调栈

2019-01-30

0 448