推 pandix: 笑死 我今天也吃爽爽 12/25 00:11
推 NTHUlagka: 第四題對c++使用者小麻煩 哭啊太久沒寫python了 12/25 01:08
平安夜
一個人孤單的寫著周賽
孤單的吃了三個 penalty
:(((((((
https://i.imgur.com/hGkRa2J.png
(不知道為什麼力扣區沒同步到，加他們進來之後應該會掉不少)
耗時最短的反而是第四題（5分39秒），也只有第四題一次過 :(((
1. Maximum Enemy Forts That Can Be Captured
n <= 1000，所以可以暴力搜，但我減法寫反方向吃一次 penalty :(
2. Reward Top K Students
這題太慘了，我看到字串要以空白分割就有點不太爽
想要改用 python
但突然有一個聲音告訴我要用 C++ 寫
結果就是寫到頭破血流，找了好久才發現漏了最後一個字串
吃了一次 penalty + 耗時二十分鐘 :(((
3. Minimize the Maximum of Two Arrays
本來在想有沒有解析解
想了一會之後決定用二分搜
x「足夠大」的條件等價於同時符合以下三點
1) x - (x / divisor1) >= uniqueCnt1 /* 有夠多的數可以填滿 uniqueCnt1 */
2) x - (x / divisor2) >= uniqueCnt2 /* 有夠多的數可以填滿 uniqueCnt2 */
3) x - (x / lcm(divisor1, divisor2)) >= uniqueCnt1 + uniqueCnt2
/* 有夠多的數可以同時填滿 uniqueCnt1 和 uniqueCnt2 */
對 x 做二分搜，找出最小的合法 x 就可以了
乘法超出 int 範圍又吃了一次 penalty :((
4. Count Anagrams
看到又要用空白分割，我決定不再頭鐵了，改用 python
仔細一看
這題不就是單純的庭院深深深幾許嗎，根本一模一樣
只有在算 L!/n1!/n2!/n3!... 時 (L = n1 + n2 + ... + nk)
因為 L, n1, n2, ... 都可能很大，直接用大數乘法可能會超時
所以要預先計算 FACT[0], ... FACT[100000] 代表階乘
邊乘邊 mod 就可以了
然後除 n1! 等價於乘上 n1! 在 10^9+7 下的乘法反元素
可以直接用 pow(FACT[n1], -1, 10**9+7) 來計算
求求你們不要再說第四題是垃圾水題了
每當我前三題吃了penalty被壓得喘不過氣來的時候
只要想到第四題可能夠難能讓我追回一點排名
就能找回活下去的希望
剛才看到了題目
雖然我知道是高中排列組合的可能性很少 畢竟世界上有那麼多題目
難免會有相似的存在
但那個題型實在太像了 我一看到就能反應過來
感覺世界開始逐漸崩塌
求求你們不要再討論這件事了
再這樣下去我連唯一支持自己活下去的理由都沒有了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671897894.A.32C.html