推 pandix: 大師 01/29 12:07
推 SecondRun: 大師 01/29 12:09
推 pandix: 原來python pow可以加模數 又學到了 01/29 12:10
→ Jaka: 大師 01/29 14:05
這次周賽也寫得跌跌撞撞的
不過可能是因為這次有兩題 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) 即可
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674965053.A.C7D.html