知識點歸類——字首和

字首和與差分相關題目整理

适用題型

1. 使用 \(O(1)\) 的時間求部分和：字首和+差分

   一維——求出數組的某一下标區間内符合要求的元素之和

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

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

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）