数位DP

AHOI2009 同类分布

先枚举各位数字之和作为模数再DP

代码

花神的数论题

和上面那个差不多,枚举1的数量

代码

枚举+数位DP式的写法,状态的描述和传统的题目有一点区别

补题的时候顺带写了几道双指针水题…

1. LC 76：双指针

给两个串 S，T，求 S 的最短的包含 T 所有字母（需考虑个数）的子串。

双指针配合哈希计数统计即可：

代码

类似的还有：最长不重复子串、最长至多 k 个不同字符子串、寻找所有单词串联子串。

2. 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)$：

代码

周末填坑