本文將同步發表于洛谷（暫無法訪問）、CSDN 與 Github 個人博客（暫未發布）
本蒟自2025.2.8開始半停課。
以下是題目格式：
-
[題目OJ 題號] [來源（選填）] 名稱
……
-
題號 - 名稱
題目：……
題解：……
-
題號 - 名稱 （[題目OJ 題號] [來源（選填）] 名稱）
……
任務計劃（站外題與專題）
數了一下，通過人數比較高的題，也就是我準備補的題，剛好差不多100道題。于是……
擺爛百題計劃開始！（糖丸了）
（2025.2.8）
-
Network
-
Network of Schools
-
DP優化——矩陣
-
數論——容斥、二項式反演
-
DP優化——斜率優化
-
數據結構——左偏樹
-
數據結構——吉司機線段樹
-
數據結構——李超線段樹
2025.1.4 新的一年
今日歌曲：New Year’s Day
去年停課的時候是有記日祭的，但是有一些是手寫的，一直都還沒有整理好。今天看到一個簡單的trick，想記下來。于是，就又開始寫日祭了。
-
[洛谷 P2831] [NOIP2016 提高組] 憤怒的小鳥
一道遠古狀壓題了。（一是指題目本身遠古，二是指這道題是好久之前就該做的題。）看到第一篇題解的trick，想起去年暑假集訓的時候也有這樣一個trick，但是忘了是哪道題。這個trick挺簡單的，但也挺好用：狀壓時，如果目標狀態是全0或全1，并且轉移順序不影響結果，那么可以直接從最低位的1或0轉移，因為最低位最終一定會被轉移，而順序又不影響結果，所以這樣做可以優化掉 O ( n ) O(n) O(n) 的復雜度。其他的按正常狀壓即可。
-
[Atcoder ARC100E] Or Plus Max
今天學了sosdp，挺神奇的一種dp。這個題算是板子題吧。只用維護子集的最大值與次大值即可。
今天下午給初二機房的辦了一場比賽，整體比較順利。（所以沒做什么題。）比賽鏈接：CWOI-N ER & NYR 1。
今天感覺要掉橙了，但是Rated的比賽還要等一周。想著把之前那篇被打回的題解改了交了，但是晚上寫給初二機房的的題解了，沒空。看明天改吧。
2025.1.10 新的開始
今日歌曲：Castles Crumbling
今天考完期末，回來一看，天塌了，掉橙了。明天打一場比賽。
現在終于確定15班后續的各種事項了。又是一個新的開始。
另外，我就莫名奇妙地進省選了（盡管是體驗名額）。還有一個有趣的事實：
我沒有提高組一等獎，然而我進了NOIP（體驗名額）；我沒有NOIP一等獎，但我進了省選（體驗名額）。
期待人生中的第一場SCOI（希望不要爆零）。
2025.1.12 言而無信
今日歌曲：Back To December （好吧其實是存貨）
我果然是一個言而無信的人。踩一腳前天的日祭，昨天還是沒打比賽。
今天%你賽，除了暴力的B和C，其它全掛了分。至于A，調試的時候把模數寫掉了。被暴扣70分嗚嗚嗚。
最終榮獲 30 + 10 + 30 + 0 = 70 30 + 10 + 30 + 0 = 70 30+10+30+0=70 的高分。
-
A - 括號序列
題目：給一個由左右括號構成的字符串 s s s，對于每一個位置 i i i，輸出有多少個子串，滿足這個子串是一個合法的括號序列，并且 i i i 這個位置在子串中。
題解：簡單維護前綴與后綴的括號數量即可。（忘寫該死的模數暴扣70pts。）
-
C - 矩陣刪除
題目：給一個 n × m n \times m n×m 的 01 矩陣，我們想在每一行刪除一個元素，得到一個 n × ( m ? 1 ) n \times (m - 1) n×(m?1) 的矩陣。其中刪除的元素的位置 ( i , a i ) ( 1 ≤ i ≤ n ) (i, a_i)(1 \le i \le n) (i,ai?)(1≤i≤n)，滿足 ∣ a i ? a i + 1 ∣ ≤ k ( 1 ≤ i < n ) \vert a_{i} - a_{i + 1} \vert \le k(1 \le i \lt n) ∣ai??ai+1?∣≤k(1≤i<n)。請問最后能得到多少種不同的矩陣。兩個矩陣如果刪除的元素位置不同，但最后得到的結果相同，我們認為是相同的。由于答案很大，輸出答案對 1 0 9 + 7 10^9+7 109+7 取模的值。
題解：比較板的DP，但是賽時思路沒那么清晰，也沒去推式子。分別維護對于每一個位置的方案數以及與旁邊位置重合的方案數，推出式子后發現全都是求和，于是用前綴和維護即可。
2025.1.13 樂極生悲
今日歌曲：Wonderland
今天期末考試考完了，整體還行，語文更是考到了驚人的 127.5 127.5 127.5，要知道我之前最高的一次也就 122 122 122 左右，而且還經常上不了 120 120 120，這次簡直是超常發揮。聽到成績的時候直接喜極而泣了。
下午體育課，剛好初一體鍛放歌，放得全是霉霉的歌，我還去點了幾首。開心。
然而下課要集合的時候，我小跑了一下，而這下就恰好被足球爆頭，眼鏡鏡架直接斷掉，箍牙的鐵絲直接斷掉，嘴皮直接被鐵釘磨得爛掉，鼻子被眼鏡壓了一個印子，還在流鼻血。
真是樂極生悲。
2025.1.17 傻子游戲
今日歌曲：Foolish One
今天開始上課六天。
昨天聽說 jmr 拿了清華一等約。祝賀他。
這周二（1.14）已經回到15班了。
昨天晚上玩梗發癲，還玩了離譜的傻子游戲。達成成就：在5.5h里睡夠8h。
上午%你賽，T1忘了判零掛了10pts，T3是之前做過的一道原題，于是賽時死磕，最后沒調出來。賽時的思路基本上是對的，但是沒想到容斥；又因為我欽定的一個條件有問題，導致正確性略有問題，最后沒調出來。
喜提 90 90 90 分。
-
A - 串
題目：在虱子王國，一句話由 n n n 個詞組成，其中恰好有 k k k 個詞是怪的，其它的詞都不是怪的。眾所周知，負負得正，我們定義一句話的一個區間是怪的，當且僅當其中含有奇數個怪詞。請構造一句符合條件的話，使得其中怪的區間數量最多。
題解：發現答案為奇數塊乘上偶數塊。構造即可。
-
B - 藝術家
題目：給定一個長度為 n 的顏色序列 c c c。再給出 m m m 個區間，第 i i i 個區間為 [ l i , r i ] [li, ri] [li,ri]，保證任何兩個區間都是不相交或包含的關系。在接下來的 q q q 個單位時間內，第 i i i 個時間會給定 x , y x, y x,y，表示將 c x c_x cx? 變為 y y y。請對于每一個區間求出，最早的其中所有顏色都互不相同的時間。
題解：
保證任何兩個區間都是不相交或包含的關系。
所以可以把區間建成一棵樹。當一個子區間合法，其父區間才有可能合法。在原數軸上維護 l s t i lst_i lsti? 表示 i i i 之前第一個顏色與 i i i 相同的點，則一個區間內部顏色互不相同等價于 max ? { l s t i , l ≤ i ≤ r } \max\{lst_i, l \le i \le r\} max{lsti?,l≤i≤r}。使用線段樹維護。對于 l s t lst lst 的更新，用 set 維護。即可。（難寫死了，還沒寫完。）
-
C - 黑白樹 （[Atcoder ARC108F] Paint Tree）
題解：畫一個直徑上吊著節點的圖，討論一個節點在什么時候可以帶來貢獻。容斥計算即可。
晚上打了入門賽，可以加咕值了。
晚自習最后10分鐘，記一些話。
我的信競，在進步么？看起來好像是的。要是拿現在的我和一年前的我對比，那已足以 k k k 倍殺。但……補過的題還是不會做，碼量大一點的又不愿意寫，一到晚自習就寫不動了，于是寫一會兒又開始劃水。我倒有一個優點，就是一般不會去刷水題（除了入門賽）。但是，難一些的題……綠題效率低，藍題想不全于是又看題解，紫題幾乎無法獨立完成。
最終做了的題似乎是白做。
……
終究還是人的問題。
2025.1.18 正難則反
今日歌曲：Wildest Dream
這兩天換了頭像。
今天上午VP CodeForces Round 997 (Div. 2)。
-
[CodeForces 2056A] Shape Perimeter
計算重疊部分即可。
-
[CodeForces 2056B] Find the Permutation
我們總是建從小節點到大節點的有向邊，對這個DAG進行拓撲排序。因為我們有時并不想讓一個小節點往大節點連邊，所以用堆維護入度為零的點即可。（可惡，賽時多測不清空卡了我一發。）
-
[CodeForces 2056C] Palindromic Subsequences
挺玄學的構造題。我們希望大概長這樣的結構：
$$
\underbrace{1,\ 1,\ 1,\ \dots,\ 1,}{a個1}\ 2,\ 3,\ 4,\ \dots, a + 3,\ \underbrace{1,\ 1,\ 1,\ \dots,\ 1}{a-1個1}
$$
這樣構造出的答案有 a ( a + 2 ) + 1 = a 2 a(a + 2) + 1 = a^2 a(a+2)+1=a2 個，可以通過。稍微分討一下即可。
賽后看了一下題解，發現自己好唐：
1 , 2 , 3 , … , n ? 2 , 1 , 2 1,\ 2,\ 3,\ \dots,\ n-2, \ 1,\ 2 1,?2,?3,?…,?n?2,?1,?2
-
[CodeForces 2056D] Unique Median
又是一道正難則反，計算壞的序列的個數。這道題的trick挺巧妙的，但沒接觸過，確實想不出來。發現長度為奇數的序列一定不是壞的，所以只考慮偶數長度序列。對于一個序列的中位數 x x x，將序列中 ≤ x \le x ≤x 的數化為 ? 1 -1 ?1，其它的化為 1 1 1。若最終區間和為 0 0 0，那么這個序列就是壞的。另外要注意去重。維護前綴和即可。
-
[CodeForces 2056E] Nested Segments
組合數學。這個包含或不交的關系恰好和昨天的B差不多。我們想要盡可能多的節點數量，那么需要構造成二叉樹。（這里具體不想證明。）對于某一個節點，設其兒子數量為 c n t u cnt_u cntu?，則計算 ∏ C c n t u ? 1 \prod C_{cnt_u - 1} ∏Ccntu??1?（卡特蘭數）即可。
下午先把E題改了，學習了一下吉司機線段樹。這東西挺好理解的，寫起來也很爽，但就是又臭又長又難調。
-
[洛谷 P10639] [BZOJ4695] 最佳女選手
這道題本來是第二道模板題的，但因為第一題相當于第二題的子問題，所以直接沖著這道題來了。寫板子即可。（啊啊啊終于還是討厭上吉司機線段樹了啊。）
今天整理了一些去年的日祭。還沒把手寫的整理上去。
2024.1.19 簡直糖丸
今日歌曲：All You Have To Do Was Stay
今天上午%你賽，T1爆零了，簡直糖丸。一共得了 60 60 60 分的高分。
下午給初二講題，講得……簡直糖丸。
煩球，今天最后幾乎啥都沒干。
啊不是為什么T1爆炸啊。
2024.1.20 簡直樂丸
今日歌曲：Daylight
昨晚又是在5.5h內睡滿8h的一晚。
今天上午VP CodeForces Round 998 (Div. 3)。才做四道，糖丸了。
-
[CodeForces 2060E] Graph Composition
賽時就很唐。并查集查聯通并算連通塊即可。
-
[CodeForces 2060F] Multiplicative Arrays
一道很好的DP+組合數學題。賽時推式子感覺推出來了，結果賽后再一看偽了。很容易發現， ∑ i = 1 l e n [ a i ≠ 1 ] ≤ 16 \sum_{i=1}^{len}[a_i \neq 1] \le 16 ∑i=1len?[ai?=1]≤16，所以DP計算非 1 1 1 元素的情況，再用組合數學即可。
-
[CodeForces 2060G] Bugged Sort
這個題就很 “tricky”。（bushi，自己隨便造的詞。）這篇題解感覺講得比官方題解還要清晰。可以觀察到，當 n ≥ 3 n \ge 3 n≥3，我們可以任意（正常）交換兩組的位置。因此，我們可以將兩組數進行翻轉。換而言之，進行翻轉的次數必須是偶數次。這里記翻轉次數為 c n t cnt cnt。我們把較小的數放在 a a a，較大的放在 b b b。若按 a a a 排序后 b b b 有序，那么該組數據有解，當且僅當滿足這三個條件之一：
- 2 ∣ c n t 2 \mid cnt 2∣cnt
- ? b i ? 1 < a i , 2 ∣ n , 2 ∣ i \exists b_{i - 1} \lt a_i,\ 2 \mid n,\ 2 \mid i ?bi?1?<ai?,?2∣n,?2∣i，此時可以選擇交換奇數組數翻轉以改變 c n t cnt cnt 的奇偶性，處于“無敵”狀態。
- 2 ? n 2 \nmid n 2?n，此時可以翻轉全部以改變 c n t cnt cnt 的奇偶性。
否則無解。判斷即可。
今天下午看了一個2025年度第一個樂子（原帖，內部帖），簡直樂丸。
又一個新梗誕生了：
@chen_zhe 管理制度錯了就要改，不能讓無辜的人以淚洗面，如果管理制度還是這樣的話，洛谷將會越來越腐敗！！，我大不了就棕名，我要讓洛谷知道瞎誣陷的嚴重性！
2025.1.21 反則難證
今日歌曲：deja vu（第一首非霉歌曲）
今天上午VP CodeForces Round 999 (Div. 1 + Div. 2)，狀態還好。
-
[CodeForces 2061C] Kevin and Puzzle
有點思維的DP，題目挺好的。
-
[CodeForces 2061D] Kevin and Numbers
又是一道正難則反。我們很難將 a a a 合并，那就把 b b b 中不合法的進行拆分。用 map 維護即可。其實這道題也好證
，只是想湊一個小標題罷了。 -
[CodeForces 2061E] Kevin and And
這題有點……難評。為什么字典樹過不了啊……
因為 m m m 很小，所以對 b b b 進行狀壓，再將 a a a 的變化量壓進堆里選最大的 k k k 個即可。（好吧其實不是特別理解。）
F 聽不懂。
附一張梗圖。
（這里聲明一下，不是 jmr 講得不好，而是實在聽不懂。）
2025.1.22 比特塞特
今日歌曲：Maroon
年前最后一天了。
上午%你賽 100 + 10 + 60 + 0 = 170 , r a n k 4 100+10+60+0=170,\ rank\ 4 100+10+60+0=170,?rank?4。T3沒用 bitset 優化暴扣了 40 40 40 分。可惡。
-
A - bins （[洛谷 P6807] [BalticOI 2010 Day2] Matching Bins）
差分即可。
-
C - candies（[洛谷 P6808] [BalticOI 2010 Day2] Candies）
題解。
2025.2.8 水討論區
今日歌曲：Bigger Than The Whole Sky
今天洛谷討論區關閉了。（以后不能水討論區了。）
這個寒假，什么也沒干。一看進度，已經和初二的差不多。但是他們第一遍拉得挺快，估計效果不大。
我如果現在回去，在那邊又吃不飽。于是，就只有多肝一肝，把之前的進度補上來。
晚上打ABC392。
-
[Atcoder ABC392E] Cables and Servers
略考細節的題。先找連通塊，之后再找每個連通塊中的返祖邊（即無用的邊），再把連通塊連通即可。
（可是這題我賽時AC，后來突然想到一個hack。還沒改，煩死了。）
-
[Atcoder ABC392F] Insert
先寫一個 O ( n 2 ) O(n ^ 2) O(n2) 的做法，發現可以分塊。所以分塊即可。（賽時想到分塊但沒寫，煩死了。）
2025.2.9 終于戰勝
今日歌曲：Holyground
綜合題1。
-
[Gym 103466I] Space Station
神奇搜索題，暴搜+剪枝+略微組合數學即可。
神奇卡常題目，拼盡全力，2700ms+，終于沖進3s。
-
[Gym 101982D] Count The Bits
很普通的一道DP題，可是賽時都在想組合數學。
d p i , j dp_{i, j} dpi,j? 表示到第 i i i 位模 k k k 的值為 j j j 的數中 1 1 1 的數量， c n t i , j cnt_{i, j} cnti,j? 表示到第 i i i 位模 k k k 的值為 j j j 的數的數量，直接轉移即可。
-
[Gym 102428F] Fabricating Sculptures
神奇DP題。最開始看題解都沒看懂，一是自己確實不理解是怎么算的，二是題解寫得比較簡略，看了好久才看懂。
設 d p i , j dp_{i, j} dpi,j? 表示從上往下一層層放，當前一共放了 i i i 個，最下面一層放了 j j j 個的方案數。有方程 d p i , j = ∑ k = 1 j d p i ? j , k ? ( j + 1 ? k ) dp_{i, j} = \sum_{k = 1}^j dp_{i - j, k} * (j + 1 - k) dpi,j?=∑k=1j?dpi?j,k??(j+1?k)（希望沒寫錯）。將這個式子拆開再維護前綴和即可。（開了long long見祖宗。）
-
[Gym 104172F] Sum of Numbers
很有趣的一道題。很容易發現，兩個相鄰字符串長度之差（的絕對值）為 0 0 0 或 1 1 1。暴搜即可。
賽時的想法是，將原字符串平均分，再給 0 0 0 或 1 1 1 的偏移。可是偏移少了一些，雖然沒 TLE 但一直 WA，拼盡全力無法戰勝。
賽后再改一改，拼盡全力終于戰勝。
今天本來說再補補昨天的 F，改改昨天的 E，結果今天的第三題看半天看不懂，昨天的 E 和 F 都沒做。
最終今天做了四道題。
感覺心態有點崩。（尤其是看第三題的時候。）
……
2025.2.10 放棄即可
今日歌曲：Peace
綜合題2。
今天還做出了一道題。
-
[Gym 100861E] Extreme Programming
看了題解真的好簡單。首先我們先確定這些問題的順序。推推式子，排序即可。現在，我們不用考慮順序，只用直接背包，找出最大的 E V EV EV 與最小的 E T ET ET 即可。
可是這道題不知道哪里寫掛了，WA on test 15。
放棄即可。 -
[Gym 100217I] Sharing the Sweets
分拆數板子題。（可是我不會。）寫板子即可。
分拆數 OI Wiki。
-
[Gym 100202A] Little Brackets
這題著實簡單。設 d p i , j , 0 / 1 dp_{i, j, 0/1} dpi,j,0/1? 表示放了 i i i 個括號，當前高度為 j j j，是否到過最高點（深度為 k k k）的方案數。直接轉移即可。
可是賽時想多了，一直在想組合數學。或許先設方程再推會好一些。
賽時還因為多測不清空掛了四發。
今天還舉辦了 CWOI-N RER 1 > 2，感覺對于他們還是太難了。
（今天字符數破 1 e 4 1e4 1e4 了。）
