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
好险，不然我早就忘了怎么写了