我咋高一了。

2025.9.1

語文老師兼班主任說，她高中時候是理科班，語文全靠感覺結果高考炸成 100。語文課的時候真的沒有點名讓我回答問題！！！

開學之后真的好忙啊。

ln：你初三的時候在哪個班？

我：1 班。

ln：欸我不是帶了半學期 1 班的嗎怎么沒見過你是不是學競賽去了

我（偷笑）：……

我都還記得到《我與地壇》是 ln 上的，我作文歷史最高是 ln 改的。

9.2

開學典禮。莫名其妙念完了演講稿。

立體幾何好難，不是我喜歡的圖形，我直接解析。

9.3

化學課 wyx 抽問硝酸鹽的分解規律，為什么我的筆記上沒有。Mg 及其以前分解為亞硝酸鹽和氧氣，Cu 及其以前分解為氧化物、二氧化氮和氧氣，Ag 與 Hg 分解為單質、二氧化氮和氧氣，本質上是氧化物二步分解為單質和氧氣。

晚二有神秘英語考試，原來是跟高一一起考，考的是初三難度題目，以為 race 不能及物錯了個完型沒能 AK 非常不爽。為什么我們去年第一次跟高一考英語難度完全不一樣，完型選項全都是生詞（

今天實在是太充實了，充實到一抬頭就 22:00 了。

9.4

文言文真好玩，運動學真好玩，硫與氮真好玩，立體幾何一點都不好玩。

中午看到數競上午考試題，發現最后一題組合是一個神秘構造，花了 15min 想出構造方案有 5pts，剩下的證明還有 45pts（

CF2135D2 From the Unknown (Hard Version)

這種東西不知道為什么我直接就想到塞一堆 \(B\) 進去，對于 \(W<B\) 的情況查 \(B\times B\) 個 \(1\)。對于 \(W\geq B\) 的情況，預處理對應的第一次詢問答案，二分出對應區間然后隨便亂做就可以了。

9.5

下午第一次大體鍛，集合之后我直接自習。但是作業還是剩好多。

9.6

不神秘模擬賽。T1 T2 看出結論之后就好做，但是 T2 需要高精度，不知道為什么我的單次 100 次簡單運算的超絕壓位高精跑得飛快，也懶得優化了。T3 比較簡單，樹上背包板子。T4 想了很久還是不會，寫 FWT 但是第一步點雙轉化就錯了（考場上想成了邊雙）所以 32pts -> 12pts。賽后發現和暴力一個分很不爽。

賽后補題直接手撕矩陣求逆，沒有逆的情況花了一點時間。

9.7

數學作業好難，兩節晚自習都沒做完。

9.9

今天化競回來了。

下午被拉去拍了神秘教師節祝福視頻。

9.10

晚上英語考試錯了一個七選五、一個完型、一個語填、一個單詞填空，很不爽。

9.11, 9.12

不知道在干什么。

9.13

又是神秘模擬賽環節。

開場先想 T2，過了 50min 才會 70pts。這時 tzy 和 xyt 在旁邊差不多過 T1，然后我回去做發現是 10min 奇妙貪心。

然后一直想 T2 都不會，T3 懶得寫暴力，最后 1h 給 T4 寫了個維護 dp 差分數組的玄學算法，懶得離散化，反正是玄學算法。

賽后發現 T4 跑了 60pts，加個離散化就過了（（（

區分度還是太差了，我打成這個樣子都沒被區分掉。

9.14 ~ 9.19

在軍訓。中間想出了一個 ds 一個圖計數，而且都沒有假掉，又可以組比賽了。

比較有趣的是 9.18 晚上提前回教室后不知道為什么特別想飆高音，結果異常輕松地上了 E5（然后被圍毆了（結果第二天就不行了

被通知又要寫演講稿，這個周末又沒了。數學作業還沒寫完呢（（（

9.20

CSP-S1 2025。比去年簡單太多了。1h 邊做邊檢查 AK 了。由于剩的時間太多去檢查差點改錯了一個選擇（（（

9.21, 9.22

心態炸裂的兩天。感覺換成半年前的我會直接趨勢，但是半年前的我似乎也不可能碰上這么多爛活。

40min 定時作文寫到 800 字發現偏題了。班主任批判了我們的綜合基礎。

好困好困。

9.23

今天是秋分哦。

下午有藝術課，認五線譜講了兩節課，憑借絕對音感和三年前的聲樂經驗殺穿了。

累似了。

9.24

星期三不妙日。整天在非常壓抑的氛圍中度過。英語定時由于沒時間完型和語填爆丸了。語填沒有時間分析句子結構導致爆了 3 個。作業根本寫不完（（（

9.25

上午回 cqbzhf 做神秘發言。這個座談會把座位安排到第一排脖子真的會傷到（（（

出來之后偶遇初一班主任（（（

聽 TQ 說因為我和 yb 那邊的中考最高分體育都沒滿，這一屆初三上強度了。我說為什么我們去年這個時候晚上還沒開始加訓。

逃掉了一上午的課，但是代價是又落了一大車任務沒做。

聽聞月末要跟著高二月考，但是隔壁班不用。

CSP-S1 查分，沒掛，AK 了。

P13863 [SWERC 2020] Decoration

熱身題目。

對于 \(x\in[0,N)\)，有且僅有一個 \(y\in[0,N)\) 可以接在 \(x\) 后面。

連一條 \(x\rightarrow y\) 的有向邊，整張圖為內向基環樹森林，一個合法的序列是一條長度為 \(K\) 的路徑。

枚舉每個點作為起點模擬即可，需要注意不能有相同的數，也就是點不能重復經過。

UOJ187 [UR #13] Ernd

接水果肯定首先要按時刻 \(b\) 從小到大的順序，考慮 dp。令 \(dp_i\) 表示考慮前 \(i\) 個水果，接到第 \(i\) 個水果的最大分數。

不妨定義 \(i\) 可達 \(j\) 當且僅當 \(b_i\leq b_j\) 且 \(|a_i-a_j|\leq b_j-b_i\)，就是說接了 \(i\) 之后下一個可以接 \(j\)。

轉移的時候，對于 \(i\) 枚舉 \(j\) 滿足 \([j,i]\) 都接到，再枚舉 \(k\) 滿足 \((k,j)\) 都沒接到（作為上一個連續段的末尾），有轉移 \(dp_i\leftarrow dp_k+(i-j+1)^2\)，要求 \(k\) 可達 \(j\)，\(\forall p\in[j,i)\)，\(p\) 可達 \(p+1\)。

那么將轉移分為 \(k\) 到 \(j\) 與 \(j\) 到 \(i\) 兩部分，先考察第一部分：

求 \(\max_k dp_k\)，要求 \(|a_k-a_j|\leq b_j-b_k\)。經典地，拆開絕對值，等價于 \(a_j-a_k\leq b_j-b_k\) 與 \(a_k-a_j\leq b_j-b_k\) 同時滿足，是二維偏序狀物（由于右邊 \(b_j-b_k\) 非負才可能成立，所以這個二維偏序要求了 \(b_j\geq b_k\)）。按其中一維排序，拿個數據結構維護另一維最小值即可。

第二部分：

是一個形似 \(dp_i=\max_j f_j+(i-j+1)^2\) 的東西，要求可以連續接下 \([j,i]\)。由于可達的描述有傳遞性，把所有極長的可達鏈拿出來，就變成了序列上 \(dp\)。這是經典的斜率優化，由于 \(x,y,k\) 全部單調，可以用各種方法做到 \(O(n)\) 或者 \(O(n\log n)\)。

P12602 指鹿為馬

下面字符串下標標號從 \(1\) 開始。

單串匹配求期望容易想到利用 KMP 自動機。定義 \(dp_i\) 表示抵達狀態 \(i\) 的期望，有 \(dp_n=0\)，要求 \(dp_1\)。

轉移比較簡單：\(dp_i=1+\sum_cdp_{\delta(i,c)}P_{s_i,c}+[\delta(i,c)=0]E_{s_i}\)。其中 \(s_i\) 表示第 \(i\) 個字符，\(P_{s_i,c}\) 表示 \(s_i\) 的下一個字符生成 \(c\) 的概率，\(E_{s_i}\) 表示從 \(s_i\) 開始生成到首字符（\(s_1\)）的期望次數。這里的 \(E\) 可以直接高斯消元求出。

關于這里為什么有一個 \(E\)，如果認為初狀態是 \(0\) 當然不需要，但是初狀態是 \(1\)（有一個初始字符），所以這里實際上是把 \(dp_0\) 直接丟掉沒管。加上 \(dp_0\) 的狀態的話需要考慮空字符后面接一個字符的概率是多少的問題，還不如這個 \(E\) 來得直接。

乍一看這個轉移是有環的，但是增廣矩陣看起來是比較特殊的稀疏矩陣，第 \(i\) 行除了常數，\(> i+1\) 的列全都是 \(0\)。

如果把含 \(dp_{i+1}\) 的項全部放在一邊，另一邊除了常數一定是 \(\sum k\times dp_{j},j\leq i\) 的形式（根據 KMP 自動機的定義，\(\delta(i,c) \leq i+1\)）。

按照移項后的式子得到的是一個三角矩陣，相當于已經高斯消元好了，轉移是 DAG，所以用 \(k_idp_1+b_i\) 表示出所有變元，最后 \(dp_1=-\dfrac{b_i}{k_i}\)，答案需要再加上初始字符的 \(1\)。

時空復雜度 \(O(nm+m^3)\)，其中 \(m\) 是字符集大小。

P13350 「ZYZ 2025」遺傳

顯性和隱性的問題只需要將患病情況取反，下面只討論顯性。

直接去求答案會受到祖先和兒子的雙重限制，不好做。那么反過來直接強制欽定一個生物的基因型，然后求此時整體合法的概率（先不考慮時間復雜度的問題），再除以不加限制的整體合法的概率。

這里整體合法我們定義為：葉子結點的基因型按照基因頻率確定，按照遺傳規律生出子代滿足題目所給患病情況的概率。

設 \(dp_{u,aa/Aa/AA}\) 表示考慮 \(u\) 子樹內部，\(u\) 的基因型為 \(aa/Aa/AA\) 時整體合法的概率。轉移理清細節還是比很多題好寫的。

接下來考慮時間復雜度的問題，注意到每次只有從一個點到根的一條路徑轉移是不同的。由于數據隨機生成，樹高是 \(O(\log n)\)，單次做 \(O(h)\) 就可以直接做到 \(O(n\log n)\)。

P12462 [Ynoi Easy Round 2018] 星野愛久愛海

先考慮暴力，對 \([l,r]\) 建出虛樹，貪心地想肯定是選葉子，選非葉節點沒有意義。令在點集 \(S\) 中選 \(k\) 個點的最優方案是 \(F(S,k)\)：

由于 \(F(S,2)\) 就是直徑，我們希望 \(F(S,k)\) 也有類似的性質，例如可快速合并兩部分的 \(F\)。

下證 \(F(S,k-1)\subset F(S,k)\)，也就是一個比較符合直覺和經驗的貪心：每次我們選擇貢獻最大的葉子加入待選集合。

\(F(S,2)\) 就是直徑，先證必須選直徑端點。通過畫圖等手段可以比較清晰地發現，如果存在兩個點 \(x,y\) 滿足去掉 \(x,y\) 兩個點之后不影響其他點虛樹形態，由于 \(x,y\) 距離不大于直徑，替換為直徑是不劣的。

所以選直徑端點一定是不劣的。

然后發現這個問題變成了確定兩個點必須要選，再選 \(k-2\) 個點的最優方案。容易用調整法證明，每次都是選貢獻最大的葉子。

所以暴力做就把一個直徑端點作為根，做長鏈剖分之后選出前 \(k-1\) 大的鏈。

用數據結構優化看起來需要支持合并操作。

下證 \(F(S\cup T, k)\subseteq F(S,k)\cup F(T,k)\)。

首先 \(S\cup T\) 的直徑端點在 \(S\) 和 \(T\) 的直徑端點之間。接著 \(S\cup T\) 的前 \(k-1\) 大鏈一定在 \(S\) 與 \(T\) 的 \(2k-2\) 并之中，不然的話可以通過選擇不在 \(F(S,k)\) 和 \(F(T,k)\) 中的那個點來增加 \(S\) 或者 \(T\) 的答案。

所以現在我們支持了 \(O(k)\) 或者 \(O(k\log k)\) 甚至 \(O(k\log n)\) 合并兩個集合的答案。這個東西顯然是滿足交換律結合律可重復貢獻之類的東西，所以拿個數據結構維護一下就可以了。

將序列按 \(k\) 分塊，塊內暴力，塊間利用 ST 表快速維護合并，如果關于虛樹的部分做線性，大概可以做到 \(O(n\log n+qk)\)。直接上線段樹也是可以的，但是多一個 \(\log\)。

9.26

今天本來準備的論語課前演講是“歲寒，然后知松柏之后凋也”，結果 zy 說這個初中講過，我反駁，zy 說大家太熟了，我下來問了 10+ 人都說不知道（（（于是只能下周重來了

9.29

恐怖下午模擬賽。打了（并非）大眾分，T2 基環樹由于想正解去了沒時間（其實可以延時但是懶）。

9.30

國慶作業太多了。放假時長為其他班 \(\frac{3}{8}\)，但英語作業為 \(\frac{3}{4}\)。

知道停課之后還要上語英天塌了。半期考試要跟高一高二考兩場天塌了。

逆天 tzy 昨天模擬賽前 U 盤下的輕小說被 zy 看到，然后下午用的時候被全班看到。

晚上看到 這個。現在 OI 界的文學都這么卷的嗎（看來我也要開始卷了