Weekly Contest 319
又是狀況很好的一天
https://i.imgur.com/d3i0VWM.png
第一次進 30 分內
不過排名反而比昨天差
1. Convert the Temperature
看到的時候還傻眼了一下
你不是都把公式寫好了，直接複製貼上就好
2. Number of Subarrays With LCM Equal to K
之前出過 gcd 版本的
總之就是 n <= 1000
暴力用 O(n^2) 的就會過了
3. Minimum Number of Operations to Sort a Binary Tree by Level
我用 BFS 把同一層的 value 放進一個 vector
argsort 讓值介於 [0, n) 之後
這個 permutation 會形成很多個 cycle
需要的 swap 次數就是這些 (cycle 大小 - 1) 的和
例如 (0 1 3) (2 4)
這個 permutation 需要的次數是 (3 - 1) + (2 - 1)
可以用不斷的 swap(A[i], A[A[i]]) 來算出
最後把每一層加起來就可以了
4. Maximum Number of Non-overlapping Palindrome Substrings
第一個觀察是，對於中心點一樣的兩個回文
如果長度都 >= k，則要選長度小的那個
因為任何選大的的結果，改選小的都還是不會重疊
所以只需要考慮長度是 k 或 k+1 的回文
接下來要做的，就是照中心點由小到大
看這些中心點能不能生出長度是 k 或 k+1 的回文
如果沒和前面選過的重疊，就直接選
至於為什麼可以直接選，不用考慮後面的那些回文
因為，根據第一個觀察，長度只可能是 k 或 k+1
因此中心點在前面的回文的結尾不可能超過後面的人的結尾
因此如果選後面的不會重疊，改選前面也一定不會和更後面的重疊
看一下 n 的大小，n <= 2000
所以暴力從每一個中心點往外測就可以
不需要用到 O(n) 的 Manacher's Algorithm
好險，不然我早就忘了怎麼寫了