洛谷千題復習計劃（一）（Codeforces + AtCoder）

整理的演算法模板合集： ACM模板

點我看演算法全家桶系列！！！

實際上是一個全新的精煉模板整合計劃

每天花一個小時簡單復習一下我寫過的洛谷的題目！
雖然還沒有到千題，但是快了（等我復習完這些以后我 luogu 刷的題目就夠千題了hhh
盡管因為太菜了寫的都是水題嗚嗚嗚

沒有按難度寫題的習慣，結果到現在黑題只寫了7道嗚嗚嗚

紅橙黃綠藍紫黑

%
2019 / 10 / 5 ～ 2021 / 3 / 1 2019 / 10 / 5 \sim 2021 / 3 / 1 2019/10/5～2021/3/1 從大一自學C語言的小菜雞到大二啥都不會的大菜雞，洛谷750 +（含CF 200，UVA 100 ），AcWing 300 +，牛客150 + ，HDU 100 +，POJ 50 + ，CF，AT只算在線比賽大概也有個幾十道，LoJ，BZOJ，51nod 零零碎碎幾十題，vjudge不到不到一百題，搞競賽一年半，也就寫1500道題，其中大多數還都是水題 … 演算法也沒學多少，博客倒是水了600篇，我也太菜了吧（不行，越說越難受，已經開始自閉了 ）

%
luogu 做題情況：
（RemoteJudge）CF + AT：188（有好多比賽的時候寫的題沒去洛谷上交）
（RemoteJudge）UVA + SPOJ：97
洛谷本站題目（P）：484
共769道水題，
每一百題分為一篇，每天兩小時，一小時寫10道，預計一個月內復習完畢

媽呀，我寫過的題怎么都這么水

[AT2271 黃]：思維，組合計數 若有奇數個人，一定有一個人左右差值為 0 否則不合法，從中間往兩邊拓展，一定均存在兩個人的差值為 2，4，6，8… 偶數則沒有為 0 的，往兩邊拓展一定為2，4，6，8，每個位置有兩種選擇，方案數為： 2 ? n ? 2 2^\frac{\lfloor n\rfloor}{2} 22?n??

[AT1350 黃]：搜索 深搜模板題

[AT1058 橙]：模擬 取模模擬回圈 n=(n-1)%s.length();

[AT1219 紫]：回滾莫隊模板 莫隊簡單來說就是離線查詢一些區間的問題，我們可以將所有詢問的區間 [ l , r ] [l,r] [l,r] 存下來，第一關鍵字按左端點的分塊的編號排序，第二關鍵字右端點從小到大排序

bool cmp(const Query& x, const Query& y){
    int a = get_block(x.l);
    int b = get_block(y.l);
    if(a != b)return a < b;
    return x.r < y.r;
}

然后根據詢問的內容進行修改，每次相當于是一個雙指標，拓展到下一個詢問區間擴大或者縮小雙指標 i , j i,j i,j ，并進行相應的增加洗掉操作（例如統計區間同一顏色數量，就修改 cnt 并根據需要修改 res ），時間復雜度是 O ( n n ) O(n\sqrt n) O(nn ?) 一般可以過 1 0 4 ～ 1 0 5 10^4\sim 10^5 104～105 的資料，奇偶排序優化：如左端點L都在奇數塊，則對R從大到小排序；若L在偶數塊，則對R從小到大排序，

回滾莫隊是指需要實作的操作，區間伸長的時候很好維護資訊，區間縮短的時候不太好維護資訊（如最大值，洗掉以后不知道次大值是多少)，我們可以使用回滾莫隊，伸長正常維護，縮短的時候直接回滾到之前備份的地方，

大體上就是還按照普通莫隊的排序方法排序，這樣就可以保證每段內部的詢問，左端點都在同一塊內，右端點遞增，像普通莫隊那樣正常詢問，只不過在伸長的時候備份一下，也就是將 r r r 移動到當前詢問的右端點，保存下來此時的資訊，將 l l l 移動到詢問的左端點，得到求出答案，然后直接用剛才保存的資訊（備份）恢復現場，這樣我們只有伸長的操作，避免了難以維護的縮短的操作，

[AT2412 橙]：前綴和 最后維護長度為 k k k 的答案即可，

[CF869B 橙]：思維 題目要求的是 b ! a ! \cfrac{b!}{a!} a!b!? 的個位是誰，顯然沒辦法暴力，我們知道一旦這里面有 10 10 10 ，那么個位數一定是 0 0 0 ，所以如果 b ? a > = 5 b-a>=5 b?a>=5 ，則 b ! a ! = ( b ? a ) ! \cfrac{b!}{a!}=(b-a)! a!b!?=(b?a)! 中一定存在 2 2 2 和 5 5 5， 2 × 5 = 10 2\times 5=10 2×5=10 ，個位數為 0 0 0，否則暴力列舉計算即可，

[CF825E 藍]：拓撲排序，貪心 一個有向圖，要求輸出字典序最小的 1 ～ n 1\sim n 1～n 的排列，也就是這 n n n 個點編號的排列，使得父結點的編號大于子節點，顯然就是求一個拓撲序，但是不是普通的優先佇列拓撲排序，因為這里不是給定所有的點的編號求順序，而是讓我們幫他編號，那么就直接貪心，我們建反邊，這樣拓撲排序的時候先出來的是子節點，我們給子節點貪心地賦當前剩余的最大值即可，

[CF805B 橙]：構造 構造長度為n的以’a’,'b’構成的字串，使得其中不存在長為3的回文子串，顯然構造成 a a b b a a b b a a b b a a b b ? aabbaabbaabbaabb\cdots aabbaabbaabbaabb? 即可，

[CF786B 紫]：線段樹優化建邊，最短路 其實拋去建圖就是一個最短路的模板，只是連邊的方式不同，這里的連邊是可以每次連接兩個點（全部都是有向邊），或者將一個點與一個連續區間的點相連，或者將一個連續區間的點與這一個點相連，暴力 O ( n 2 ) O(n^2) O(n2) 資料 n ≤ 1 0 5 n\le 10^5 n≤105 不可過，其實仔細想想，他的提示性很強，連續區間，這不就是線段樹嘛，我們可以直接建一顆父結點連一個有向邊到子節點的線段樹，一個點與一個連續區間連邊，我們直接將這個點與該區間的父結點連邊即可，至于區間向某一個點連邊，我們再建一個棵線段樹在樹上反向建邊就可以了，記得建線段樹的時候線段樹的編號不要重復即可，(Code)

[CF776B 黃]：質數 數 2 ～ n ? 1 2\sim n-1 2～n?1 ，A是B的素因子，則A與B的顏色不同，問染色方案，用最少的顏色，輸出需要用的顏色方案數以及染色方案，顯然所有素數互素，可以是一種顏色，所有合數， 2 ～ n ? 1 2\sim n-1 2～n?1 中一定含有素因子，是另一種顏色即可，注意特判一下序列里沒有合數的情況，顯然只用到了 1 種顏色，

[CF743C 黃]：小學數學經典轉換 給定 n n n ，求 x , y , z x,y,z x,y,z 滿足： 1 x + 1 y + 1 z = 2 n \cfrac {1}{x} + \cfrac{1}{y} + \cfrac {1}{z} = \cfrac {2}{n} x1?+y1?+z1?=n2?，顯然 1 x + 1 y + 1 z = 1 n + 1 n \cfrac {1}{x} + \cfrac{1}{y} + \cfrac {1}{z} = \cfrac {1}{n}+\cfrac {1}{n} x1?+y1?+z1?=n1?+n1?，若 1 x = 1 n \cfrac {1}{x} = \cfrac {1}{n} x1?=n1?，則 1 y + 1 z = 1 n \cfrac{1}{y} + \cfrac {1}{z} = \cfrac {1}{n} y1?+z1?=n1?，顯然 1 n ? 1 n + 1 = 1 n ( n + 1 ) \cfrac{1}{n}-\cfrac{1}{n+1}=\cfrac{1}{n(n+1)} n1??n+11?=n(n+1)1?，即： 1 n = 1 n + 1 + 1 n ( n + 1 ) \cfrac{1}{n}=\cfrac{1}{n+1}+\cfrac{1}{n(n+1)} n1?=n+11?+n(n+1)1? 故 1 y = 1 n + 1 \cfrac{1}{y}=\cfrac{1}{n+1} y1?=n+11?， 1 z = 1 n ( n + 1 ) \cfrac{1}{z}=\cfrac{1}{n(n+1)} z1?=n(n+1)1? ，輸出即可，

[CF915A 紅]：模擬 暴力列舉取最大值，或者用優先佇列，

[CF853A 藍]：簡單優先佇列貪心 設第 i i i 架飛機的時間安排為 d i \displaystyle d_i di??， 則總花費為 ∑ i = 1 n ( d i ? t i ) ? c i \displaystyle \sum_{i=1}^n{(d_i-t_i)\cdot{c_i}} i=1∑n?(di??ti?)?ci? 即 ∑ i = 1 n d i ? c i ? ∑ i = 1 n t i ? c i \displaystyle \sum_{i=1}^n{d_i\cdot{c_i}} - \sum_{i=1}^n{t_i\cdot c_i} i=1∑n?di??ci??i=1∑n?ti??ci?
? t i ? c i t_i\cdot c_i ti??ci? ?不變，故 d i d_i di? ?需要盡量的小，因為同樣是等，同樣都要花錢，費用大的多等就會多花錢，不如讓他先走，花費小的再等一會，使得總花費最小，于是我們可以 c i c_i ci?排序，盡量向小的取，顯然使用優先佇列，并且根據題目的限制，我們每次只能把起飛時間小于等于 i i i 的放入優先佇列里，因為起飛時間也就是編號，所以從合法起飛時間的起點 k + 1 k+1 k+1 開始回圈，然后搞一個指標 cnt ， 所有 cnt <= i 的再放到佇列里，并且每次起飛一架飛機，并算一下花費即可，（Code）

[CF777A 橙]：模擬 顯然就是找回圈節的題目，發現回圈節是 6 6 6 ，打表方案輸出即可，

[CF701C 黃]：雙指標 顯然直接雙指標，開一個桶記錄一下一共有多少種顏色，然后雙指標跑一遍，包含了所有顏色就更新答案，（有莫隊模板題那味了hhh）

[CF662C 黑]：矩陣翻轉 + FWT 這題其實挺離譜，本來應該是一個DP，然后發現 n ≤ 20 , m ≤ 1 0 5 n\le 20,m\le10^5 n≤20,m≤105，正常人肯定能立馬想試試能不能狀態壓縮，然后發現我們不僅可以狀壓行翻轉狀態，對于每一個列的01狀態因為只有 n n n 行，所以也可以狀壓，并且我們要求的答案可以 O ( 1 ) O(1) O(1) 貪心直接得到，矩陣翻轉其實就可以寫成異或的形式，列出來一個答案的式子，發現跟 FWT 有點像，經典轉換之后就變成了 FWT 的模板了，太棒了，直接卷就行了hhh（Code）

[CF660C 藍]：雙指標 顯然我們直接雙指標，輸入的時候前綴和統計一下區間里 1 1 1 和 0 0 0 的個數，如果 0 0 0 的個數小于等于 k k k 就用區間長度更新答案，如果大于了就移動指標，最后取最值輸出即可，（Code）

[CF632A 紅]：模擬 經典老奶奶賣蘋果，直接倒推就行了，每次求和，如果沒有送的話就直接乘2，送了的話就乘2+1，因為蘋果一定是整數個嘛，最后有一半是自己賣出去的，一半是多加的，輸出 sum * p / 2 即可，

[CF510D 紫]：裴蜀定理+最短路 因為每買一張牌，就可以獲得 l [ i ] l[i] l[i] 跳躍能力，我們想要能夠跳到所有的位置，顯然可以想到 裴蜀定理 ，并且本題想要求最小的花費，也就是說題目變成了找到兩個或者多個最便宜且他們的 l [ i ] l[i] l[i] 是互質的數，顯然是一個動規問題，但是因為資料較大，動規比較難寫，我們發現其實可以轉換為一個圖論問題，因為選擇若干個數，實際上可以看作是從某一點出發，選擇了哪些點就是走過了哪些點，即從 0 0 0 開始 x = 0 x=0 x=0，for 回圈選擇了 l [ i ] l[i] l[i]，即從點 x x x 出發，而點 x x x 能到的點是 y = gcd ? ( x , l [ i ] ) y=\gcd(x, l[i]) y=gcd(x,l[i])，中間最短路求的是能到達的點 y y y 的最小花費 d i s t [ y ] dist[y] dist[y]，最后的答案即走到點 1 1 1（實際意義是所走的所有點的 gcd ? = 1 \gcd=1 gcd=1 ）最小花費即 d i s t [ 1 ] dist[1] dist[1] ，（Code）

[CF498C 紫]：首先顯然我們選擇的兩個數 ( i , j ) (i,j) (i,j) 操作之后， a [ i ] a[i] a[i] 與 a [ j ] a[j] a[j] 均除以他們的公約數而不是最大公約數，也就是說如果一次操作中我們選擇的 v v v 不是質數，那顯然把它拆成若干次 v v v 是質數的操作更優（因為任何一個合數都可以拆成若干個質數的次方的乘積，唯一分解定理，這樣拆成質數最后操作的次數會更多），那么問題就變成了：每次選取滿足要求的一對數，同除一個質數，問能操作多少次，我們發現題目中還有一個重要的條件： i k + j k i_k+j_k ik?+jk? 為奇數，那么 i k i_k ik? 和 j k j_k jk? 一定有一個是奇數，另一個是偶數，因此我們可以把數列中的元素按下標的奇偶分成兩個集合，感覺有點像二分圖了，最多的操作看上去好像是一個二分圖匹配，注意到 v v v為不同質數時的操作是不會相互影響的，因此我們將數列中的元素質因數分解，時間復雜度為 O ( n a i ) O(n\sqrt{a_i}) O(nai? ?) ，我們發現，進行一次操作實際上就等價于，找到了一條關于質因子的匹配邊，那么問題就變成了二分圖最大匹配，也就是將輸入的點都質因數分解，這樣一個點拆成多個點，然后建圖跑一次最大流即可，實際意義就是每次選取兩個相同的質因子跑一次匹配，也就是操作一次，最多的操作次數就是最大匹配邊數，（Code）

[CF485A]
[CF476D]
[CF453D]
[CF448C]
[CF438E]
[CF429D]
[CF294C]
[CF282A]
[CF280A]
[CF266B]
[CF263A]
[CF231C]
[CF190C]
[CF189A]
[CF156D]
[CF136A]
[CF117C]
[CF71A]
[CF62A]
[CF56A]
[CF43A]
[CF38C]
[CF38A]
[CF37A]
[CF35A]
[CF34A]
[CF33A]
[CF32B]
[CF32A]
[CF29A]
[CF27A]
[CF26A]
[CF25B]
[CF25A]
[CF22A]
[CF20C]
[CF20A]
[CF16A]
[CF14A]
[CF12E]
[CF12A]
[CF11B]
[CF11A]
[CF10B]
[CF10A]
[CF9A]
[CF7C]
[CF6C]
[CF6B]
[CF6A]
[CF5C]
[CF5A]
[CF4C]
[CF4B]
[CF4A]
[CF3C]
[CF3B]
[CF3A]
[CF2A]
[CF1B]
[CF1A]
[CF978D]
[CF978C]
[CF993C]
[CF1015D]
[CF1015C]
[CF1015B]
[CF1066D]
[CF1066B]
[CF1070E]
[CF1108F][
CF1108D][
CF1108B]
[CF1108A]
[CF1144F]
[CF1144E]
[CF1144D]
[CF1144B]
[CF1144A]
[CF1177A]
[CF1182A]
[CF1108E1]
[CF1203E]
[CF1245D]
[CF1280A]
[CF1293B]
[CF1295C]
[CF1295B]
[CF1295A]
[CF1296B]
[CF1296A]
[CF1307D]
[CF1307C]
[CF1307B]
[CF1307A]
[CF1355E]
[CF1355D]
[CF1355C]
[CF1355B]
[CF1355A]
[CF1358A]
[CF1385E]
[CF1385B]
[CF1385A]
[CF1382A]
[CF1384A]
[CF1399E1]
[CF1399D]
[CF1399C]
[CF1399B]
[CF1399A]
[CF1393A]
[CF1391A]
[CF1398D]
[CF1398C]
[CF1398B]
[CF1398A]
[CF1401F]
[CF1401C]
[CF1401B]
[CF1401A]
[CF1400A]
[CF1397B]
[CF1397A]
[CF1409E]
[CF1409D]
CF1409C]
[CF1409B]
[CF1409A]
[CF1407D]
[CF1408D]
[CF1413C]
[CF1437D]
[CF1471B]
[CF1471A]
[CF1470D]
[CF1470C]
[CF1470B]
[CF1470A]
[CF1474C]
[CF1474B]
[CF1478C]
[CF1478B]
[CF1478A]
[CF1477C]
[CF1477B]
[CF1477A]
[CF1485F]
[CF1485D]
[CF1485C]
[CF1485B]
[CF1485A]
[CF1481F]
[CF1481E]
[CF1481B]
[CF1481A]
[CF1480B]
[CF1480A]
[CF1479B2]
[CF1479B1]
[CF1479A]
[CF1492D]
[CF1492C]
[CF1492B]
[CF1492A]

我好菜，就沒怎么寫過Div1的最后一題，補都不想補