→ PyTorch: 大師 04/30 12:02
推 JIWP: 大師 04/30 12:03
推 Rushia: 你好優秀 04/30 13:25
推 pandix: 大師 04/30 14:13
推 NTHUlagka: 好猛 04/30 19:39
昨天雙週賽 40 名，今天 58 名，開心
https://i.imgur.com/AMyk2Le.png
其實排名我原本以為會更爛
因為我中間有寫錯方向重寫
最後一題蠻可愛的
1. Determine the Winner of a Bowling Game
這在第一題中算是很麻煩的了
維護這個x2 buff 剩餘的回合數
如果這回合打出 10 分就重置成兩回合
否則就減一
2. First Completely Painted Row or Column
因為數字不會重複，所以可以維護
1) R, R[i] 代表這一橫排被選過的次數
2) C, C[i] 代表這一直排被選過的次數
照 arr 順序選，選到就把相應的 R 和 C 加一就好
滿了就 return
3. Minimum Cost of a Path With Special Roads
關鍵的觀察是，只有兩種走法
a) 走特殊通道
b) 正常的走到終點或某個特殊通道的入口
所以只要維護出入口加上起終點的 graph 即可
|V| <= 402, |E| <= |V|^2
之後用 dijkstra 即可
4. Lexicographically Smallest Beautiful String
我們要讓字串中不存在長度 >= 2 的回文
假如 s 存在回文 t，則 t 拔掉頭尾還是回文
所以 s 不合法若且唯若存在長度是 2 或 3 的回文
也就是我們只要讓所有長度是 2 或 3 的子字串都不是回文就好
而長度是 2 的子字串不是回文若且唯若兩個字符不一樣
長度是 3 的子字串不是回文若且唯若頭尾兩個字符不一樣
也就是我們只需要讓當下這個字符和前兩個不一樣即可
要找出最小的 beautiful string
只要找出從尾巴數回來第一個可以增加又保持合法的 index
後面就在保持合法的情況下 greedy 的取最小的那個字符就好
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1682827248.A.5F3.html