某島

… : "…アッカリ~ン . .. . " .. .
May 8, 2020

Codeforces Round #639

喜聞樂見的連續兩場 unrated … 導致第二天直接開了一場壓力測試。

A. Hilbert’s Hotel

按照題意求余統計有沒有重複即可,作為 A 題來說未免有點太水了。

B. Monopole Magnets

讀題壓力巨大,這裡 possible 是必須要存在一種讓 N 極移動過去的方案,所以每個連通塊需要恰好有一個 N,然後只需要檢查掉不合法的情況就好。

C. Quantifier Question

考察一些情況,有環的話顯然無解。否則,對於 xi < xj,一定是一個 A 一個 E,如果 i < j,那麼 A xi E xj,如果 j < i,那麼 A xj E xi 就好。
所以先檢查是否能夠拓撲排序,然後貪心的優先設置 A 即可。

D. Résumé Review

顯然先對函數做一下差分,發現是一個二次函數,對稱軸在 0.5,所以在正整數範圍內單調遞減,於是可以貪心。
考慮到 k 很大,可以二分 threhold,裡層可以再套個二分或者解二次函數。
這樣最後 k 可能還沒有全部用上,出來之後還需要補正一下。

E. Train Tracks

數據結構題。
這個切鐵路的動作和 link-cut tree 里的 access 完全一致。
所以第一問可以 link-cut tree,然後就要想想第二問怎麼寫比較簡單了,最好也能用 link-cut tree。

F. Piet’s Palette

套路題。
構造出矩陣表示出題目中的幾個操作。
然後可以高斯消元即可。