这次还行
https://i.imgur.com/EryuGTN.png
感觉最后一题网络上应该一堆答案
不过我写的卡卡的浪费很多时间
不然我前三题的状况还不错
1. Form Smallest Number From Two Digit Arrays
两层 for 循环，如果数字一样可以只有一个数
取最小的
2. Find the Substring With Maximum Cost
变形的 maximum subarray
其实就只需要维护字母对应到值的表
再把 s 都转成对应的值再直接套 max subarray 就可以了
3. Make K-Subarray Sums Equal
看了一下解出来的人数，大家好像认为这题比第四题难
我自己是觉得比一般的第三题难
至少感觉需要两种第三题等级的技巧同时用在这一题上
所有长度 k 的 subarray 的和都一样，
所以对任意的 i，我们有
arr[i] + ... + arr[i+k-1] == arr[i+1] + ... + arr[i+k]
消一消之后就能得到 arr[i] == arr[i+k]
因为是环形的，所以会被切成 gcd(arr.size(), k) 个 subsequence
令 g = gcd(arr.size(), k)
对任意 0 <= i < g, 我们有
arr[i] = arr[i + g] = arr[i + 2g] = ...
而让 arr[i], arr[i+g], arr[i+2g], ... 全部一样的最小 cost
就是取他们的中位数
4. Shortest Cycle in a Graph
看题目就感觉是经典题
我自己也觉得好像很久以前有做过的样子
不过实际写起来就一直卡卡的
最后我的作法是对每个节点 v 做 bfs
如果有某个走过的点想要走到另一个走过的点
就计算他们的 cycle 的长度
因为是 bfs 所以这会是这两个点经过 v 的最短 cycle 了
不过要处理像是不能朝原路走回去之类的细节
后来是觉得如果改成每次拔掉一个边 (u, v) 后
再用 bfs 算 u