2020年11月1日 星期日

Codeforces Round #680 雜記

#第一次就上手如何跌出LGM


開粉專第一篇就來教大家如何上手跌出 LGM XD

= = =

今天最大的敗筆大概是賽前一兩分鐘還在和別人聊天以及因為這場比賽而沒能和老婆一起吃晚餐導致心情有點亂吧 (>__<)

以後還是不要打和吃飯時間重疊的比賽好了 (>__<) 

= = =

開場看了 A 題,題目簡單易懂

給定兩個數 p, q (p<=10^{18},q<=10^9),請找到最大的數滿足 x 整除 p 且 q 不整除 x。

這題算是比較套路的,我第一個閃過的念頭其實是使用大質因數分解的模板來枚舉所有 p 的因數來 check 答案 XD。

但是在 10^{18} 範圍的 p,因數可能有超多個!所以必須減少需要檢查的因數個數。

要選哪些數呢?先不管要做什麼事情,反正有個常見套路就是要枚舉質因數。

那麼枚舉質因數能做啥呢?啊!只要 x 的某個質因數的次方小於 q 的質因數的次方就行了!

枚舉 p 的質因數似乎有些繁複,於是再多想一點就會發現只要枚舉 q 的質因數就行了!

枚舉 q 的質因數並把 p 一直除以該質因數直到不被 q 整除,那麼剩下的數就是 x 的可能候補之一,最後取最大的候補就好啦~

雖然我打那麼多字,可是這些思考大概是一分多鐘以內的事,並只用兩分多鐘就寫完了 code,在不到 4 分鐘時就過了 Pretest!

此時看了一下每題 AC 人數,發現 AC A 題的只有 8 人,而 AC B 題的已有 4 人!!!??

= = =

接著馬上看 B 題,B 題的敘述很短:

給 2n 個數,把他分成 2 組各 n 個數,第一組為命名為 a_i, 且把它由小到大排序,第二組命名為 b_i 且把它由大到小排序。

每個分法的 cost 為 abs(b_i - a_i) 的總和,請計算所有分法的總和。

這題是前三題我想最久的題了...

這種題乍看之下也是個套入題,就是去算每個數字的對答案的貢獻。

於是我就開始去思考,每個數字在 cost 中是負和正時各有幾次,我列了好多次式子都無法把公式列清楚,看來我比賽前的心煩意亂在需要數學計算的時候就體現出來了 (>__<)

算了好久並且用程式寫了幾個式子都沒有過 Sample。

這時我提醒自己,可是有 4 個人在開場馬上就 AC 了,公式應該超簡單。

於是我就在計算紙上模擬一些實際例子。然後馬上就發現,前 n 個數對答案的貢獻總是是負的,並且後 n 個數對答案的貢獻總是是正的...

又再次的驗證,什麼都想不出來的時候,觀察一些 Sample 如何計算答案就有機會猜到答案...

= = =

前兩題都過了 pretest 後,比賽已過了 21 分鐘,可是還沒有人過了 pC 的 pretest,於是我覺定從 E 題看回來。

但是 E 題是個互動題 =口=,我看都沒看就跳看 D 題。

D 題看完並理解題意,是個構造題,據我經驗,構造題通常在思考上的不確定性太大,所以我想都沒想就直接看回 C 題了...

C 題題意如下:

給一個 Graph,每個點屬於 1~K 中的恰一個 Group,有些 Group 可能不包含任何點,請問有多少 Group Pair 滿足這兩個 group 的點所形成的導出子圖 (induced subgraph) 是個二分圖。(點數、邊數和 K 都不超過 5*10^5)

這時我有些急躁... 一剛開始我看錯題意了...,以為它是問有多少導出子圖的補圖有完全匹配...

於是就覺得,這題目怎麼看起來那麼難 =口=

花了一些時間後我發現,要解我讀錯的題目,我就能夠解出點數和邊數都超多的圖的一般圖匹配!

這不可能啊!結論=>我讀錯題了,於是我在重讀一次題...才發現問的是二分圖...

題目一正確後我就知道正確的做法,因為是判斷二分圖,並且算是有些動態的判斷二分圖,那麼和記憶中匹配的演算法就只有並查集 + 時光逆流了。

我使勁把他刻完了,又重寫了一次時光逆流...,以後應該也要把時光逆流的部分放入 codebook (此處應有思考的表情)

Debug 了許久,直到比賽剩 1 個小時的時候左右才過了 Sample。

原本想檢查一下再傳,但衡量了這題 code 有點長且已經沒有時間優勢了。我求勝關鍵要擺在多 AC 一題。所以值得賭賭看能不能一次就過 pretest,可惜失敗了 (此處應有哭臉表情)

首先馬上就抓到了一個 x,y 打反的 Bug...但再傳一次還是 WA。

接著我又花了好久時間都找不到 Bug... 中間又亂傳了一次,於是共錯了 3 次。

真的百思不得其解!我一定沒有 Bug!若有 Bug,那肯定是我題目又讀錯了!

於是我又再仔細讀了幾遍題目,然後發現....我的作法中殘留了原本讀錯題目時才會產生的條件:Group Pair 的總點數必須是偶數才有可能滿足條件 (ꐦ ಠ皿ಠ )

為什麼我多寫了這個條件還能過所有 Sample 啦...

於是我把這個條件移除後就過 Pretest 了...

= = =

還剩 40 分鐘

但我腦袋大概有點壞掉了。沒能冷靜下來思考題目,在試圖解 D 題的過程中慘不忍睹,這次就不把慘不忍度的過程記錄下來了 (>__<),感覺沒有任何教育意義,純粹就是我腦袋壞掉...

比賽結束後原本的名次是一百多且 Rating 預測也是會減少一百多,不過評測結果有非常多人 C 題 WA 掉了 (此處應有困惑表情),於是我名次以及減少的 Rating 數值都落回 100 以內。

明天還有一場 Div. 1 難度的 Codeforces 比賽,且這場比賽是 VK Cup Final 的題目!依過去經驗,VK Cup Final 的題目都會很精彩!請大家敬請期待!

沒有留言:

張貼留言