知识点归类——前缀和

适用题型

  1. 使用 \(O(1)\) 的时间求部分和:前缀和+差分

    一维——求出数组的某一下标区间内符合要求的元素之和

    若 \(S_{[1,n]}=a_1+a_2+…+a_n\) ,则

    \(S_{[L,R]}=S_{[1,R]}-S_{[1,L-1]}\)

    二维——求出二维数组某一子矩阵内符合要求的元素之和(通常和DP结合)

    若 \(S_{[1,1]->[N,N]}=a_{11}+a_{12}+…+a_{21}+a_{22}+…+a_{NN}\) ,则

    \(S_{[l,r]->[L,R]}=S_{[1,1]->[L,R]}-S_{[1,1]->[l-1,r]}-S_{[1,1]->[l,r-1]}+S_{[1,1]->[l-1,r-1]}\)

码题记录

  1. 洛谷P1865 - A % B Problem(源地址自⇔洛谷P1865

    tag:⇔数论(素数筛)、⇔前缀和、⇔个人评级:入门级(橙题)【原:黄】

    题意:对于给定的区间,输出这段区间内质数的个数(输出给定区间内质数的个数)。

    思路:先一遍 \(O(n*\sqrt{n})\) 的遍历求解每一位是否是质数,然后再用前缀和数组累加,求出到这一位为止前面一共有多少质数。对于一次询问,以 \(O(1)\) 效率输出。

    补充:刚开始以为数据量是 \(t*n\) ,想到朴素素数筛可能过不了(\(t*n*\sqrt{n}\)),所以就改用了埃氏筛,最终时间复杂度是 \(O(t+n*log_2n)\) ,用时85ms,看了一圈应该是用时最短的那个层级的了。A了之后才发现 \(t\) 不是乘到复杂度里的,而是加进去的,而且数据很水 (洛谷的数据一如既往的水啊)

  2. 洛谷P1114 - “非常男女”计划(源地址自⇔洛谷P1114

    tag:⇔排序、⇔前缀和、⇔个人评级:入门级(橙题)【原:黄】

    题意:找到给定 \(01\) 序列中最长的子串,子串中 \(0\) 的数量等于 \(1\) 的数量(输出包含 \(01\) 数量相等的最长子串)。

    思路:若有两个位置,其前面 \(1,0\) 的数量差相同,则说明这两个位置之间 \(1,0\) 的数量差为0,即为所求。故——先一遍 \(O(n)\) 的遍历计算出前缀和数组,求出到这一位为止前面 \(1\) 的数量比 \(0\) 的数量多了多少个,并存入类桶结构,然后以常数时间查找、输出(注意,这个地方有卡常风险)。

  3. 洛谷P3131 - [USACO16JAN]Subsequences Summing to Sevens S(源地址自⇔洛谷P3131

    tag:⇔数学规律、⇔前缀和、⇔个人评级:普及级(黄题)【原:橙】

    题意:找到给定序列中最长的子串,子串中各元素之和恰好能被 \(7\) 整除(输出各元素之和恰好能被 \(7\) 整除的最长子串)。

    思路:其实和上一题一样,但是不那么容易想到。若有两个位置,其前面所有元素之和 \(\%7\) 恰好相等 ,则说明这两个位置之间各元素之和 \(\%7\) 为0,即为所求。先一遍 \(O(n)\) 的遍历计算出前缀和数组,求出到这一位为止前面所有元素之和 \(\%7\) 的值,并存入类桶结构,然后以常数时间( \(O(7)\) )查找、输出即可。

  4. 洛谷P2969 - [USACO09DEC]Music Notes S(源地址自⇔洛谷P2969

    tag:⇔二分法、⇔STL、⇔前缀和、⇔个人评级:入门级(橙题)

    题意:(输出给定元素在哪个区间里)。

    参见类似题

  5. 洛谷P3662 - [USACO17FEB]Why Did the Cow Cross the Road II S(源地址自⇔洛谷P3662

    tag:⇔前缀和、⇔差分、⇔个人评级:普及级(黄题)

    题意:共有 \(n\) 个信号灯,坏了 \(b\) 个,给出它们的编号。问:最少修好几个信号灯,使得连续有 \(k\) 个信号灯是好的。

    思路:先处理路灯亮灭,亮为 \(0\) ,灭为 \(1\) 。再计算前缀和,求出到这一位为止前面一共有多少 \(1\) (多少灯是灭的);再差分,求出从前面 \(k\) 位到这一位为止(连续 \(k\) 盏灯),一共有多少 \(1\) (多少灯是灭的),同时统计最小值。

  6. 洛谷P3406 - 海底高铁(源地址自⇔洛谷P3406

    tag:⇔前缀和、⇔贪心、⇔个人评级:入门级(橙题)【原:黄】

    题意:\(n\) 座城市按数序,各自有独立铁路相连,每段铁路的票均分为两种,且价格各不相同——一种是以高价 \(A_i\) 购买,另一种是先以 \(C_i\) 办卡(一段铁路只需办一次卡)、再以低价 \(B_i\) 购买。现告诉你访问城市的顺序,计算出最少的花费是多少。

    思路:先使用前缀和算法,求出每一段铁路分别经过了几次,再根据售价计算最少的花费。全程开销为 \(O(n+m)\) 。

  7. 洛谷P4440 - [COCI2017-2018#3] Programiranje(源地址自⇔洛谷P4440

    tag:⇔前缀和、⇔个人评级:入门级(橙题)【原:绿】

    题意:给定序列 \(Str\) ,共有 \(k\) 次询问,每次取出 Str[l,r]Str[L,R] 两串子串,判定这后者是否可以通过重新排列得到前者。

    思路:转化题意,就是判断两个区间中,每个字母的数量是否相等。对每一个字母进行前缀和,求出到这一位为止前面一共有多少这个字母,然后差分并输出答案。

  8. CF1253C - Sweets Eating(源地址自⇔CF1253C
  9. CF816B - Karen and Coffee(源地址自⇔CF816B
  10. CF1547E - Air Conditioners(源地址自⇔CF1547E
上一篇:java泛型——同一类型


下一篇:日常Harbor运维镜像-持续更新