推 pandix: 大師 02/26 12:04
推 NTHUlagka: f大跟p大好猛都前100 邊版真的各種神人 02/26 12:22
推 dustsstar79: 大師 02/26 12:23
推 MurasakiSion: 大師 02/26 12:25
推 dannyko: 第三題我直接憑感覺 能證出來的果然是真強者 02/26 15:23
今天還行 不過因為這次難度比以往簡單
所以把 < 寫成 <= 扣的五分鐘就損失很大了
https://i.imgur.com/FRr45LE.png
1. Left and Right Sum Differences
直接照他說的做出 leftSum 和 rightSum 就可以了
leftSum[0] = 0
leftSum[i] = leftSum[i-1] + num[i-1]
然後因為 n <= 1000，所以甚至用 O(n^2) 的寫法也沒問題
2. Find the Divisibility Array of a String
我們要計算出 div，其中 div[i] 為 word[0..i] % m 是否是 0
可以發現
word[0..i] % m == (word[0..(i-1)] * 10 + word[i]) % m
== ((word[0..(i-1)] % m) * 10 + word[i]) % m
所以就一直 *10 加上 word[i] 再看 %m 後是不是 0 即可
注意 10^9 * 10 會超 32-bit
3. Find the Maximum Number of Marked Indices
首先，能不能 mark 跟 i, j 的位置無關所以我們就無腦先 sort
接著因為組數一定 <= n/2，假設答案是 k 且是以下幾組
(a_1, b_1), ..., (a_k, b_k)
觀察到，我們一定可以讓
a_1 <= a_2 <= ... <= a_k <= b_1 <= b_2 <= ... <= b_k
因為如果有一組 a_i <= a_j <= b_j <= b_i 的話
我們可以改成配對 (a_i, b_j), (a_j, b_i) 也是合法的
接著我們發現我們可以讓
a_1 = nums[0], a_2 = nums[1], ...
b_k = nums[n-1], b_{k-1} = nums[n-2], ...
因為 a 只會變小 b 只會變大所以還是一定合法
因此只要用 two-pointer
讓 a 從 0 開始，b 從 n/2 開始 greedy 的取就好了
因為如果存在解，就必定存在有 nums[0] 的解...
把 < 寫成 <= 錯了一次 :(
4. Find the Maximum Number of Marked Indices
首先觀察到，會失敗若且唯若 grid[0][1] > 1 且 grid[1][0] > 1
因為如果其中一個 <= 1, 可以來回移動到宇宙毀滅再出發
這樣就一定每一格都可以走
接著看奇偶性，偶數的點一定只能在 time 是偶數時抵達
因此如果一個偶數的點的值是奇數 2k + 1
他可能的最佳解最好就是 2k + 2
我們可以先掃一遍 grid 處理完
因為來回移動的特性，我們發現如果存在鄰近的點能在 t = k 時走到
則從那個鄰近的點過來的最佳解就會是 max(k + 1, grid[x][y])
所以就用 dijkstra 做一做就好了，O(|V| + |E|log|E|)
因為 |E| <= 4|V| 所以就是 O(|V|log|V|)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677384076.A.194.html