Re: [閒聊] LeetCode Weekly Contest 411

[involution ( )]

終於有能貼出來的成績了

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: 幹 大師
→ oin1104: 我電腦壞了 不能玩
推 sustainer123: 大師
推 Che31128: 大師
推 DJYOMIYAHINA: 幹 大濕==
推 dont: 大師 第三題我是先都塞9 再根據k=1~9分別判斷 像是8是最前後
→ dont: 三位塞8, 7看mod6改最中間兩位, 6看n 奇偶改前後跟中間兩位
→ sixB: 第三題我分case分好久
→ sixB: 有看到solution直接mod dp做起來的