某島

… : "…アッカリ~ン . .. . " .. .
November 29, 2021

Deltix Round, Autumn 2021

於是成功的在籌辦新一輪 CF Round 之前打回黃名了。。。(求輕噴。。。
這場題目中規中矩,想上分還是挺容易的。。。

https://codeforces.com/contest/1609

Problem A. Divide and Multiply

把所有 2 因子收集起來,剩下的數里挑一個最大的乘以這些 2 因子,再加上餘下的數即可。

Problem B/E. William the Vigilant/William The Oblivious

這兩個放在一起說,給定一個 abc 字元串,
每次修改一個字元,問至少需要幾次修改操作,可以使得該串中不存在 “abc” 模式的 子串/子序列。

子串的情況討論討論即可。
子序列的情況先解決靜態的問題,然後用線段樹維護即可。

Problem C. Complex Market Analysis

先篩法做素數判定,然後按照模數分段線性掃描,每次找到素數的時候看兩邊各有多少個 1。
假設左邊和右邊分別有 p 個 1 和 q 個 1,那麼對答案的貢獻就是 (p+1)*(q+1)-1。

Problem D. Social Network

讀題鴨梨巨大。。

第一遍讀完感覺是每次加一條邊,看傳遞閉包里的最大度數,這個只要 DSU 維護連通分量的大小即可。
寫完發現樣例不對,再讀一遍,發現給的邊是要求在傳遞閉包中成立,在滿足前 i 組成立的情況下,至多加 i 條邊,原圖中最大的連通分量大小。
只要稍微改改,開個 map 維護每個連通分量的大小,然後每次出現冗餘條件是,就可以多取一個連通分量,每次取最大的幾個即可。

Problem F. Interesting Sections

給定一個數列,問有多少組區間 ,使得區間中,最小數和最大數的二進位有相等數目的 1。

感覺比賽時想偏了,用了某種求最大子矩陣的 排序+插入 合併區間的方法。。。
好像只要普通的分治就可以了。。。
不過似乎也可以不分治。