====== 本周推荐 ======
===== Marvolo =====
数位DP
==== 同类分布 ====
[[https://www.luogu.com.cn/problem/P4127|AHOI2009 同类分布]]
先枚举各位数字之和作为模数再DP
[[2020-2021:teams:tle233:Code1|代码]]
=== 花神的数论题 ===
[[https://www.luogu.com.cn/problem/P4317|花神的数论题]]
和上面那个差不多,枚举1的数量
[[2020-2021:teams:tle233:Code2|代码]]
枚举+数位DP式的写法,状态的描述和传统的题目有一点区别
----
===== Kevin =====
补题的时候顺带写了几道双指针水题...
**1. [[https://leetcode.com/problems/minimum-window-substring/|LC 76]]：双指针**
给两个串 S，T，求 S 的最短的包含 T 所有字母（需考虑个数）的子串。
双指针配合哈希计数统计即可：
[[2020-2021:teams:tle233:Code3|代码]]
类似的还有：[[https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/|最长不重复子串]]、[[https://leetcode-cn.com/problems/longest-substring-with-at-most-k-distinct-characters/|最长至多 k 个不同字符子串]]、[[https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/|寻找所有单词串联子串]]。
**2. [[https://loj.ac/problem/2086|LOJ 2086]]：双指针+线段树**
求所有至少k覆盖的区间组中，花费最少的区间组的花费（一组区间的花费定义为，最长区间的长度减去最短区间的长度）。
考虑将区间按长度排序，那么解肯定是连续取的一段。
注意如果 [i:j] 可，那么 [i:j+1]、[i-1:j] 一定都不是最优解。因此只需先枚举 i，然后 j 从 i 枚举到刚好至少 k 覆盖为止。维护一下数轴做区间+1和区间查最大就可以判断了。
复杂度 $O(n^2logn)$ 高了一点，考虑单调性，其实有很多重复操作（i 枚举了很长一段，到 i+1 又从头开始了，其实从 i 变成 i+1 的时候 j 应该至少从上次的 j 开始的），因此双指针同时枚举 ij 即可。复杂度 $O(nlogn)$：
[[2020-2021:teams:tle233:Code4|代码]]
----
===== TownYan =====
周末填坑