[闲聊] LeetCode Weekly Contest 336

楼主: fxfxxxfxx (爱丽丝)   2023-03-12 12:00:52
炸了 似乎只要是刚睡醒就会打很烂
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,都尽量往右排
证明的话,应该可以证每个循环结束时
解都是当下合法的最佳解中,连续选了最长结尾的那一个解
不过因为我爆炸了很难过 所以不想证 :(
作者: kerycheng (kk)   2023-03-12 12:01:00
大湿
作者: idiont (supertroller)   2023-03-12 12:19:00
第4题也没想法 试了greedy优先做重叠最多的时间点果然不会过隐藏测资QQ

Links booklink

Contact Us: admin [ a t ] ucptt.com