省流

\(6t\) 銅首，然而距離銀似乎仍舊遙遠(yuǎn)。

10.28

內(nèi)含劇透，請(qǐng)vp后再來(lái)。

不是題解！！！！！！！

賽前

第一次和 chumeng 老師以及 qwsxza 老師組隊(duì)打，想著可以抱大腿拿個(gè)銀啥的，結(jié)果開始的比預(yù)想的晚，只全力打了不到三個(gè)小時(shí)。

賽時(shí)

我一開始從后往前開，英文題面很煩，看的不太舒服，沒(méi)看明白。很快 J 題有人開出，然后三人一起去看了，我和 qwsxza 還沒(méi)搞懂題面 chumeng 老師就先拔頭籌，把機(jī)子要過(guò)去開寫。碼力相當(dāng)強(qiáng)，在恍惚間就碼完了。
然后一起跟榜開 C，C 是有一個(gè)人，可以選擇使用 \(a\) 分鐘復(fù)制一個(gè)自己，或者用 \(b\) 分鐘出一道題，問(wèn)出 \(c\) 道題所需的最短時(shí)間。我想到一定是先復(fù)制自己后出題，于是給出三分的做法，然而這個(gè)東西并不是嚴(yán)格的遞增遞減，所以不太好搞。然后 qwsxza 和 chumeng 先后表示只用枚舉所有人共同復(fù)制的次數(shù)，我覺(jué)得應(yīng)該要考慮有一些人復(fù)制而另一些人出題的情況，不過(guò)他們都聲稱不需要，于是丟給他們，chumeng 老師要走了，很快寫完過(guò)了。他們兩人去開 G。
我放掉 C 不管后看了 F，模擬題，機(jī)子空下來(lái)后寫完一發(fā)過(guò)。
然和和他們會(huì)合看 G，G 題要求在給定的總長(zhǎng)度為 \(n \leq 1e5\) 的字符串集合中找到一個(gè)字符串，使他的所有子串都在集合中出現(xiàn)過(guò)。因?yàn)樽址淖哟當(dāng)?shù)量是平方級(jí)別，所以只有長(zhǎng)度小于根號(hào)級(jí)別的才有可能成功。顯然這個(gè)是一個(gè)凸函數(shù)，所以最壞情況就是 \(O(n\sqrt{n})\) 的查詢次數(shù)，利用滾動(dòng)哈希可以通過(guò)。不過(guò) qwsxza 提出了一個(gè)長(zhǎng)度為 \(n\) 的串當(dāng)且僅當(dāng)它的 \(1\) 到 \(n-1\) 子串和 \(2\) 到 \(n\) 的子串都可以成功時(shí)才成功，所以可以是一個(gè)排序后 \(O(n)\) 的 dp 解決，我覺(jué)得他的沒(méi)問(wèn)題就讓他上機(jī)寫了。也是一發(fā)通過(guò)。
接著我一個(gè)人去看 L，chumeng 老師和 qwsxza 一起去看了 E。L 題給了一顆有 \(n \leq 1e6\) 個(gè)點(diǎn)的樹，要求把這顆樹分成一些集合，要求每個(gè)集合要么是一條從上往下的鏈，要么所有節(jié)點(diǎn)互相不為祖先，問(wèn)最少要分多少個(gè)集合。可以把分集合的操作看作刪除點(diǎn)，而一個(gè)點(diǎn)也可以刪多次。只考慮第一個(gè)操作，就是要?jiǎng)h葉子節(jié)點(diǎn)數(shù)條鏈，然后考慮加入第二個(gè)操作。第二個(gè)操作可以想到刪掉所有葉子，然后發(fā)現(xiàn)如果刪掉的不是葉子，葉子數(shù)量不減少，那么第一個(gè)操作的鏈的數(shù)量就也不會(huì)減少，所以一定先刪葉子，那么只要第二種操作刪掉所有葉子就可以。然后遍歷第二種操作的次數(shù)，再看剩余的葉子數(shù)，就可以求出所有情況的操作次數(shù)了。我第一次實(shí)現(xiàn)時(shí)用的是從上到下的高度，掛了，然后改過(guò)來(lái)從下到上，還是掛。
過(guò)了一會(huì)他們把 E 在兩發(fā)罰時(shí)解決了，于是來(lái)看 L。我講了一下題目和思路，chumeng 沒(méi)太聽懂，qwsxza 覺(jué)得沒(méi)問(wèn)題。他看了一下我的代碼之后覺(jué)得我的代碼奇爛無(wú)比選擇重構(gòu)寫一個(gè)拓?fù)渑判颍Y(jié)果他讀入多讀了掛一發(fā)，然后他修改讀入又修改錯(cuò)了掛一發(fā)，然后我重新改了一下他的讀入終于過(guò)了。
然后我們看了一下 A 和 B，都沒(méi)什么思路，決定去磕 B 題。B 題是給了一個(gè) \(250 \times 250\) 的網(wǎng)格，其中有一些有障礙物。要求把其中空白的一些格子涂顏色，要求每行每列只能涂一種相同的顏色，或者補(bǔ)圖。最后的總花費(fèi)是涂的顏色種類 \(k\) 乘給定的值 \(c\) 加沒(méi)有涂色的格子數(shù) \(z\) 乘給定的值 \(d\)。我和 qwsxza 根據(jù)時(shí)間復(fù)雜度猜了一個(gè)三次方的 dp，接著互相提出了一些猜測(cè)，不過(guò)都假了，沒(méi)有交結(jié)束比賽。

賽后

\(6t\) 罰時(shí) \(442\)，距離銀線的 \(352\) 罰時(shí)還差九十分鐘，對(duì)于 qwsxza 來(lái)說(shuō)感覺(jué)是不太可以接受的結(jié)果。
本來(lái)想補(bǔ) B 的，但網(wǎng)絡(luò)流完全不會(huì)，下班！

2025年10月29日