Re: [閒聊] LeetCode Weekly Contest 411

看板Marginalman作者involution ( )時間1年前 (2024/08/18 17:39)推噓5(5推 0噓 4→)

留言9則, 6人參與討論串1/3 (看更多)

終於有能貼出來的成績了 https://i.imgur.com/jn59rSX.png

Q1: 我寫了 sliding window 才發現 n <= 50 有點浪費時間了 Q2: 簡單的 DP, 存以 energyDrinkA 結尾和以 energyDrinkB 當下的最佳解即可 Q3: 我囉哩八縮寫了一大堆不知道有沒有更好的解法假如答案是 a0a1a2a3...a_{n/2}...a2a1a0 那他代表的數字是 a0*10^0 + a1*10^1 + ... 刷一遍 10^i mod k 是多少就可以知道 a_i 影響多少接著從 a_{n/2} 開始倒著填到 a_0 (因為 a_0 越大越好) DP[i][r] 代表填到 a_i 時能達成 mod k 為 r 的最大數，則有 DP[i][r] = max_{0<=d<=9} [ DP[i+1][r-(d*b_i) mod k] 有值 ] 其中 b_i = (10^i + 10^{n-1-i}) mod k 之後就從 DP[0][0] 開始重新建出這個字串其實我連保證有解都沒證不過反正他沒講沒解要怎樣所以就是一定有解了（大概吧） Q4: 如果不是 query 題這題會是標準的 sliding window 一個很關鍵的觀察是設一個函數 f(b) --> a 其中 a 是最小能使 s[a..b] 合法的 index 則 s[i..b] for a <= i <= b 是以 b 結尾的所有合法 substring 而且可以刷一遍 sliding window 建好 f 的表對於 query (l, r) 我們要求的就變成 sum((b-max(l,f(b))+1) for b in [l..r]) 因為 f 是遞增的可以用二分搜找出最小的 a' 使得 f(a') >= l 則要求的變成 sum((b-l+1) for b in [l..(a'-1)]) ...(1) + sum((b-f(b)+1) for b in [a'..r]) ...(2) (1) 直接乘起來 (2) 只要先算好 f 的 prefix sum 也能馬上得出來就得出最後的答案了體感難度 Q3 >= Q4 >>>> Q2 > Q1 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723973970.A.842.html

推

oin1104

08/18 17:40, 1年前 , 1^F

08/18 17:40, 1^F

→

oin1104

08/18 17:40, 1年前 , 2^F

08/18 17:40, 2^F

推

sustainer123

08/18 17:41, 1年前 , 3^F

08/18 17:41, 3^F