省流

五年前的題打到銀首，感覺(jué)放到現(xiàn)在應(yīng)該也就銅。

10.31

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

不是題解！！！！！！！

賽前

簡(jiǎn)要和他的其他隊(duì)友 vp 一場(chǎng)去準(zhǔn)備武漢區(qū)域賽，于是我和葉神，帶著 wanglinqi 一起開(kāi)了一把比較古老的區(qū)域賽。

賽時(shí)

跟著榜先開(kāi)了 K 題，要求構(gòu)造一個(gè)長(zhǎng)度為 \(n\) 的排列使排列中下標(biāo)和數(shù)字的 gcd 為 \(1\) 的個(gè)數(shù)恰好為 \(k\)。我一開(kāi)始讀錯(cuò)了題目，葉神很快說(shuō)想到了，我問(wèn)了他題意之后認(rèn)為他的解法是正確的。一開(kāi)始排列按順序排，然后答案就是只有 \(1\) 這一個(gè)位置，臨項(xiàng)交換兩個(gè)位置會(huì)讓答案加 \(2\)，于是他上機(jī)去寫。
我和 wanglinqi 去開(kāi) L，L 是給了一些紅點(diǎn)和藍(lán)點(diǎn)，要求選擇一個(gè)點(diǎn)使到這個(gè)點(diǎn)距離小于最近的藍(lán)點(diǎn)的紅點(diǎn)的數(shù)量最多。我發(fā)現(xiàn)這個(gè)點(diǎn)只會(huì)取兩個(gè)藍(lán)點(diǎn)間的中點(diǎn)，而答案就是這兩個(gè)藍(lán)點(diǎn)之間的紅點(diǎn)數(shù)量。和 wanglinqi 說(shuō)后他發(fā)現(xiàn)這樣會(huì)漏掉兩端，所以要在開(kāi)頭和結(jié)尾特判一下。
葉神以不知道為什么的掛一發(fā)寫完 K，wanglinqi 上機(jī)，我和葉神一起去看 F。
F 是給定 \(n\) 和 \(m\)，制作一個(gè)煙花要 \(n\) 時(shí)間，點(diǎn)燃所有煙花要 \(m\) 時(shí)間，一個(gè)點(diǎn)燃的煙花成功率為 \(p\)，問(wèn)最好的方案有一個(gè)煙花成功點(diǎn)燃的期望是多少時(shí)間。我首先和葉神說(shuō)一定是制作固定數(shù)量的煙花數(shù)再點(diǎn)，然后猜測(cè)一個(gè)結(jié)論可以三分。葉神同意前一個(gè)，但覺(jué)得應(yīng)該可以直接根據(jù) \(p\) 和 \(m\) 計(jì)算出需要制作的煙花個(gè)數(shù)。我通過(guò)樣例計(jì)算認(rèn)為他是錯(cuò)誤的，但他覺(jué)得是我期望算錯(cuò)了，和他稍微吵了一會(huì)，非常對(duì)不起他，而且我也重新確認(rèn)了比賽概率相關(guān)的東西還是要我來(lái)。
也許是 wanglinqi 初次打區(qū)域賽有點(diǎn)不擅長(zhǎng)葉神的機(jī)子，碼的慢了一些，中間幫助他查了一下以及加了快讀，以一發(fā)罰時(shí)通過(guò)。
然后我上機(jī)寫 F，在此前看了 E 題認(rèn)為是簡(jiǎn)單模擬于是丟給 yrjzs。wanglinqi 則是去搞了 M。
我很快碼完 F，因?yàn)榫葐?wèn)題吃了兩罰，然后看 M。yrjzs 上機(jī)碼 E，掛了，wanglinqi 轉(zhuǎn)過(guò)去幫他查細(xì)節(jié)。
M 題給了一棵樹(shù)，要求樹(shù)從上往下刪掉每一個(gè)點(diǎn)，刪掉的點(diǎn)的消耗是他本身的值加所有兒子的值，問(wèn)可以免費(fèi)去掉從 \(0\) 到 \(n\) 個(gè)點(diǎn)后總消耗最少是多少，點(diǎn)的數(shù)量為 \(2000\)。我一開(kāi)始在和 wanglinqi 討論，容易想到應(yīng)該考慮加點(diǎn)而非刪點(diǎn)，考慮貪心。但是貪心很難維護(hù)前一步先取父親，后一步卻取兩個(gè)兒子的情況。我想到對(duì)于一個(gè)點(diǎn)來(lái)說(shuō)，兒子很多而父親永遠(yuǎn)只有一個(gè)，所以如果使用樹(shù)形 dp，可以通過(guò)存儲(chǔ)一個(gè)根節(jié)點(diǎn)下選擇了 \(j\) 個(gè)點(diǎn)，以及他自己有沒(méi)有被選擇的 \(dp\)。父親節(jié)點(diǎn)則需要對(duì)每個(gè)兒子更新一次。因?yàn)槊總€(gè)兒子都只會(huì)在父親處更新一次，以及自己計(jì)算時(shí)更新一次，所以復(fù)雜度仍然是 \(n^2\) 的。我整理好轉(zhuǎn)移方程后讓他們下機(jī)，我很快寫完一發(fā)通過(guò)。
接著很快他們通過(guò) E 題，雖然吃了四罰但已經(jīng)穩(wěn)銀了，不過(guò)受到鼓舞后，且還有 \(100min\)，決定再開(kāi)題，雖然一題已經(jīng)不會(huì)影響排名，但是考慮做出兩題。于是他們看金牌線的 H 題，我則是看了幾個(gè)獎(jiǎng)杯題看有沒(méi)有擅長(zhǎng)的。
看完之后感覺(jué)獎(jiǎng)杯題不太可做，于是讓他們給我講 H。wanglinqi 講是一個(gè)方陣中涂三種顏色，要求存在一個(gè)矩形，四個(gè)角中，有兩個(gè)相連的角同色，而另外兩個(gè)角也同色。問(wèn)方案有多少種。在他給我介紹題意時(shí)，一邊畫一邊想我提出了有一邊大于 \(6\) 就必定所有情況可以滿足，于是我們考慮小于等于 \(6\) 的情況。隨著時(shí)間流逝，非常慌，于是看了可能大小發(fā)現(xiàn)并不大，于是暴力求出了小于的所有情況，打表通過(guò)了，拿下銀首。

賽后

E 題是給了一個(gè)人在起點(diǎn)，給了一個(gè)向上下左右走的序列，要求任意交換這個(gè)序列中的位置，走的時(shí)候不能碰到一個(gè)給定位置的炸彈。我們做的時(shí)候是分類討論了炸彈的位置，很麻煩，而題解直接枚舉了四種方向走的順序的情況，只有 \(24\) 種，這樣的做法很輕易的解決這道題目。
距離 ICPC2025 沈陽(yáng)站還有 \(14\) 天。

2025年11月1日