GDKOI2021遊記
Day0
期末考試的最後一天。
考完後有了一種整個人都放松了的感覺……
Day1
寒假第一天。破天荒地一直賴到起床鈴響。
其實考場就在本校，不管從什麼角度都不是遊記呢……
權且當作在這個不算小的校園裡遊蕩吧。
T3
發現字元串不會變，那麼我們先馬拉車一下。
[ans_{[l, r]} = max_{i=l}^{r} {min{len[i], i-l+1, r-i+1}}
]
還是不大好求。那麼考慮二分。那麼在([l+mid-1, r-mid+1])中查找回文長度最大的串判斷即可。
T4
遞推莫得前途，我們考慮生成函數。
然後熟練運用二次方程求根公式可以得到一個帶根号的多項式。
接下來就是套路了。
套路
All in all
第一天發揮比較正常(?)
然後第二題想出來寫炸了……
Day2
T1
套路期望題
套路*2
T2
題意轉化後是一個線段覆寫最左端點問題。
一直在思考線段如何撤銷，想了各種方法都沒有思路……
比賽後同桌提醒我隻要求沒有被覆寫到的最右端點就行了……
我怕不是個智*
T4
原題說的是下濾，其實我們從小到大上濾也是可以的。
雖然我不會證就是了
然後發現每次上濾的點把堆分成了互不幹擾不相交的兩段。
在序列上一共會有(O(log_2 n))段，每段中我們查詢最小值進行下一次上濾。
一共就是(O(n log_2^2 n))的
In a word
這一天感覺沒有發揮太好，一道做過的套路題沒有推出來，一道顯然的簡單題沒有看出來。
總的來說時間配置設定不大合理，做過的題也沒有好好總結。
Day3
Difficulty++
T1
套路是先分解質因數。
然而後面的按照不同質因數不同次數染色是我沒想到的，貢獻為那個質因數也是我沒想到的。
然後考慮如何隻算一次。
我們欽定相同顔色隻算DFS序最小的。
瘋狂分類讨論.jpg
T2
想到拆成字首和。
然後考慮分治，發現前面與後面的貢獻可以寫作卷積形式，FFT (O(n log n cdot C))（C為巨大的常數）
然而需要一點平衡規劃技巧，在區間足夠小時直接暴力
是以我真正的考察點是平衡規劃哒！
T3
遊戲好評，考場上寫了一個模拟玩了好久……
要注意到每個點被擴充到的方案數的奇偶性決定了這個點能否存活
然而講題人太Rush了我沒聽清……
T4
組 合 題
前三個subtask都還好。
第四個先二分一個半徑。
然後任取一個點将距離小于兩倍半徑的點分成同一塊從原圖中去除。重複以上步驟直至原圖中沒有點。
然後考慮K的限制。
如果一個塊中有一個點能夠換到另一個塊裡，那麼從換入的塊向換出的塊連邊，那麼我們隻要找一個從小于K的塊出發到大于K的塊的路徑即可。
換完之後記得重構圖……
注意以下兩點
- 選出的中心兩兩之間距離大于兩倍半徑。
-
不存在兩個選出的中心在最優方案中存在于同一個塊。
即可說明正确性。
All in all
在題目偏難的情況下我這種暴力選手就有新生活的希望了(并沒有
最後暴力寫炸了好多……
實作能力有待提高。