推 kerycheng: 大濕 03/12 12:01
推 idiont: 第4題也沒想法 試了greedy優先做重疊最多的時間點 03/12 12:19
→ idiont: 果然不會過隱藏測資QQ 03/12 12:19
炸了 似乎只要是剛睡醒就會打很爛
https://i.imgur.com/Tmqnk8c.png
（因為接近 1:30 所以之後應該會更爛）
1. Count the Number of Vowel Strings in Range
蠻煩的無聊題，不過反正就一個一個檢查
2. Rearrange Array to Maximize Prefix Score
降序的 sort 是最佳解
3. Count the Number of Beautiful Subarrays
可以發現是 beautiful 若且唯若全部 xor 起來是 0
定義 prefixXor: X[i] := nums[0] ^ nums[1] ^ ... ^ nums[i-1]
則 subarray nums[i..j] 是 beautiful 若且唯若 X[i] == X[j+1]
所以用一個 hashmap 存 prefixXor
對每個 j 看有多少 i < j 使 X[i] == X[j+1] 即可
4. Minimum Time to Complete All Tasks
突然卡住想不太到怎麼解
想了一堆方向，dp 和 binary search 好像都行不通
最後是想到當 duration = 1 時可以 greedy 的取右端點才想到怎麼解
不過因為想到的時候已經是快結束了
所以實際上我沒有證過正確性就直接寫了
總之就是先用右端點排序後
對每個 task，都盡量往右排
證明的話，應該可以證每個循環結束時
解都是當下合法的最佳解中，連續選了最長結尾的那一個解
不過因為我爆炸了很難過 所以不想證 :(
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.198.173.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1678593654.A.FC1.html