開(kāi)學(xué)第二個(gè)月，已經(jīng)開(kāi)始麻木了。

2025.10.1

國(guó)慶節(jié)日常被作業(yè)包圍。

將世界最后的空白刻印在斑駁心海

而我等蜉蝣只得抒發(fā)不足日的無(wú)奈

無(wú)名歌者哼唱著積雨云為之落淚的歌在人海

發(fā)現(xiàn) ARC 原來(lái)有這么多優(yōu)質(zhì)計(jì)數(shù)。

ARC105F Lights Out on Connected Graph

前幾天 tzy 學(xué)了集合冪級(jí)數(shù)與子圖計(jì)數(shù)之后一直找我討論各種奇葩的東西能不能數(shù)，然后順手提到了二分圖。

求黑白染色的圖個(gè)數(shù)比較簡(jiǎn)單，拆下式子子集卷積就好。這樣對(duì)于連通塊個(gè)數(shù)為 \(c\) 的二分圖會(huì)算 \(2^c\) 次。發(fā)現(xiàn) \(\ln\) 之后除以二就對(duì)了。

10.2 ~ 10.3

咋能這么頹的。

晚上 CF 10min 過(guò)了 A 和 C，感覺(jué)很有希望。但是一旦感覺(jué)有希望就要墜機(jī)了。因?yàn)轭j太多了 DE 做得比較慢。同樣因?yàn)轭j太多了 FG 都沒(méi)做出來(lái)。幸好分比較低甚至漲了。

10.4

補(bǔ)之前的神秘模擬賽，發(fā)現(xiàn) T4 的隨機(jī)化可以過(guò)，但是被 corner case 卡掉了。賽時(shí)考慮過(guò)這個(gè) corner case，但是判錯(cuò)了。不如去年的自己。

開(kāi)了 4 個(gè) ds，很難評(píng)價(jià)。

10.5

誰(shuí)懂各個(gè)題單加起來(lái) 47 道題的救贖感！

貪心很難，ds 很難，雜題很難。

晚上 ARC 35min 過(guò) A，70min 過(guò) B，C 想歪了反應(yīng)過(guò)來(lái)的時(shí)候已經(jīng)來(lái)不及了，沒(méi)有調(diào)出來(lái)。明明是能力范圍內(nèi)的（）

10.6

中秋節(jié)。

晚上讓我們?cè)诮淌壹谐栽嘛灪涂觳停鳛橹星锊环偶俚难a(bǔ)償。

10.7

又雙叒叕被奇妙模擬賽創(chuàng)飛了。

開(kāi)場(chǎng)他們都說(shuō)不會(huì) T1，簡(jiǎn)單想了一下也不會(huì)，T2 大概會(huì)了但是感覺(jué)代碼很難寫，T3 有點(diǎn)神秘，T4 是數(shù)據(jù)結(jié)構(gòu)，跟著他們倒開(kāi)。

很快會(huì)了樹(shù)套樹(shù)做法，但是糾結(jié)外層值域樹(shù)上二分花了很長(zhǎng)時(shí)間。最后寫出來(lái)樹(shù)狀數(shù)組 3log 比線段樹(shù) 2log 快，這么牛的。糾結(jié)一下交了樹(shù)狀數(shù)組版本。

最后 20min 猜了個(gè) T1 結(jié)論過(guò)掉了，然后因?yàn)闆](méi)有 T2T3 墜機(jī)了。

10.8

永不停歇的奇妙模擬賽。

早上起床莫名頭暈反胃，灌了半瓶水還是撐著來(lái)打模擬賽了。開(kāi)場(chǎng) 1h 什么都沒(méi)干，頭倒是更暈了，后悔來(lái)學(xué)校。開(kāi)場(chǎng) 2h 摸了下 T4 \(O(n^3)\) 暴力掛了，打了下 T1，結(jié)果因?yàn)橐槐閷戇^(guò)，沒(méi)有按平時(shí)邊寫邊思考的習(xí)慣來(lái)寫，因?yàn)橐粋€(gè)細(xì)節(jié)掛了 25pts。T2 又是棋牌題，懶得寫代碼。最后調(diào)出了 T4 \(O(n^3)\) 但是里面有個(gè)斯特林?jǐn)?shù)不太會(huì)優(yōu)化到正解，寫 FFT 試圖騙分結(jié)果爆精度了而且 T 飛。賽后發(fā)現(xiàn)是組合意義滅天地，欸。

10.9

我咋不會(huì)背《阿房宮賦》了。

怎么就停課了呢，感覺(jué)什么都沒(méi)干啊。

lf 說(shuō)我做題數(shù)倒數(shù)，猜猜為什么。

10.10

孩子們是 ds，快跑！

晚上的題目討論，三個(gè)題只會(huì)半道，這輩子也是有了。

10.11

神秘藍(lán)藍(lán)綠黑模擬賽，T2 T3 對(duì)數(shù)據(jù)分治，T4 超長(zhǎng) ds，極限時(shí)間打出分塊 43pts 部分分。

10.12

數(shù)學(xué)周考最難的不是三角，是集合（）（）（）答題算范圍的題基本上有分討取交并集都取錯(cuò)了（）（）（）

選擇錯(cuò)了三，這咋玩。倒是最后一個(gè)大題證明比較獵奇，歸納直接秒了。

又沒(méi)考過(guò)語(yǔ)文，唉。

10.14

ARC208C Mod of XOR

可以規(guī)約為 \(n+X=n\oplus C\) 是否存在的問(wèn)題。那么考慮異或?qū)嶋H上是一部分加上一部分減去，也就是我們希望存在 \(A\oplus B=C\)，\(A\cap B = 0\)，\(A-B=X\)，就有 \(n=B\) 滿足條件。解得 \(B=\dfrac{C-X}{2}\)，檢驗(yàn)一下即可。

10.15

最想退役的一天。

T3 線段樹(shù)合并調(diào)了 3h，不評(píng)價(jià)。

T4 補(bǔ)題 tarjan 寫掛，不評(píng)價(jià)。

會(huì)做 \(n=10^5\) 和 \(n=15\) 的 DAG 可達(dá)性統(tǒng)計(jì)問(wèn)題不會(huì) \(n=300\)，不評(píng)價(jià)。

ARC205D Non-Ancestor Matching

這個(gè)弱智被綠題硬控。一直在想自底向上怎么做（）

如果存在一個(gè)大小超過(guò)一半的兒子，操作次數(shù)會(huì)被其限制，于是考慮計(jì)算其內(nèi)部的答案，一直遞歸就做完了。

10.16

今天人不舒服半在線高維前綴和都想了好久，所以專門挑了綠題來(lái)做然后更想退役了。

不說(shuō)了來(lái)復(fù)健了。

ARC206B Slime Swap

又被 *1000 的綠題薄紗了。

只用考慮同顏色之間的貢獻(xiàn)，類似冒泡排序的過(guò)程逆序?qū)?huì)產(chǎn)生貢獻(xiàn)。此時(shí)相當(dāng)于對(duì)顏色相同的逆序?qū)B邊，求最大獨(dú)立集。

然后到這里就不會(huì)了，后來(lái)才發(fā)現(xiàn)沒(méi)有邊就是順序?qū)Γ?LIS 即可。

ARC206C Tree Sequence

終于遇到會(huì)做的題了/ll

題目給的條件很抽象，但是 \(n\) 居然有 2e5。緊接著考察長(zhǎng)度為 \(2\) 的區(qū)間 \([i,i+1]\)，必須有 \(B_i=i+1\) 或者 \(B_{i+1}=i\)，然后長(zhǎng)度 \(>2\) 的區(qū)間也順勢(shì)滿足了。對(duì)這個(gè)東西做 dp 就好。

ARC205B Triangle Toggle

再次證明我的題目難度關(guān)于真實(shí)題目難度是下凸函數(shù)，峰谷在上位綠到下位藍(lán)的位置。

先考察完全圖，翻轉(zhuǎn)三元環(huán)的操作使得每個(gè)點(diǎn)被翻轉(zhuǎn)的次數(shù)是偶數(shù)次，應(yīng)該對(duì)于 \(n\) 是奇數(shù)答案是 \(\dfrac{n(n-1)}{2}\)，偶數(shù)是 \(\dfrac{n(n-2)}{2}\)。

那么不是完全圖也有類似的思路，統(tǒng)計(jì)每個(gè)點(diǎn)的度數(shù)，看奇偶性即可。

ARC205C No Collision Moves

復(fù)健成功，終于不會(huì)被簡(jiǎn)單題卡了。

如果向左走和向右走的人有交，肯定無(wú)解。之后按左端點(diǎn)排序就好了。

ARC204A Use Udon Coupon

你這個(gè)人怎么剛復(fù)健就做計(jì)數(shù)。

如果沒(méi)有取 \(\max\) 的操作最后一定是 \(\sum B-\sum A\)。考慮取 \(\max\) 帶來(lái)的貢獻(xiàn)。

對(duì)于一個(gè) \(A\)，在放進(jìn)去的時(shí)候如果 \(C<A_i\) 會(huì)產(chǎn)生 \(A_i-C\) 的貢獻(xiàn)。如果之前一次取 \(\max\) 都沒(méi)有進(jìn)行過(guò)，\(C\) 是前面的 \(\sum B-\sum A\)；否則是從上一次取 \(\max\) 的位置開(kāi)始算的 \(\sum B-\sum A\)。把每一段的貢獻(xiàn)加起來(lái)就是 \(\sum A-\sum B\)，最后一段沒(méi)有觸發(fā)取 \(\max\) 不會(huì)給貢獻(xiàn)。

求答案套路容成 \(\leq x\) 的答案，則要求任意時(shí)刻 \(\sum A-\sum B\leq x\)，\(dp\) 即可。

感覺(jué)可以優(yōu)化但不是很會(huì)啊。

[SHOI2016] 黑暗前的幻想鄉(xiāng)

求包含所有顏色邊的生成樹(shù)個(gè)數(shù)。

考慮矩陣樹(shù)上直接 FMT 做或卷積，感覺(jué)很浪費(fèi)但是 \(O(2^nn^3)\) 隨便過(guò)。

然后發(fā)現(xiàn)題解區(qū)都是容斥，這下也是學(xué)傻了。

10.17

要語(yǔ)文周考，甚至寫三元作文，zy 說(shuō)我們直接上就可以了。

CF1481F AB Tree

觀察樣例和手玩大概可以得到一個(gè)讓同深度節(jié)點(diǎn)盡可能相同的貪心。

那么理想情況就是可以找出一些深度的點(diǎn)恰好有 \(x\) 或 \(n-x\) 個(gè)。

非理想情況下至少有一層同時(shí)存在兩個(gè)字母，欸不是很會(huì)了。好像對(duì)答案的貢獻(xiàn)只有 \(1\)。

所以是總量為 \(n\) 的背包板子。輸出方案有點(diǎn)惡心的。

注意到多重背包只需要記錄第一次變成 \(1\) 的方式就可以只用一維數(shù)組記錄方案。

ARC202A Merge and Increment

考慮一個(gè)貪心，從左往右掃，如果當(dāng)前數(shù)比下一個(gè)小，貪心地將其補(bǔ)全到下一個(gè)數(shù)然后合并。這樣做是不對(duì)的，因?yàn)槿绻?dāng)前數(shù)的左邊比右邊小，可以先和左邊合并。那么在當(dāng)前數(shù)比下一個(gè)大的時(shí)候存下來(lái)，再在后面判斷即可。

這么做之后會(huì)得到一個(gè)降序序列，這個(gè)直接貪就好了。

ARC201C Prefix Covering

考察一個(gè)字符串，其能保證所有包含其作為前綴的部分。考慮在 Trie 上 dp，\(dp_u\) 表示 \(u\) 子樹(shù)內(nèi)被保證的方案數(shù)，則該子樹(shù)被保證要么兩個(gè)子樹(shù)都被保證或者選上當(dāng)前點(diǎn)。

ABC411F Contraction

啟發(fā)式合并板子寫掛了，記以明志。

刷這個(gè)難度區(qū)間的題是不是算劃水啊（）

ARC200A Dot Product

觀察樣例可得如果 \(A,B\) 線性相關(guān)時(shí)無(wú)解。否則考慮用兩個(gè) \(X\) 來(lái)構(gòu)造。

\(A_1X_1+A_2X_2>0\)，\(B_1X_1+B_2X_2<0\)。

假設(shè) \(\dfrac{A_1}{B_1}>\dfrac{A_2}{B_2}\)，即 \(A_1B_2>A_2B_1\)，考慮構(gòu)造 \(A_1B_2-A_2B_1\) 和 \(A_2B_1-A_1B_2\)，那么 \(X_1=A_2+B_2,X_2=-A_1-B_1\) 即可。

10.18

語(yǔ)文選擇錯(cuò)四，不想活了。病句題最后兩分鐘改錯(cuò)了，語(yǔ)用作為優(yōu)勢(shì)區(qū)間這把也是炸了。

這把模擬賽怎么反向掛分的。開(kāi)場(chǎng)讀題之后期望 \(100+100+50+50=300\)。結(jié)果寫到 8:50 發(fā)現(xiàn) T2 讀錯(cuò)題了，改到 9:20 發(fā)現(xiàn)還是讀錯(cuò)了。有點(diǎn)害怕，先寫了 T3T4 共 80pts 暴力。理清 T2 題意之后 10:20 過(guò)了，但是以為卡常卡到快 11:00。接下來(lái)去做 T4 20pts 特殊性質(zhì)，結(jié)果不會(huì)。11:50 的時(shí)候發(fā)現(xiàn)這個(gè) T1 其實(shí)拿 SA 維護(hù)字典序就可以了，想不到更簡(jiǎn)單的做法，直接干。SA 板子掛了咋說(shuō)。

賽后發(fā)現(xiàn) T1 其實(shí)主函數(shù)比較后綴字典序的時(shí)候?qū)憭炝耍遣恢罏槭裁催^(guò)了。

T2 不知道為什么樹(shù)剖 ST 表只跑了 0.4s-。fxl 的倍增開(kāi) 2s 都 T 了。

T3 暴力多了 10pts。

T4 特殊性質(zhì)考場(chǎng)上用一個(gè) \(n=5\) hack 掉但是測(cè)出來(lái)過(guò)了。

然后變成了 \(100+100+60+50=310\)，但是總榜上 T1 出題人想卡掉我所以開(kāi)成 500ms 掛了 20pts。

模擬賽 T4

冒泡排序題我咋不會(huì)的。肯定是因?yàn)椴皇钦娴拿芭菖判颉?/p>

注意到答案是每個(gè)點(diǎn)排好序的時(shí)間最大值（注意到我只在做特殊性質(zhì)的時(shí)候注意到了這一點(diǎn)）。那么和特殊性質(zhì)一樣，一個(gè)數(shù)不考慮其他數(shù)的影響的話答案就是前面比它大的數(shù)個(gè)數(shù)再考慮奇偶性。如果被其他比它小的數(shù)擋住，就會(huì)跟著它一起動(dòng)。然后拿數(shù)據(jù)結(jié)構(gòu)維護(hù)就做完了。

10.19

[ZJOI2016] 小星星

果然是學(xué)的越多越不會(huì)做題。

有一個(gè) naive 的 dp，\(dp_{u,i,S}\) 表示考慮 \(u\) 子樹(shù)內(nèi)對(duì)應(yīng)原圖的點(diǎn)集 \(S\)，\(u\) 對(duì)應(yīng)點(diǎn) \(i\) 的方案數(shù)，但是這是 \(O(n^33^n)\) 的。直接套用子集卷積板子是十分詭異的 \(O(n^52^n)\)，但是但凡帶個(gè)腦子提前把 FMT 做好就是 \(O(n^42^n)\)。然而這樣仍然過(guò)不了，關(guān)鍵在于子集卷積的占位會(huì)帶上 \(O(n)\)。但是稍微動(dòng)動(dòng)腦子就能發(fā)現(xiàn)，為啥要做子集卷積，最后要求的是全集的答案那么直接或卷積就是對(duì)的。然后我們就十分詭異地過(guò)掉了這個(gè)題。

然而存在更簡(jiǎn)單的容斥做法，只需要?dú)J定所對(duì)應(yīng)的點(diǎn)集放掉 \(S\) 一維的限制即可 \(O(3^n)\rightarrow O(2^n)\)。

10.20

JOISC2019J ケーキの貼り合わせ (Cake 3)

如果確定了選的數(shù)，貪心一定是按 \(C\) 從小到大排。于是問(wèn)題變成選兩個(gè)端點(diǎn)加上中間 \(m-2\) 大的權(quán)值最大值，第一反應(yīng)是感覺(jué)是凸的可以 wqs，但是 WA 了。接著考慮對(duì)于每個(gè)右端點(diǎn)，左端點(diǎn)是單調(diào)的，因?yàn)閰^(qū)間前 \(k\) 大是很經(jīng)典的四邊形不等式式子。然后決策單調(diào)性分治，不知道為什么被一堆細(xì)節(jié)卡了很久。

10.21

由于多校模擬賽是數(shù)論場(chǎng)，lf 給我們找了一套 CSP-S 模擬賽，但是沒(méi)有最大的大樣例。

開(kāi)場(chǎng)發(fā)現(xiàn) T1 是簽，T2 T3 感覺(jué)不會(huì)，T4 想了一下好像會(huì)了，將每個(gè)點(diǎn)分討為三種顏色，然后將基環(huán)樹(shù)分為樹(shù)和環(huán)的部分，樹(shù)的部分樹(shù)剖+線段樹(shù)上二分，環(huán)的部分 set 直接做。

先寫了 T1，對(duì)著 T2 T3 坐牢。突然意識(shí)到 T2 不拆位是不可做的，草稿紙上畫了幾下發(fā)現(xiàn)會(huì)了，寫完發(fā)現(xiàn)已經(jīng) 9:40 了。T3 很急，感覺(jué)從 \(O(n^2)\) dp 優(yōu)化更有前途，但是 \(dp_i\) 涉及到 \(dp_{i-1},dp_{i-2}\)，有點(diǎn)懵。突然意識(shí)到可以矩陣，寫完調(diào)了很久才過(guò)樣例，然后發(fā)現(xiàn)過(guò)不了大樣例，快嚇?biāo)懒恕懥藗€(gè)暴力輸出中間過(guò)程，發(fā)現(xiàn)是統(tǒng)計(jì)答案部分的問(wèn)題，改完過(guò)了大樣例。此時(shí) 11:14，緊急 rush T4，大概 11:50 寫完了過(guò)不了第二個(gè)小樣例，急。調(diào)了一下發(fā)現(xiàn)是 dfn[top[x]], dfn[x] 寫成了 dfn[top[x]], x，急。改完過(guò)了大樣例，贏了。

賽后發(fā)現(xiàn) T1 掛至 40pts，rp++。T4 被卡常至 95pts，加了個(gè)剪枝跑至最優(yōu)解。

原本計(jì)劃打的多校模擬賽 T4

起手式離散對(duì)數(shù)變成加法，那么答案是 \(\dfrac{998244352}{\gcd\limits_{v\in S}\{\ln v\}}\)。

于是變成了子樹(shù)加鏈上求 \(\gcd\)，經(jīng)典差分+樹(shù)剖變成單點(diǎn)修區(qū)間查，發(fā)現(xiàn)是三個(gè) \(\log\)，但是 \(\gcd\) 那個(gè)由于 \(998244352=7\times 17\times 2^{23}\) 可以砍掉。由于出題人比較瑚璉之器所以把樸素 BSGS 求 \(\ln\) 卡了，想讓大家去寫 std 的求階的 lcm 的做法，但是直接竊取核心科技并二分塊長(zhǎng)即可擦邊通過(guò)。

[集訓(xùn)隊(duì)互測(cè) 2024] 長(zhǎng)野原龍勢(shì)流星群

效率好低。學(xué)習(xí)。

二分答案 \(x\) 后有一個(gè) dp，\(dp_u=\sum_v \max(0, dp_v) + a_u - x\)。考慮 \(dp_v\) 第一次隨 \(x\) 減小變成 \(0\) 的時(shí)候，用堆維護(hù)這個(gè)東西，并查集維護(hù)對(duì)其有貢獻(xiàn)的兒子即可。

類似有 [Ynoi2006] spxmcq，但是太累了不想寫了。

10.22

語(yǔ)文選擇錯(cuò)四個(gè)但是 117 rk5，班上最高分 120，怒了。現(xiàn)代文閱讀不知道在干什么，怒了。語(yǔ)用炸掉了，怒了。

課間音樂(lè)預(yù)選單里面有《我的悲傷是水做的》，洛水天依也是打進(jìn)課間音樂(lè)了。

ARC197D Ancestor Relation

當(dāng)時(shí)場(chǎng)上不知道在干什么。

考察兩個(gè) \(A_{i,j}=1\) 的 \(i,j\)，兩者之間肯定是包含關(guān)系。如果 \(A_i\) 是 \(A_j\) 的真子集，\(j\) 是 \(i\) 的祖先，反之亦然。那么不確定的部分是 \(A_i=A_j\) 的情況，這種情況所有 \(A\) 相同的在樹(shù)上會(huì)以一條鏈的形態(tài)排列，如果有 \(c\) 個(gè)，方案數(shù)為 \(c!\)，但是不能算進(jìn) \(1\) 號(hào)點(diǎn)。

然后就做完了，要判一下無(wú)解。

CF2144E Looking at Towers

注意到最大值必須要選，然后可以分為前后兩個(gè)部分，就是選的第一個(gè)最大值前面和最后一個(gè)最大值后面。兩部分本質(zhì)是類似的，只考慮前面部分。

有一個(gè)樸素的 dp，\(dp_{i,j}\) 表示考慮前 \(i\) 個(gè)數(shù)，當(dāng)前匹配了前 \(j\) 個(gè)前綴最大值。令前綴最大值為 \(p\)，若當(dāng)前數(shù) \(a_i>p_j\)，當(dāng)且僅當(dāng) \(a_i=p_{j+1}\) 能選；否則沒(méi)有要求。

然后這個(gè)東西看起來(lái)就能線段樹(shù)優(yōu)化，就能過(guò) Hard version 了。

CF2143D Inversion Graph Coloring

注意到當(dāng)且僅當(dāng) LDS 長(zhǎng)度 \(> 2\) 的時(shí)候不合法。

一個(gè)暴力做法是暴力記錄最大值和 LDS 結(jié)尾的最大值。令 \(dp_{i,j,k}\) 為考慮前 \(i\) 個(gè)數(shù)，最大值為 \(j\)，LDS 結(jié)尾最大值為 \(k\) 的方案數(shù)。轉(zhuǎn)移可以樹(shù)狀數(shù)組維護(hù)做到 \(O(n^2\log n)\)。

CF2127E Ancient Tree

賽時(shí)寫的做法是對(duì)的但是 T 掉了，但是當(dāng)時(shí)并沒(méi)有發(fā)現(xiàn)其實(shí)就是在合并子樹(shù)。賽后第二天居然也沒(méi)有發(fā)現(xiàn)判一下 siz 啟發(fā)式合并就對(duì)了。這很詭異。

今天隨到這個(gè)題突然發(fā)現(xiàn)了這一點(diǎn)然后就過(guò)了。考慮自底向上貪心，如果 \(u\) 沒(méi)有顏色且 \(u\) 的不同子樹(shù)中有相同顏色，累加答案并將 \(c_u\) 設(shè)為這個(gè)顏色。否則隨便給 \(u\) 賦一個(gè)子樹(shù)內(nèi)本身就有的顏色，這樣不會(huì)產(chǎn)生影響。需要特判子樹(shù)內(nèi)沒(méi)有一個(gè)點(diǎn)有顏色的情況。

CF1736D Equal Binary Subsequences

考慮不操作如何判定。貪心，如果開(kāi)頭有兩個(gè)相同的，分配到兩邊一定不劣。否則必須有一邊分走形如 1000... 或者 0111... 的極長(zhǎng)段，直到這個(gè)段與前一個(gè)段長(zhǎng)度相同。如果這個(gè)段比前一個(gè)段短，就無(wú)解。同時(shí)這個(gè)過(guò)程就是構(gòu)造的過(guò)程。

接下來(lái)考慮操作的意義。如果選的數(shù)里面相鄰兩個(gè)有相同的顯然沒(méi)有意義，所以操作的本質(zhì)是選擇偶數(shù)個(gè) 01 交替的位置 flip。

所以考慮模擬上面的過(guò)程，如果遇到不匹配的就做翻轉(zhuǎn)操作。大概間接證明了除了個(gè)數(shù)是奇數(shù)一定有解。

緊接著發(fā)現(xiàn)沒(méi)有對(duì)上腦電波。考慮 \(p\) 永遠(yuǎn)取奇數(shù)位，對(duì)于任意情況都可以構(gòu)造合法的解。

10.23

CF1144G Two Merged Sequences

晚自習(xí)離線測(cè)的題，思路太詭異了調(diào)了半天，掛個(gè) 題解。

10.24

由于考的是周三多校的模擬賽，大部分人提前拿到了題解。然后沒(méi)有什么好說(shuō)的，T4 這種序列操作計(jì)數(shù)太難了。

下午做了下歲月，發(fā)現(xiàn)我出的那個(gè)黑計(jì)數(shù)是 C 性質(zhì) plus 版，感覺(jué)有點(diǎn)危險(xiǎn)。

晚上要考英語(yǔ)但是很困很困，所以緊急背書（？），結(jié)果發(fā)現(xiàn)單詞和語(yǔ)法考的都很基礎(chǔ)，淦。作文是記敘文辯論稿縫合怪根本寫不來(lái)。閱讀從 A 篇開(kāi)始拿不準(zhǔn)，已經(jīng)下 140 了，應(yīng)該有 135。

10.25

上午 CQ 友誼賽，但是很困。

開(kāi)場(chǎng)感覺(jué)四個(gè)題都很小清新，發(fā)現(xiàn) T4 有點(diǎn)像前幾天 yzq 給我看的 [PA 2014] Druzyny，想了一下感覺(jué)會(huì)了，又感覺(jué)假了。之后在 T1/2/3/4 之間反復(fù)橫跳無(wú)果。T1 寫了個(gè)奇丑無(wú)比的鏈表，居然只跑了 0.3s，誰(shuí) CSP-S 模擬賽 9:50 過(guò) T1 啊。T2 枚舉若干貪心/dp 做法無(wú)果，拼了個(gè)區(qū)間 dp 上去試圖騙分。T3 進(jìn)行了若干轉(zhuǎn)化，然后先擱著去寫 T4 了。T4 寫完 60pts 之后又想了一下，發(fā)現(xiàn)其實(shí)可以沿用 CDQ 分治的思路，細(xì)節(jié)好多，到 11:25 發(fā)現(xiàn)過(guò)不了大樣例。調(diào)到 11:43 發(fā)現(xiàn)樹(shù)狀數(shù)組沒(méi)清空，嚇?biāo)懒恕０l(fā)現(xiàn)還是過(guò)不了大樣例，心跳 speed gathering。接著發(fā)現(xiàn)有個(gè)小細(xì)節(jié)節(jié)外生枝了，改完就過(guò)大樣例了，此時(shí) 11:52，不知天地為何物了。緊急 rush T3 暴力發(fā)現(xiàn)轉(zhuǎn)化假了，擺爛。

出來(lái)發(fā)現(xiàn)他們好像沒(méi)有幾個(gè)過(guò) T2 的，都是什么貪心/dp+shuffle 亂搞，還有不明正確性但很有道理的貪心。T3 好像過(guò)的不少，72pts 的暴力也不少。T4 60pts 居然比預(yù)想中少，詭異。yzq 和 tzy 都沒(méi)調(diào)出來(lái) T4，好像只有我過(guò)了。雖然但是，我只有 200+eps，顯然打不過(guò)任何拼了暴力的。

還是好困，已經(jīng)要累死了。英語(yǔ)所有二選一炸完了，rp += inf。

今日 T4

題目大意：將整個(gè)序列劃分為若干區(qū)間，使得所有 \(1\leq i\leq n\) 滿足 \(i\) 所在區(qū)間長(zhǎng)度 \(\geq a_i\)，求合法劃分方案數(shù)。有多組詢問(wèn)，每次詢問(wèn)指定一個(gè) \(a_x\leftarrow 1\)，詢問(wèn)之間獨(dú)立。

首先有暴力 dp 式子，可以 CDQ 或者最值分治優(yōu)化，可以直接拿到 60pts。考慮這個(gè)解除一個(gè) \(x\) 的限制是何意味。容易想到維護(hù)前后綴答案后考慮包含 \(x\) 的合法區(qū)間 \([l,r]\)，對(duì) \(pre_{l-1}\times suf_{r+1}\) 求和，但是這個(gè)東西不太好做。那么考慮答案的增量，對(duì)于一個(gè)區(qū)間 \([l,r]\) 如果 \(x\) 不是嚴(yán)格最大值，\(a_x\leftarrow 1\) 之后沒(méi)有影響；否則該區(qū)間的限制由 \(a_x\) 轉(zhuǎn)變?yōu)榇未笾怠?/p>

也就是說(shuō)，現(xiàn)在需要查詢所有包含 \(x\) 的區(qū)間 \([l,r]\) 滿足 \(r-l+1< a_x\) 且 \(r-l+1\ge\) 區(qū)間次大值。由于一個(gè)區(qū)間只會(huì)貢獻(xiàn)到一個(gè)嚴(yán)格最大值（什么廢話），這個(gè)東西也可以直接上 CDQ 分治，把前面的代碼改一下細(xì)節(jié)就可以了。感覺(jué)最值分治也是可以做的，但是 tzy 場(chǎng)上寫這個(gè)沒(méi)調(diào)出來(lái)，感覺(jué)是數(shù)據(jù)結(jié)構(gòu)做太多導(dǎo)致的。

10.26

突然發(fā)現(xiàn)昨天 T2 考場(chǎng)上的 \(O(n^4)\) dp 費(fèi)用提前計(jì)算就對(duì)了，難過(guò)。

英語(yǔ)炸到 129.5 了，還有個(gè) had been elected 可能是因?yàn)楦牡缴厦娼o我改錯(cuò)了，不然就上 130 了，難過(guò)。

晚上 AGC 做了倆小時(shí) A，沒(méi)救了，難過(guò)。

AGC074A Communicate Topological Order

首先猜測(cè)答案是 \(n -\)DAG 最長(zhǎng)鏈，但是只能過(guò) 11 個(gè)點(diǎn)，這東西顯然沒(méi)有用到 \(p\) 的性質(zhì)。

觀察到其實(shí)是圖上若干最長(zhǎng)鏈可以被推理，那么在 \(p\) 上做 dp 即可。

10.27

晚上跟 yzq&tzy 打 duel，人不是偶數(shù)怎么辦，他倆直接二打一，這我怎么打。

開(kāi)場(chǎng)發(fā)現(xiàn) E 有 bitmasks 標(biāo)簽，想了一下發(fā)現(xiàn)會(huì)了但是和 bitmask 好像沒(méi)有任何關(guān)聯(lián)，不過(guò)還是很快過(guò)了。

與此同時(shí) tzy 在做 D，yzq 在做 F，所以我跑去把 A 的換根 dp 寫了。然后做 C，想了個(gè) \(O(n^3)\) 但是有個(gè) if 沒(méi)判對(duì)導(dǎo)致被 tzy \(O(n^4)\) 截胡了，于是投降了。這個(gè)時(shí)候 90min 了 yzq 還沒(méi)過(guò)題。

yzq 發(fā)現(xiàn) F 一個(gè)東西他拿點(diǎn)分治+李超是假的，題解是最短路。發(fā)現(xiàn) B 其實(shí)是我題意沒(méi)有理解好，其實(shí)是很簡(jiǎn)單的題。

ARC112E Cigar Box

枚舉從頭到尾沒(méi)有動(dòng)過(guò)的區(qū)間 \([l,r]\)，那么有 \((l-1)+(n-r)\) 次操作確定了，且這些數(shù)在這之前可以亂動(dòng)。所以考慮 \(dp_{i,j}\) 表示有 \(i\) 個(gè)數(shù)可以亂動(dòng)，動(dòng) \(j\) 次的方案數(shù)，統(tǒng)計(jì)答案是簡(jiǎn)單的。

CF1839D Ball Sorting

\(k=n\) 的時(shí)候答案是 \(n\) 減去 LIS，考慮 \(0\) 球的作用，實(shí)際上是讓包含其的連續(xù)一段區(qū)間移動(dòng)。所以設(shè) \(dp_{i,j}\) 表示考慮前 \(i\) 個(gè)數(shù)用了 \(j\) 個(gè) \(0\) 球的答案，轉(zhuǎn)移是簡(jiǎn)單的。

CF2070F Friends and Pizza

考察兩個(gè)朋友所代表的集合 \(S\)，\(T\)，那么要求 \(\forall i\in S\cap T\)，\(a_i\) 是偶數(shù)，對(duì)答案貢獻(xiàn)為 \(\sum a-\sum_{i\in|S\cup T|} a_i\)。考慮枚舉 \(S\cup T\)，讓 \(S\) 和 \(T\) 做集合并卷積。對(duì)于 \(S\cap T\) 的限制，仿照子集卷積的形式加占位 \(|S\cap O|+|T\cap O|=|(S\cup T)\cap O|\)，其中 \(O\) 是為奇數(shù)的集合。

CF1322D Reality Show

上面提到 duel 的 E。

先把序列倒過(guò)來(lái)變成從小到大。那么很簡(jiǎn)單有一個(gè) \(dp_{i,j,k}\) 表示考慮前 \(i\) 項(xiàng)當(dāng)前攻擊性為 \(j\) 的有 \(k\) 個(gè)。轉(zhuǎn)移可以選擇要第 \(i\) 項(xiàng)，\(dp_{i,j,k}\leftarrow dp_{i-1,j,k-1}+c_k-s_i\)；然后可以選擇結(jié)束當(dāng)前值域，\(dp_{i,j+1,\lfloor\frac{k}{2}\rfloor}\leftarrow dp_{i,j,k}+c_k\times\lfloor\frac{k}{2}\rfloor\)。看似是 \(O(n^3)\) 的但是卡一下上界就是 \(O(n^2)\)。

CF2124F Appending Permutations

上面提到 duel 的 C。

考慮一個(gè)合法序列，將其映射到唯一的劃分方案計(jì)數(shù)，優(yōu)先按 \(1\) 開(kāi)頭劃分。容易有狀態(tài) \(dp_{i,j,k}\) 表示考慮前 \(i\) 個(gè)數(shù)，第 \(i\) 個(gè)位置是 \(j\)，當(dāng)前循環(huán)移位應(yīng)該以 \(k\) 結(jié)尾的方案數(shù)，特別地 \(k=0\) 表示是 \(1\) 開(kāi)頭。轉(zhuǎn)移比較簡(jiǎn)單，但是腦子暈了調(diào)了很久條件。

10.28

上午的模擬賽沒(méi)有計(jì)數(shù)和 ds，擺爛。T1T2 比較簡(jiǎn)單，T3 只會(huì) 55pts \(O(n^3c)\)，但是對(duì)于和 \(O(n^2c^2)\) 一個(gè)分很不滿。T4 構(gòu)造搞了很久不會(huì)，最后只有 AB 性質(zhì)過(guò)了，A 性質(zhì)拿了 75%。T3 數(shù)組開(kāi)小了少了 5pts。

賽后 T3 亂搞無(wú)果。懶得補(bǔ)題，OJ 評(píng)測(cè)都被卡炸了。

CF374E Inna and Babies

首先將共線的點(diǎn)用并查集并到一個(gè)集合里面。

考慮二分答案轉(zhuǎn)判定。合法當(dāng)且僅當(dāng)存在 A 類點(diǎn) \(a,b\) 與 B 類點(diǎn) \(c,d\) 滿足 \(a\) 與 \(c,d\) 相交，\(b\) 與 \(c,d\) 相交。

考慮 bitset 維護(hù) A 類點(diǎn)對(duì) B 類點(diǎn)相交的信息，然后再枚舉 \(a,b\) 查詢其交集大小是否大于一。

時(shí)間復(fù)雜度是 \(O(\frac{n^3\log V}{\omega})\)，看起來(lái)很不能通過(guò)。但是由于當(dāng)共線的點(diǎn)較多時(shí)集合數(shù)量比較少，共線的點(diǎn)較少時(shí)查詢次數(shù)不會(huì)跑滿，所以在數(shù)據(jù)比較水的情況下可以通過(guò)。

CF482D Random Function and Tree

小清新計(jì)數(shù)。

容易有 \(dp_{u,0/1}\) 表示 \(u\) 子樹(shù)內(nèi)涂了偶/奇?zhèn)€點(diǎn)的方案數(shù)。轉(zhuǎn)移時(shí)把正反加起來(lái)，再減掉正反相同的部分。

考慮一個(gè)選子節(jié)點(diǎn)的方案正反相同，當(dāng)且僅當(dāng)所有選擇的子節(jié)點(diǎn)前后綴奇偶性一樣，簡(jiǎn)單推一下就是所有子節(jié)點(diǎn)奇偶性與總和奇偶性相同。

CF1610F Mashtali: a Space Oddysey

好奇妙的構(gòu)造題。

考慮一個(gè)點(diǎn) 1/2 邊的度數(shù)奇偶性，只有有奇數(shù)條 1 邊時(shí)能貢獻(xiàn)答案。

考慮用歐拉回路刻畫，如果 1/2 邊都是奇數(shù)，在中間連一條邊，否則讓其中為奇數(shù)的連向超級(jí)源點(diǎn)。跑歐拉回路定向即可。

CF1109D Sasha and Interesting Fact from Graph Theory

兩個(gè)關(guān)鍵點(diǎn)編號(hào)沒(méi)有什么用。考慮枚舉兩個(gè)關(guān)鍵點(diǎn)之間的邊數(shù) \(i\)，那么從 \(n-2\) 個(gè)點(diǎn)選出 \(i-1\) 個(gè)放在中間，再隔板法確定中間的邊權(quán)，剩下的邊隨便選邊權(quán)。還有連成一棵樹(shù)的方案數(shù)，直接套擴(kuò)展 Cayley 定理即可。

10.29

模擬賽開(kāi)場(chǎng)看題，T1 計(jì)數(shù)，后面三個(gè)都像 ds。T1 花了一會(huì)兒會(huì)了，賽后發(fā)現(xiàn)是高貴的出題人做法。

T3 是最小生成樹(shù)題，因?yàn)闅q月做多了所以只想到了 \(O(nmf)\) 做法，\(f\) 是葉子個(gè)數(shù)。賽后發(fā)現(xiàn)很容易去掉那個(gè) \(m\)，也很容易進(jìn)行優(yōu)化。

T4 是 ODT 題沒(méi)時(shí)間做了。

賽后不知道為什么沒(méi)有代碼，我到底動(dòng)了誰(shuí)的蛋糕/ll

晚上的英語(yǔ)配音比賽去不了/ll 我到底動(dòng)了誰(shuí)的蛋糕/ll

感覺(jué)狀態(tài)和心情不是很好開(kāi)了把雀，三人東東一局對(duì)對(duì)和綠一色聽(tīng)牌但是流局了，然后上課了被迫下線等到回來(lái)發(fā)現(xiàn)放了一個(gè)累計(jì)役滿，我到底動(dòng)了誰(shuí)的蛋糕/ll

10.30

早上班主任叫我們晚上回去 20min 參加集體生日會(huì)，這才發(fā)現(xiàn) 10 月已經(jīng)要過(guò)完了。

AGC049C Robots

對(duì)于 \(a_i>b_i\) 的直接按順序吃掉，考慮剩下的沒(méi)有被毀掉的機(jī)器人，都滿足 \(a_i\leq b_i\)。對(duì)每個(gè)機(jī)器人可以選擇變一個(gè) \(a_i+1\) 出來(lái)踩掉它，也可以強(qiáng)行讓 \(a_i>b_i\)。維護(hù)是簡(jiǎn)單的。

10.31

12 月前最后一次上語(yǔ)文英語(yǔ)課，不知道該用什么語(yǔ)氣詞!

上午開(kāi)了個(gè)信心賽，T1 T2 是智慧題，T3 是鬼街弱化版，T4 是啟發(fā)式合并+維護(hù)凸包板子，全都懶得打，所以打雀。注意到考前游戲打得越多越爛，考試考得越好，這點(diǎn)已被 WC2025 和 APIO2025 證明，目前沒(méi)有證偽。看吧，三人東連續(xù)十把三位，rp += inf。

下午隔壁班踢足球比賽前不知道為什么感覺(jué)要下雨了，然后說(shuō)了句天氣之子要發(fā)力了，結(jié)果半場(chǎng)休息的時(shí)候真下了。

10 月份要結(jié)束了，不知道該用什么形容詞！