終於有能貼出來的成績了
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)