云落碎碎念

1. 題面翻譯取自 luogu，本蒟蒻也會安置原題鏈接
2. 不保證文章中不出現(xiàn)“顯然”或者“注意到”，可能會出現(xiàn)“易證”
3. 有寫錯的地方歡迎各位神犇指正

前言

只有陽光灑在身上的時候，我才發(fā)覺冬天那刻骨銘心的寒。

動態(tài)規(guī)劃 or 找性質專場。

CF573A

題解

題目傳送門

簡單數(shù)論題，給每個數(shù)刨去 \(2,3\) 的質因子，對剩下的部分判等。

時間復雜度上是沒有問題的，不需要分解質因數(shù)，直接試除法就能行，單次 \(/2\)，所以每個數(shù) \(\log\) 次。

細節(jié)處理

感覺上沒什么細節(jié)。

CF573B

題解

題目傳送門

我真是服了，被 DP 題暴打了，結果一看，是個黃題……

一開始想歪了，上去就是一套二分答案，然后不可做，死活沒想到 DP 可以轉移。

記 \(f_i\) 表示 \(i\) 這根柱子被摧毀的最小時間，有轉移：

然后我就卡在這里了，根本不知道這個東西怎么去轉移。

后來說可以正著掃一遍，再倒著掃一遍，給我看傻了……

實際上可以這么去理解，記 \(l_i\) 表示只考慮 \(1 \to i\) 的摧毀順序，\(i\) 的摧毀時間；\(r_i\) 表示只考慮 \(n \to i\) 的摧毀順序，\(i\) 的摧毀時間。

顯然有 \(f_i = \min(l_i,r_i)\)。前面的 \(l_i,r_i\) 都是好轉移的，所以直接做做完了。

細節(jié)處理

注意一下 \(+1/-1\) 的邊界，建議 1-index，否則容易出現(xiàn)下標越界。

CF573C

題解

題目傳送門

難點和關鍵點非常明確，就是對條件進行充要轉化。

記 \(P_1\) 為所有度數(shù) \(\le 2\) 的點構成的集合，\(P_2\) 為所有度數(shù) \(=3\) 的點構成的集合，\(P_3\) 為所有度數(shù) \(\ge 4\) 的點構成的集合。

給出的樹合法，當且僅當——

存在一條鏈 \(s\) 覆蓋點集 \(P_3\)，且鏈 \(s\) 的鄰域覆蓋點集 \(P_2\)。

嘖，如果這個結論是對的，可以直接先把這條鏈抓出來（抓不出來就不合法），然后擴展鏈的兩個端點，判一下鄰域就好了。

---

接下來證明這個結論是等價轉化。

充分性

構造方式顯然：把 \(s\) 丟到第一行，把 \(P_2\) 的所有點丟到第二行，剩下的按著編號補齊就行。

大概長成這樣子……

必要性

對于存在鏈 \(s\) 覆蓋 \(P_2\) 這一條件，可以考慮反證法。

假設存在鏈 \(s\) 不覆蓋 \(P_2\) 可以滿足條件，則一定有結點 \(u \in P_2\) 與其它結點不在同一行。然后會出現(xiàn)類似下圖的東西，就寄了。故假設不成立，結論得證。

對于鄰域覆蓋 \(P_1\) 這一條件，和上面條件類似，反證法之后也會出現(xiàn)下圖狀物，所以假設不成立。

---

既然是充要條件，那么就可以直接構造這樣的結構，構造不出來就不合法。

細節(jié)處理

沒寫代碼，不過感覺代碼也就是簡單 DFS 練習題。

CF573D

題解

題目傳送門

并非難題，有人直接 \(O(nQ)\) 的 DP 草過。

如果沒有不能騎自己的馬的限制，顯然是一個圖匹配的形式，經(jīng)典排序后小連小，大連大。

然后你考慮不能騎自己的馬，可以猜測就是在上面的基礎上進行一點小調整。

嘖這個小交換就是自己及其周邊進行一個輪換，根據(jù)經(jīng)驗，這個輪換的大小不會超過 \(3\)。

然后你就可以寫出一個 \(O(n)\) 的 DP 轉移，但問題是還有 \(Q\) 組多測。

考慮把轉移刻畫成矩陣的形式，直接 DDP 維護即可。

時間復雜度 \(O(n \log n \times c^3)\)，其中 \(c=3\)。

細節(jié)處理

全在線段樹的 modify 上，但也沒什么辦法，只能硬調。記得開 long long。

CF573E

題解

題目傳送門

好題。

像我這樣的蒟蒻，也可以做到一眼 \(O(n^2)\) DP，然后就沒有下文了。

樸素 DP 轉移如下：

根據(jù)題解區(qū)，各路神仙直接開始證明，觀測到上述兩種轉移是存在一個分界點 \(k\) 的?？吹奈依涎刍杌?，欲生欲死的。

當 \(i\) 固定的時候，對于 \(j \in [1,k-1]\)，\(f_{i,j}\) 都用 \(f_{i-1,j-1}\) 去轉移，而對于 \(j \in [k,i]\)，\(f_{i,j}\) 都用 \(f_{i-1,j-1}+a_i \times j\) 去轉移。

可能這道題目給我的啟示并非是花里胡哨的證明，而應該是對這種 DP，有全新的優(yōu)化思路。對于一種結構相當固定的 DP 來說（且無法用熟知的優(yōu)化方式去降復雜度），不妨打表，對轉移點進行一個刻畫。

現(xiàn)在假設我們已通過打表獲得了和題解區(qū)類似的結論，考慮優(yōu)化。

你發(fā)現(xiàn) \(i\) 這一維度可以直接丟掉，顯然是先二分出 \(k\)，然后上數(shù)據(jù)結構維護 \(f\) 數(shù)組。

顯然 \([1,k-1]\) 的部分都不用變，而 \([k+1,i]\) 的部分由原來的 \([k,i-1]\) 轉移而來，相當于后綴加等差數(shù)列，是好做的。然后你發(fā)現(xiàn)多了一個現(xiàn)在的 \(k\)，有之前的 \(k-1\) 轉移過來，相當于單點插入。

問題轉化為需要一個數(shù)據(jù)結構，支持單點插入，區(qū)間加等差數(shù)列，單點求值。

其實數(shù)據(jù)范圍不大，可以根號算法，當然最好的做法肯定是手搓平衡樹。

細節(jié)處理

不要忘記初始化。

后記

加油！堅持??！相信自己！

完結撒花！