这次周赛也写得跌跌撞撞的
不过可能是因为这次有两题 hard
所以排名比想像中好
https://i.imgur.com/WKvF35r.png
1. Count Distinct Numbers on Board
对于 x > 2，因为 x % (x - 1) == 1
所以到 2 为止都总有一天会放上去
注意 n = 1 的 case 即可
2. Count Collisions of Monkeys on a Polygon
只有全部往左或全部往右可以没有碰撞
总共是 2^n - 2 种
太小看第二题没发现会到 10^9 吃了一次 TLE
直接改用 python 内建的 pow(2, n, 10**9+7)
就不用自己写 O(logn) 的次方了
3. Put Marbles in Bags
说是 hard 不过还蛮简单的
分成 k 堆等价于取 k-1 个边界
例如 [1,3,5,1] 总共有 3 个边界
(1, 3) (3, 5) (5, 1)
挑出最大及最小的 k-1 个边界即可
4. Count Increasing Quadruplets
看到 n <= 4000 可以知道大概要是 O(n^2)
考虑 (j, k) 且有 j < k 及 nums[j] > nums[k]
则以 j, k 为中心的答案数量是
(在 j 左边小于 nums[k] 的数量) * (在 k 右边大于 nums[j] 的数量)
因为我们有
在 j 左边小于 nums[k] 的数量
= 在 j - 1 左边小于 nums[k] 的数量 + nums[j] 是否小于 nums[k]
因此只要我们一开始花 O(n^2) 维护好 L[j][k] 代表在 j 左边小于 nums[k] 的数量
之后就再花 O(n^2) 扫一遍 (j, k) 即可