JOI Open2019 T1 三级跳
考虑对于一组询问的合法的解， ( t (a,b,c))， 如果有 ( t ale ile b) 使得 ( t A_i ge min(A_a,A_b))， 那么把 ( t a、b) 中那个 ( t A) 值较小的换成 ( t i)， 答案不会变劣， 所以只需考虑满足它们之间的数都严格小于 ( t min(A_a,A_b)) 的 ( t a,b) 。这样的 ( t a,b) 只有 ( t O(n)) 组， 这是因为它们必然分别是它们之间的最大的数的 “左边第一个比这个数大的数” 和 “右边第一个比这个数大的数”。(相邻的 ( t (a,b)) 也要考虑)
不会了， 看题解了。
首先预处理出所有这样的 ( t (a,b))， 然后考虑把询问离线， 按照左端点从大到小的顺序排序， 逐个处理， 这样可以使得决策集合单调不减。 考虑对于每个新加入的 ( t (a,b))， 把所有满足题目条件的 ( t c) 都维护一个 ( t B) 值， 为最大的 ( t A_a+A_b)， 再用线段树维护下整个序列的 ( t max(B_i+A_i)) 就做完了。
从粉兔那学了不少代码经验啊ovo， 以前维护复杂线段树信息好像也是从他那学的。
甚至还学到了一次单调栈预处理序列里某个数左右最近的更大值
[AHOI2009]同类分布（弱化版， 叫月之谜）
这种题就是算出 ( t [1,R]) 和 ( t [1,L-1]) 的答案， 相减。
考虑计算 ( t [1,N]) 的答案， 考虑枚举前 ( t i) 位都和 ( t N) 的前 ( t i) 位都相等且第 ( t [i+1,k]) 位和 ( t N) 的第 ( t [i+1,k]) 位都不相等的答案， 具体来说， 从大到小枚举从小到大的第 ( t i) 位填什么， 若小于 ( t N) 的这一位， 则后面的数可以随便填， 把方案累加到答案里； 否则， 令这一位等于 ( t N) 的这一位， ( t i=i-1) ， 继续这一过程。
考虑如何累加答案，发现很难统计， 因为最终的数位和不确定。
由于数位和的范围很小， 考虑在外层枚举数位和，假设枚举到的数位和为 ( t sum)。
考虑在枚举第 ( t i) 位的时候维护最高位到第 ( t i) 位的数位和 ( t t) 和当前数值对 ( t sum) 取模的结果 ( t q)。（当前数值是指后面补 ( t 0) 后的数值）。
设第 ( t i) 位当前从小到大枚举到数字 ( t p)，
- 若 ( t p) 小于 ( t N) 在第 ( t i) 位的数字， 则后面 ( t i-1) 位可以随便填。加上 ( t i)， 后面一共 ( t i) 位的数值和加起来膜 ( t sum) 的值要是 ( t sum-q)， 且后面的数位和要是 ( t sum-t) ， 把这部分答案加到总答案里。
- 否则， 令 ( t t=t+p)， ( t q=(q+p*10^{i-1})mod sum)， 继续枚举下一位。
考虑情况一的答案怎么统计， 这个答案一共有这么几个限制： “膜一个数的余数”、“数位和”、“位数”。
其实这就可以上数位 DP 了，
设 ( t F[i,j,k,l]) 表示由 ( t i) 位数字组成、数位和为 ( t j)、对 ( t k) 取模余数为 ( t l) 的数有多少个。（允许前导零）
状态转移方程比较好想：
那么情况一要加到总答案里的就是： ( t F[i-1,sum-t-p,sum,(sum-q-p*10^{i-1})mod sum])
话说数位 DP 其实还有其它实现， 这题的加强版是 [AHOI2009]同类分布 ，用这种方法过不了qwq， 建议学一下更优的写法。