250801

今天繼續完成前面的題目，包括 CF571A和前兩次比賽的C題

CF571A

發現直接求比較困難，考慮求出總方案數再減去不合法的方案

枚舉加上的數字 \(k\) ，可將 \(k\) 分為 \(3\) 個數的問題轉化為 \(k\) 個小球外加 \(2\) 個擋板，則方案數為\(C_{k + 2}^{2}\)

對于不合法的方案數，不合法的情況一定滿足，\(a', b', c'\)中存在一個數 \(＞\) 其它兩個數的和，枚舉該數并保證當前總長度加上其它兩個數的和小于枚舉的數

250802

A

期望：\(100\) \(\quad\) 實際：\(55\) \(\quad\) 耗時 : \(80min\)

枚舉答案并進行校驗，考試的時候枚舉的范圍過大導致超時。

前面花了不少時間，所以考試時過了大樣例就沒管了，完全沒有發現寫了一個毫無用處的枚舉

B

期望：\(25\) \(\quad\) 實際：\(25\) \(\quad\) 耗時： \(1h\)

一開始看到只會第一檔和第五檔的，后面發現第二檔分討一下即可得到

其實子任務\(2\)會做后\(3, 4\)兩檔分也容易得出，只是多了幾個段而已，這\(20\)分應該要拿

然后子任務\(5\)是暴力\(dp\)，考場上最后試著寫了一下沒寫出來，實際很簡單......又是20分

所以其實這題即使不會正解暴力分也有不少，不應該只拿這點分

C

期望：\(0\) \(\quad\) 實際: \(0\) \(\quad\) 耗時 ： \(20min\)

考試看到完全不會，壓根沒想連通塊，實際上\(m \le 2000\) 已經很明顯了。

前 \(20\) 分把合法的邊選出來加入并查集，直接算答案就行，這檔分是一定要拿的

對于第二檔 \(k\) 為 \(2\) 的冪次的情況，說明 \(k\) 與 \(d_i\) 二進制下前面幾位要相同， 可按照 \(d_i / k\) 分組， 還是并查集做，這檔也算是想想能夠到的吧

D

期望：\(25\) \(\quad\) 實際：\(0\) \(\quad\) 耗時 ： \(45min\)

第二檔分，\(x = y\) 的情況相對還好寫點，\(x = y\) 說明操作只與\(AB\)的個數有關， 且如果\(AB\)個數合法，就一定能加出來

250803

今天主要復習圖論。

A （CF1255C）

看完思考了大概\(15min\)，思路比較簡單，實現稍微麻煩點

\(p_1, p_n\)只會被覆蓋一次，\(p_2, p_{n - 1}\)會被覆蓋兩次，同時 \(p_1, p_2\) 一定在同一個三元組中，所以找到\(p_1\)以后就能找到 \(p_2,p_3\) ，以此類推就都能找

B （P9650）

對于多個終點的問題卡了一會，同時對于至多\(d_i\)個出口需關閉的問題不會。

至多 \(d_i\) 個出口關閉，則對于最短路過程中到達的每個點，由于該點是當前權值最優的點，判斷該點當前是否還要封閉出口，如果要就封鎖，否則繼續轉移加邊

類似這種多個終點反著來跑的做法比較套路，反應速度還要加快，出口關閉的問題要結合做法的根本原理。

C （P5839）

求出了由一個顏色修改為另一個顏色的最小花費，剩下不知道怎么做

實際上 \(dp\) 就行, \(dp_i\) 表示前 \(i\) 位均組成連續 \(\ge k\) 的段的最小代價，前綴和計算出 \((i，j)\) 之間填顏色 \(c\) 的代價 \(S(i, j, c)\)，轉移就是 \(min(d_j + S(i, j, c)), j \le i - k\)

枚舉 \(j\) 不可行，可將前綴和拆開，維護前綴最小值 \(v_c = min(d_j + s_{j, c})\)，便可進行\(O(1)\)轉移

這個 \(dp\) 包括優化都不算難，應該是要想到的，優化部分通過決策集合單調遞增可以推出。

H （P6062）

二分圖匹配，不太記得了都，稍微復習了下

250804

A （0/30, 2h）

一直在想\(60\)的做法，式子顯而易見但考試的時候方案數推錯了，還有組合數預處理的時候范圍只寫到了n導致答案不對。

然后到最后才去寫了前兩檔的分，沒寫完于是一分沒有。

不會二項式定理，但至少應該寫出60分。

二項式定理：\((a + b) ^ n = \sum_{k = 0} ^ {n} C_{n}^{k} \times a ^ {n - k} \times b ^ k\)

B （40/40, 30min）

前面兩檔分可以搜索或者\(dp\) 實現

C （25/25, 35min）

看完就寫了前兩檔暴搜的分 發現部分分給的很多 本打算再想一下的但寫前面的去了
dp可以實現后面幾檔分 稍微想一下應該要寫出來的

D （20/20, 30min）

看完第二檔分的條件后覺得可做 但后面發現不會找是否存在另一條為d+1的邊

總結

時間分配很不合理，T1浪費了太多時間還沒得分非常不應該，當一檔分寫了很久還沒寫出來的時候先去寫前面的分保底

250805

完成前幾天的題目

A （CF1679D）

思考了大概20分鐘，不知道怎么處理從每個點開始的問題，題目中最小化最大值明顯可以考慮二分，這點沒有想到，然后判斷是否存在長度為\(k\)的鏈或環可以用拓撲排序。

250806

今天主要復習樹的相關知識

A （CF1336A）

思考約20min，想到一個點若作為工業城市，則其下面的點應均為工業城市才為最佳選擇方案，可以貪心選取，實現比較容易，大概10min

B （P5536）

想了大概15min不會，看到最小化最大距離還想了下二分，但也不知道怎么判斷一個距離是否可行。

實際上需考慮什么時候時最大距離，對于任意一點，樹上距離最遠的即為直徑的一個端點，而在直徑中點的時候距離最短，沒有想到這一點

實現不算復雜，兩次dfs找到直徑以后從中點再dfs一次計算每個點最遠能走的距離，但計算直徑終點的部分除以二取整有問題，調了很久，大概花了50min

250807

A （50/30, 45min）

看到 $n \le 2000 $ 只有30分有點慌，想了很久也不會別的更快的做法了只能硬寫

\(O(n log n)\) 求最長上升子序列還想了一會，居然還跑過了\(1e4\)這一檔

由于排列是隨機的，可以每次倒著模擬刪除一個元素的過程，如果當前元素在最長上升子序列中就修改后重新計算一遍，否則不管，復雜度可通過

改的時候對于如何判斷當前元素是否在最長上升子序列中還卡了一會，實際上只要每次轉移的時候記一下自己前面的數，最后標記一遍即可

隨機數據 這么做確實是想不到，下次或許可以試著想一下數據隨機時的性質？

B （0/0, 1h）

看完題大概15min想到了暴力做法，對應第二、三檔，但是沒有考慮單獨的0的問題，導致答案錯誤

其實這個問題隨便造組樣例就能調出來，考試的時候因為寫了比較久，腦子有點亂，看了其他樣例也沒發現問題，這兩檔肯定要寫出來的。

C （5/5, 25min)

考試時對于a = 0不會計算兩個不同數字之間插了以后還能再插的情況。

D （0/10, 40min）

搜索都能掛了，因為沒開longlong 加上有可能一個點有多條限制的情況

第二檔和第三檔分可以dp，考試時有嘗試過。

總結

主要還是各種要命的細節問題，試樣例的時候仔細點，過了樣例也再檢查一下

250808

主要練習數論

A （CF947A）

思考大約10min，沒有想到\(x_i - p_i + 1 < x_{i - 1} < x_i\) 這一結論。

題目中已經給出了 \(x_{i - 1} < x_i\) 以及 \(p_i\) 是\(x_{i - 1}\) 的倍數, 應往三者大小關系的方向考慮

B （CF1499D）

想了大概25min，將\(lcm(a,b)\) 轉化為了 \(\frac{ab}{gcd(a,b)}\) ，但是不知道怎么繼續。

實際上只要把\(a, b\) 繼續表示為\(gcd(a, b) * k\)的形式， 將 \(gcd(a, b)\) 用已知數和\(k1, k2\)表示便可計算答案。

對于這種式子，應當考慮將主要的未知數(例如本題中的gcd(a,b)）用已知表示，便于計算

C （P12021）

思考15min，主要不會在如何確定選的數，以及對于每次選的不同的數都要符合要求不選k倍的數

關鍵在可獨立考慮每個集合的方案數，便能夠進一步推出計算方案的方式

250809

補完了前天考試的B題 （CF1584E）

一段區間若合法，則需每個子區間都要滿足奇數位的和等于偶數位的和，寫的時候在加減號交替和刪去map中不合法元素的地方理解了很久，照著推了個樣例就明白了

250810

A (20/40, 40min)

k = 2 的情況分討了半天但是寫錯了，易發現答案很小。

B （60/60， 30min）

暴力做法很快就能想出，考試時沒有看出二分的性質，正解應該是二分+st表

C（30/30，20min）

65分內都可以用背包做，實現比較容易，應該要寫出來的

D （0/20， 40min)

前20分就是暴力dp，這檔分應該要拿的，

250811

上午補了之前樹的題單，完成CF1244D, CF1790F

CF1244D

思考了大約20min，發現如果一個節點有兩個及以上的分叉，則無法滿足題目中連續三個點顏色不得相同的要求

所以就很簡單了，必須為一條鏈的形式，枚舉前兩個點涂的顏色計算最小答案即可，實現大概10min

CF1790F

思考10min，大概只會暴力做法，后面才知道復雜度是正確的.

還有\(O(n log n)\)的做法

下午完成CF2049

前面幾道題很簡單，前四題花費大概50min

E題思考了大概20min，一開始不知道怎么線性算出每個數與別的數的異或值，后來想到了可以一位一位的考慮，統計出整個數組第i位為1的數的個數，根據當前枚舉的數第i位的值分別計算答案

F題一開始想的是先處理出一個大小為k的矩陣然后再粘很多遍，但是發現還是會有相鄰的相同的問題，來回改了很久，大概30min

后面重新想了一遍其實就是直接按順序填就行，但如果m為k的倍數就會有相鄰的相同的問題，所以可以奇數行右移一位，錯開就行

G題

想了25min左右，雙端隊列沒怎么用過，一開始不會翻轉操作，維護正著和倒著兩個序列swap即可。算答案那里稍微推了一會，分別記一下答案和當前序列的和就行。

250812

上午補了CF2049H，并寫了CF2033G

CF2049H

由于l，r較大無法枚舉，所以可以枚舉約數，比較好實現，大概寫了15min

CF2033G

想到暴力枚舉向上走幾步計算一次詢問的答案，設f(u)表示u的子樹內最深的點的深度，沒有想到用倍增優化。

下午完成CF2037

ABC都比較簡單，大概花費30min。

D題思考約25min，題目要求提升的點數最少，一開始看錯了，所以可以遍歷每個障礙區間，如果跳不過去就選取當前符合位置要求的價值最大的能量點，可用優先隊列維護價值大小，實現比較容易，大概花費25min

E題思考30min，每次詢問 \([1, i + 1]\)，記錄當前0的個數和上一個的答案，根據當前和上次的答案之差計算0 / 1 的個數, 大概寫了十幾分鐘

250813

上午完成CF2037F, CF2037G, 昨天知道了思路以后實現都比較簡單

下午完成CF1986

前三題用時45min，其中B題每個點的答案不會受四周點的影響，因為若當前點能夠修改，則四周的點的值比該點都小，所以不會影響答案

D題大概想了25min，看到的第一反應就是有0出現答案就為0，但也有能填的空小于2時的特殊情況。其實不用單獨判，每次枚舉哪個空空出來不填，特判0和1的情況即可

實現花了點時間，一開始沒有考慮 \(\times 1\) 的問題調了一會，大概寫了25min

E題思考20min，一開始沒想到取模，其實就是按取模后的大小計算每個集合的最小答案，要分個數的奇偶性討論。

250814

上午完成CF1986F,CF1986G, 比較好實現

下午完成CF1980

前三題用時50min，時間有點久，主要是C題對于無法匹配的 \(d_j\) 可以重復覆蓋的處理想了一會，寫完大概花了30min。

D題計算每個位置對應的b值，預處理出從前往后/從后往前是否能夠滿足升序，再枚舉刪除的數判斷即可。

寫的時候在邊界處理的地方調了一會，總共花費30min左右。

E題比較簡單，看完題大概想了八分鐘，由于每次修改同一行/同一列的數不會改變，想到了記錄每個值出現的位置，并遍歷整個排列查看是否出現沖突

不過其實不用具體處理如何修改，可以直接將兩個矩陣按照行和列排序，判斷是否相同即可。

250824

上午繼續補前面的題，完成CF1980F1, CF1980F2, CF2033G

其中CF1980的兩道F題是之前講過的，按照橫坐標或縱坐標排序后單調棧維護，計算新的點產生的答案即可

下午完成CF1974(D)

前三題總共用時45min，比較容易，C題一開始減去重復計算的方案減錯了調了一會

D題容易發現x軸和y軸移動互相獨立，所以只要兩個方向步數相等即可，特判一下特殊情況，大概用了40min

E題看到直接想到01背包，但是發現獲得的錢數量太大存不下，可以將狀態改為達到幸福值j最多剩下的錢，然后仍然01背包轉移即可

250825

上午完成昨天的兩題CF1974F, CF1974G

最后一題是反悔貪心 都比較好實現 大概花了75min完成

下午完成CF1955(C)

前三題比較容易 大概花了40min左右完成

D題思路很簡單 就是計算最開始的m個有多少滿足條件的 然后每次后移一個修改答案

但是一開始計算的時候統計合法位置的時候大于小于號弄錯了 導致調了很久時間

總共完成時間大概50min 有點長了要再快點 避免這種細節錯誤

250826

上午完成昨天的兩題CF1955G, CF1974H

其中G題只需要枚舉約束，用bfs/dp校驗一下是否可行即可，類似求最大的最大公約數的題大部分做法都為枚舉

下午完成CF1941(E)

前四題都比較容易，大約花費100min，其中B題的貪心(是貪心嗎 還想了一會

E題看完后很快想到dp算出每一行的最小代價，但一開始沒想到如何優化，可以用單調隊列，實現不難，總共花費約50min

F題最大化最小答案容易想到二分，然后校驗部分也挺好寫的，大概用了45min

250827

上午完成CF1941F, CF1941G。

F題因為二分校驗的時候循環m寫成了n調了很久，還有就是longlong的問題，有幾個變量少開了

下午完成CF1933(C)

前三題花了40min，C題一開始寫的是枚舉k結果沒有判斷指數為0的情況，后面改成枚舉a,b了更好寫一點。

D題很容易想到沒有重復數字的情況，然后剩下的舉幾個例子也很好分析，想了大概8min，實現很短，總共花費15min左右

E題很明顯的二分，求最小的大于0的段，前綴和算出每個跑道的價值。思考約10min，式子推了一會，實現比較容易，大概花費25min

F題由于列是循環移位的，可以將向下和向右的兩個操作轉化為向右下一格和向下兩格，然后bfs即可，大概寫了30min

250828

上午完成CF1933G

下午完成CF1921(D)

前四題都比較容易，用時45min

E題博弈的討論想了很久，沒想到根據相差行數的奇偶性判斷哪方可能贏這一點，然后再根據列來判斷是贏還是平局

討論出一種后另外一種很相似，實現還算容易，總共用時55min

F題是根號分治，在\(d \le sqrt(n)\)時用兩遍后綴和，否則直接計算

一開始想到了用后綴和計算，但沒有考慮到\(d \ge sqrt(n)\)的情況，總共用時30min

250829

補了前面的題目，完成CF1980G，CF1790F1，CF1970F2

第一題前面講過但有點忘了，回憶了下做法，由異或的性質，對每個點記錄前綴異或和，然后根據深度奇偶性分別用兩棵字典樹來記錄異或最大值

后面兩道題是模擬，用map記錄每個球員的位置，注意細節問題，被攜帶的球和人要同步，總共用時80min左右

看了CF1921G，思考20min，對于求三角形的前綴和不會計算