推 dannyko: 大師 02/12 12:06
爆炸~ 吃了五次 penalty, 總時間超過比賽長度
https://i.imgur.com/vosM489.png
（因為時間超過比賽長度所以更新完之後應該會更爛）
1. Find the Array Concatenation Value
照他說的做，用內建整數字串互轉的語言會寫比較快
2. Count the Number of Fair Pairs
不知道是不是我哪裡想錯了，
比我想像中的第二題要難
我的作法是
sort 過後，對每一個元素 x
用 lower_bound / upper_bound 找出在 [lower - x, upper - x] 的個數
如果自己在裡面的話要減一
最後因為每個 pair 會算到兩次所以要除二
3. Substring XOR Queries
其實就是對每個 query_i = [first_i, second_i]
找出有沒有 substring 是 first_i ^ second_i
因為 <= 10**9 所以只須考慮長度 <= 32 的即可
把 s 的所有長度 <= 32 的 substring 加入 map
要注意優先順序，只有最左側的要加入
像是 s = '1111' 就會有
map = {1: [0, 0], 3: [0, 1], 7: [0, 2], 15: [0, 3]}
沒考慮到 0 吃了一次 penalty
想成長度 <= 10 而不是 32 又吃了一次
4. Subsequence With the Minimum Score
又是一個花了一堆時間 debug 的題目
首先，可以發現，因為只考慮最左及最右
所以把 [left, right] 內的全刪了 score 還是一樣
所以其實是在問刪除最短的區間 [left, right] 能讓 t 合法
也等於是選一個 t 的 prefix 及 suffix 合起來合法（不能重疊）
首先建出 L, R, 其中
L[i] = 能使 t[0:i] 是 s[:j] 的 subsequence 的最小 j
R[i] = 能使 t[i:] 是 s[j:] 的 subsequence 的最大 j
對於某個 prefix: t[0:i]
我們要找出最小的 j 使得 i < j 且 L[i] < R[j]
因為有單調性所以可以用 sliding window / two-pointer 來做
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676174522.A.926.html