GDOI2021 摸魚記

今年總算有驚無險地獲得了參加聯合省選的資格，雖然 N O I P NOIP NOIP 和 N O I    W C NOI\; WC NOIWC 的低分已經決定我進不了省隊了，但是出去 摸魚 鍛煉一下它不香嗎？

Day [ − n , − 12 ] [-n,-12] [−n,−12]

屢次比賽的失利使我對自己實力的懷疑變為否定，我開始反思當初決定學習 O I OI OI 是否是一個錯誤，開始思考現在繼續的合理性。

以前隻看到了山頂在不遠的地方，卻不知“望山跑死馬”的道理。現在已近日落，仍不知在哪個山溝裡。也許下山才是明智的選擇吧。國小規劃的路線又有幾分合理性？都說是隻為興趣在學，怎麼就沒聽說過堅持不下去中途放棄的前輩呢？難道隻有一條正道嗎？難道能為了一個所謂的興趣拖死自己嗎？

突然意識到自己想得太灰暗了，抑或是說轉折太大了。不管那麼多了，停兩周課認真準備省選再說。

Day [ − 13 , − 2 ] [-13,-2] [−13,−2]

開始為期兩個星期的停課訓練。

發現自己的狀态很差：考場上從來沒有成功地切過題，是以榜上總是處于中下遊的位置；賽後好多題都沒有改出來，感覺就是三道題都很難，切每道題都費力。

幾天後就碰都不碰文化課了。

最後做了兩次正規的模拟賽，第一次因為兩天都沒有切題，是以排名很差；第二次兩天的題目都很難，部分分成本效益又低得離譜，最後排名也很差。

狀态真的不好，今年省選估計沒了。成功被模拟賽打掉自信心。

Day − 2 -2 −2

放假回家收拾東西了。但是我的行李衣服都在學校呢，當然不會回去收拾的啦。

回去浪了一波，心态放松了不少。總之這次就是出去鍛煉的，也不求能拿到什麼好成績，盡力了就行。

Day − 1 -1 −1

想着早點開始收拾東西，于是下午 13 : 20 13:20 13:20 回到學校，這時才發現其他同學還在宿舍睡覺，現在進不去。等到 13 : 40 13:40 13:40 ，在打鈴前 5 5 5 分鐘和 G S M GSM GSM 溜了進去。

14:30

從校門口牌坊出發，開始聽歌。

17:30

到達深圳耀華中學。

剛下車還以為我們要住的酒店就在對面那兩棟綠色的高樓裡，賊慌（因為 X C XC XC 之前說過樓下有美食街之類的話，那裡樓下确實也有一些快餐店），好在是虛驚一場。

18:10

和 Z Z J ZZJ ZZJ 大佬分到一間雙床房，放好東西後商量了一下，決定下樓吃湘菜。吃完飯後又順着道路散步，瞥見了不遠處燈光閃爍的高樓大廈。

22:00

X C XC XC 叫我們去 308 308 308 開會，覺得有點不妙。果然，誇了一下這家酒店後就說要收手機，說是怕我們晚上光顧着玩手機不睡覺。那麼第二天怎麼起床？逐個敲門叫，順便發手機。

Day 1 1 1

06:30

L Z A LZA LZA 過來要手機，把我們叫醒了。由于安排十分混亂（比如丁老師不知道叫醒我們時要發手機，比如黃老師以為 5 5 5 樓的手機是紀雅），接近 7 : 00 7:00 7:00 才拿到手機。

08:00

進入考場，要等到 8 : 27 8:27 8:27 才能開始操作機器。有點無聊，就趴在桌子上休息。

08:27

公布了密碼，但是 W i n d o w s Windows Windows 版的壓縮包不能輸入密碼解壓。試了兩次後就想試一下 L i n u x Linux Linux 版的，成功解壓了。

08:30~13:00

開始讀題。

T 1 T1 T1 一眼上去顯然是枚舉最小值啊！那麼最大值呢？可以雙指針處理吧。

T 2 T2 T2 沒什麼想法，但是 n , m n,m n,m 那麼小可能可以做。

T 3 T3 T3 好複雜了，就去水暴力分吧！

然後開始做 T 1 T1 T1 。發現雙指針有億點難搞，因為枚舉最小值指針後，最大值指針可能要回退，情況很多。

很不巧的，這時開始犯困了，強然困意寫了一坨接近 2000    b y t e s 2000\; bytes 2000bytes 的代碼，寫完之後意識到最大值指針回退有很多情況沒考慮到。由于太困了，根本無法正常思考，申請排隊上廁所後又胡亂改了幾下，沒有改出來。

上廁所洗了把臉，頓時清醒了。回去一看，我 ∗ * ∗ ，之前寫的是什麼鬼？！

全部删了，再寫一遍。發現如果用二分做的話會簡單很多。

寫完之後調試了一下，過了大樣例。然後寫對拍，沒想到第一個資料就錯了！

經檢查，發現我某個地方寫錯了，通路數組時下标是一個

bool

變量，沒想到這都能過大樣例，這大樣例是精心用腳構造的吧。後面再拍就沒拍出錯誤了。

T 2 T2 T2 第一個子任務在草稿紙上畫一畫就出來了：假設現在四個數從小到大分别是 b 1 , b 2 , b 3 , b 4 b_1,b_2,b_3,b_4 b1​,b2​,b3​,b4​ ，不妨設它們原來分别在矩陣的左上角、右上角、右下角、左下角。那麼我可以這樣子填數：

0 0 b 2 − b 1 0 b 1 0 b 4 − b 1 0 b 3 − b 1 \begin{matrix} 0 & 0 & b_2-b_1\\ 0 & b_1 & 0\\ b_4-b_1 & 0 & b_3-b_1 \end{matrix} 00b4​−b1​​0b1​0​b2​−b1​0b3​−b1​​

接下來就是 m = 2 m=2 m=2 的子任務，不妨令右邊那一列全部是 0 0 0 ，那麼現在就是要求出一組滿足以下條件的解：

{ 0 ≤ a 1 ≤ 1 0 6 , 0 ≤ a 2 ≤ 1 0 6 ,     ⋯ 0 ≤ a n ≤ 1 0 6 , a 1 + a 2 = b 1 , a 2 + a 3 = b 2 ,     ⋯ a n − 1 + a n = b n − 1 \begin{cases} 0\le a_1\le 10^6,\\ 0\le a_2\le 10^6,\\ \quad\space\space\space\cdots\\ 0\le a_n\le 10^6,\\ a_1+a_2=b_1,\\ a_2+a_3=b_2,\\ \quad\space\space\space\cdots\\ a_{n-1}+a_n=b_{n-1} \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​0≤a1​≤106,0≤a2​≤106,   ⋯0≤an​≤106,a1​+a2​=b1​,a2​+a3​=b2​,   ⋯an−1​+an​=bn−1​​

後半部分的每一個等式都可以寫成兩個不等式：

a i + a i + 1 = b i ⇔ { a i + a i + 1 ≤ b i , a i + a i + 1 ≥ b i a_i + a_{i+1} = b_i \Leftrightarrow \begin{cases} a_i + a_{i+1} \le b_i,\\ a_i + a_{i+1} \ge b_i \end{cases} ai​+ai+1​=bi​⇔{ai​+ai+1​≤bi​,ai​+ai+1​≥bi​​

然後就可以愉快地 差分限制 了。

第二個子任務調了一會兒才過了手造的資料，這時已經 12 12 12 點多了，手玩了幾下沒錯就去打 T 3 T3 T3 。

T 3 T3 T3 看起來比較複雜，加之沒有時間想題了，就急急忙忙打暴力。可惜到最後都沒有調出來，遺憾爆 0 0 0 。

13:00~13:30

出了考場，和同學們讨論了一下發現 T 1 T1 T1 被切穿了，有人就是用 O ( n ) O(n) O(n) 的方法過的，對我 O ( n log ⁡ 2 n ) O(n\log_2 n) O(nlog2​n) 的二分十分不屑。

然後我就發現我的 T 2 T2 T2 極可能要 0 0 0 分了——因為我“不妨設”一些地方填 0 0 0 ，其他地方極可能會爆上限（比如所有輸入的數都是 4 × 1 0 6 4\times 10^6 4×106 時我就挂了）

那麼今天的得分應該就是 [ 100 , 150 ] [100,150] [100,150] 了吧。

13:30~14:40

午餐和一群人高消費了，吃完飯後買了杯奶茶，然後回耀華中學參加經驗交流會。

15:00~17:00

經驗交流會和原想的 很不一樣 。本以為是題目講解之類的，想不到就真的是經驗交流分享。

先是香港中文大學深圳分校、南方科技大學等大學的介紹，然後是兩個學長分享一些有關算法競賽的東西。大概就是關于我們以後的發展方向的吧。沒想到接下來竟然是 D Z D DZD DZD 教授的發言——他竟然來 G D O I GDOI GDOI 現場了！

17:30~21:30

和 Z J J , G S M , L Z A , H M H , L J ZJJ,GSM,LZA,HMH,LJ ZJJ,GSM,LZA,HMH,LJ 去玩密室逃脫了。

深圳遠比我想象中的繁華，四處是高樓，人很多，讓我這個鄉村學校的學生大開眼界。

22:00

丁老師上門收手機。

Day 2 2 2

07:00

為了防止像昨天一樣考試打瞌睡，就晚點起床了。

8:30~13:00

先看 T 1 T1 T1 ，不會做。因為是樹上的問題，就先考慮怎麼在鍊上面做。

但是我發現在鍊上也不會做。隻會一步一步地暴力跳，而且放回樹上之後不知道怎麼從某一種顔色開始往後跳。

掙紮了很久，還是不會，太菜了。

但是如果 T 1 T1 T1 不切，根據我多次模拟賽的經驗，這次比賽就要挂了。

不管了，挂就挂吧。後兩題看起來不會太難，可能可以做。

T 2 T2 T2 看起來可以 狀壓DP ，但是這樣要記錄的狀态有 4 4 4 個：還沒有選過的隊伍，上一次選的 b b b 值，剩餘 b b b 值總和，上一支選擇的隊伍編号。這些狀态我都消不掉，那就 n ! n! n! 拿掉 60 60 60 分吧！

T 3 T3 T3 我比較有想法。

首先可以發現，一個點的 D D D 集合勢必是一條鍊上的若幹個點，因可以把這個圖變成一個樹形結構，每個點的父親是它的 D D D 集合中離它最近的那個點。

對于一個詢問 s → t s\to t s→t ，如果這是樹上的一條返祖邊或者 f a s = f a t fa_s=fa_t fas​=fat​ ，那麼顯然輸出 0 0 0 ；否則就輸出 s i z t siz_t sizt​ （ s i z i siz_i sizi​ 表示 點 i i i 在樹上的子樹大小）。

然後怎麼建樹呢？可以發現某個點的父親是把邊反向後，它的所有出邊的第一個彙合點。這樣寫起來 極 其 陰 間 ，我就挂掉了。

13:00~13:30

由于要拍合照，出考場後就在外面等了一會兒。

大家都說 T 1 T1 T1 很水，被切穿了； T 2 , T 3 T2,T3 T2,T3 貌似沒什麼人切。

然後我得知我 T 3 T3 T3 的想法就是 支配樹 ，考場上手推支配樹，我好猛耶！

可惜的是這次 G D O I GDOI GDOI 我又沒掉了。就當出來玩吧。

14:30

坐上回中山的大巴車，繼續聽歌。

路上成功地拉 W Y D WYD WYD 回坑皇室。

17:00

回到紀中。

D a y    2    T 3 Day\; 2\; T3 Day2T3 經兔子的指點豁然開朗。原來建樹反過來就行了，枚舉祖先找子孫會容易很多。

也就是枚舉每個點，把它删掉，然後從 1 1 1 出發看看哪些點到達不了（這不就是題目給出的 支配點 定義嗎？我為什麼要把它反過來啊？！）

18:00

什麼？一段考提前一天，明天就考試？！！

19:00~22:30

瘋狂複習，哦，不是複習，是學習。

才兩周怎麼就欠了這麼多知識點啊？！！

Day 3 3 3

7:00~7:30

升旗儀式。

C o t t o n Cotton Cotton 說我 D a y    2    T 3 Day\; 2\; T3 Day2T3 漏考慮了億點點情況。

9:00~17:00

考國文和數學。考完之後居然感覺良好？

Day 4 4 4

段考最後一天，考實體、英語、地理、化學。

因為堅持寫了兩周英語草書，英語作文寫得很菜。盡管如此，考完今天後還是感覺良好。

晚上看電影，就溜去機房了。手畫了一下，發現 D a y    2    T 3 Day\; 2\; T3 Day2T3 真的漏考慮了億點點情況：凡是加邊後父親改變的點都要被計算，是以不隻有 t t t 的子樹要被修改。

稍微修改一下做法，把那些父親不在 1 → x 1\to x 1→x 的支配樹路徑上、 y y y 不經過這個點的父親就能到達這個點的點的子樹大小加起來即可，注意不能算重。

好像有點亂，就是要把那些滿足 f a u fa_u fau​ 不在 1 → x 1\to x 1→x 的支配樹路徑上，且 y y y 不經過 f a u fa_u fau​ 即可到達 u u u 的點 u u u 的子樹大小加起來。

時間複雜度 O ( n m + q n ) O(nm+qn) O(nm+qn) ，可以通過這道題。

總結

雖然最後 100 + 20 + 0 + 25 + 60 + 15 = 220 100+20+0+25+60+15=220 100+20+0+25+60+15=220 ，超過估分了，但還是很遺憾，因為失誤太多了。

隻能說這兩天在深圳玩得很開心，或許也收獲了一些東西吧。

失誤的原因有很多：

1. 長期訓練積累下來的模拟賽經驗 很 大 程 度 上 不 适 用 于 省選。因為平時的模拟賽的高得分主要獲得途徑隻有切題（部分分都比較陰間，并且很多時候隻有正解打挂了或者某些東西沒有想到才能拿到部分分），是以要花很多時間來思考；而正規比賽的部分分都很慷慨，應該花大量時間打題，但我卻沒有。
2. 知識點掌握得不好，存在一定程度上的思維定勢。 D a y    2    T 1 Day\; 2\; T1 Day2T1 我沒想到的一個重要原因是看到那個 m ≤ 5 × 1 0 4 m\le 5\times 10^4 m≤5×104 沒有想到 倍增 ，因為平時做 倍增 的時候資料範圍都是 1 0 5 10^5 105 級别的。想題應該從算法的功能、本質入手。
3. 代碼實作能力弱。這個問題不是一時半會的了，必須想辦法克服。
4. 思維不夠靈活， D a y    2    T 3 Day\; 2\; T3 Day2T3 在建支配樹時想錯了以後，沒有考慮反過來思考。
5. 休息不好， D a y    1 Day\; 1 Day1 打瞌睡了。如果當時那一個小時我沒有打瞌睡， D a y    1    T 3 Day\; 1\; T3 Day1T3 我是一定能拿到 20 20 20 分的，這次比賽就是 240 240 240 分。

省選後，就要開始填文化課的大坑了。

To AFO, or not to AFO: that is the question.