终于有能贴出来的成绩了
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)