离ACM还有一定距离

题解

学习笔记(7) 牛客多校2020(1)

/ 注册

全部文章 / 题解（共43篇）

【每日一题】数学考试

Solution:这是一道不会很难想的贪心题。我们枚举第二个区间的起点，同时维护该起点之前的区间最大值，当作是第一个区间的最大值，然后就可以维护答案的最大值，即ans=max(ans,ma+sum[i+k]-sum[i])。 #include <stdio.h> #include <...

2020-04-02

0 632

【每日一题】滑动窗口 (单调队列)

Solution：经典的单调队列模板题，我们可以用deque来实现。首先，滑动窗口的size不能大于k，得：r-l<=k；其次，当每个数进入队列时，若是求最大值，那么队列里比他小的数就不可能再成为答案，得：while(a[r]<=now && r>=0) r--;分...

2020-04-02

0 745

【每日一题】月月查华华的手机

思路：由于数据范围达到1e6，暴力做法时间复杂度显然离谱。我们考虑优化查找这一过程，不难想到维护一个数组 f[0-s.size]['a'-'z']，用来表示第i个字符后面第一次出现的'a'-'z'的位置，这样一来我们在查找的时候就只需要判断该字符是否在上一个字符右边出现即可，然后跳转到对应位置。关于...

2020-04-02

0 501