推 peter6666712: 大師 02/19 12:02
推 NTHUlagka: 大師 恭喜好猛前50 02/19 12:03
推 MurasakiSion: 大師 02/19 12:03
→ NTHUlagka: 第三題我用hash map一直TLE 後來優化才有辦法過orz 02/19 12:05
→ YukihanaLami: 大師 02/19 12:06
加罰時 44:26，不過排名比想像中好很多
排 50 名，史上最好的一次
https://i.imgur.com/Cl32lr7.png
1. Merge Two 2D Arrays by Summing Values
用 map 收集起來就好，而且 map 會自己幫你排好序
反正 n <= 200, O(nlogn) 綽綽有餘，不需要麻煩的用 two-pointer
2. Minimum Operations to Reduce an Integer to 0
隨手寫了一個每個 node 有 34 條邊的 BFS
(+1, +2, ..., +2^16, -1, ..., -2^16)
但 TLE 了，蠻意外的 應該是因為我用 set 而不是 vector 來存走過的點
改成只有 +- least significant bit 才過
仔細想想，好像可以分成若干 1111 的 group
如果長度 >= 2 就花兩步，如果長度 == 1 則只花一步
3. Count the Number of Square-Free Subsets
會被 > 1 的平方數整除等價於會被某個質數的平方整除
例如會被 a^2 整除，a 的所有質因數的平方還是可以整除
因為 nums[i] <= 30，用手算可以發現 <= 30 的有 10 個質數:
[2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29]
想要保持以上十個數的平方都不能整除的話
質因數分解以後上面出現的次數要 <= 1
因此只會有 2^10 總共 1024 種狀態
n <= 1000 所以 dp 做狀態轉移即可
狀態轉移：
oldstate | bit --> newstate
其中 bit 是新的數質因數分解時十個質數出現的次數的 bitset 形式
並且要求 oldstate & bit == 0, 也就是沒有重複的質數出現
（否則 >= 2 會被質數的平方整除）
4. Find the String with LCP
先考慮假如這樣一個合法的字串存在的話應該要長什麼樣子
稱他為 ans 好了
首先，因為各字母是對稱的，所以第一個一定填 'a'
接著，我們可以藉由檢查 lcp[i][j] 是否 >= 1 來決定 ans[i] 是否等於 ans[j]
如果 lcp[i][j] == 0 for all i < j, 則 ans[j] 必須給他一個新的字元
當然如果超過 26 種就失敗了
這裡其實可以存 26 個字母第一次出現的 index 就好
不過因為 n <= 1000 所以直接遍歷所有 i < j 就可以了
這樣我們得出了一個字串 ans 有
「假如答案存在，則 ans 一定是答案」
現在剩下檢查 ans 能不能讓 lcp 合法
可以發現有
lcp[i][j] = 0, if ans[i] != ans[j]
lcp[i][j] = 1 + lcp[i+1][j+1], if ans[i] == ans[j]
一個一個檢查是否符合即可（邊界要注意）
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676779291.A.E97.html