题目分析

这是一个循环模式匹配与区间覆盖问题。Pak Dengklek 需要找到最少的"要求"来覆盖整个墙壁，每个要求对应一个长度为 $M$ 的承包商序列与墙壁颜色的匹配。

核心思路

1. 问题转化

将问题转化为：在长度为 $N$ 的墙壁颜色序列上，用最少的长度为 $M$ 的区间进行覆盖，每个区间必须满足循环匹配条件。

2. 循环匹配条件

对于每个位置 $i$，检查颜色 $C[i]$ 是否可以被某个承包商粉刷。关键观察是：承包商 $j$ 可以粉刷位置 $i$ 当且仅当：

其中 $D[c]$ 是喜欢颜色 $c$ 的承包商集合。

3. 贪心覆盖策略

采用从右向左的贪心策略：

• 维护当前能够覆盖到的最远位置
• 对于每个位置，计算从该位置开始能够形成有效匹配的最远延伸
• 当需要开始新的覆盖区间时，选择能够覆盖最远的有效区间

算法框架

预处理阶段

1. 建立颜色到承包商的映射：对于每种颜色，记录哪些承包商喜欢它
2. 初始化匹配状态：准备跟踪每个可能的偏移量对应的匹配长度

主算法流程

1. 逆向扫描：从墙壁末端向开始端扫描
2. 动态维护匹配信息：对于每个位置，更新各偏移量对应的连续匹配长度
3. 贪心选择：当当前覆盖区间结束时，选择能够延伸最远的有效区间开始新的覆盖

可行性判断

• 如果在某个位置，没有任何偏移量能够形成完整的 $M$ 长度匹配，则问题无解
• 如果从起点无法被完全覆盖，返回 $-1$

算法特点

时间复杂度优化

• 利用 $\sum f(k)^2 \le 400,000$ 的条件，确保颜色分布的稀疏性
• 避免暴力检查所有可能的匹配，通过维护关键状态信息提高效率

空间复杂度优化

• 使用紧凑的数据结构存储颜色-承包商关系
• 动态维护必要的状态信息，避免存储整个匹配矩阵

关键洞察

1. 循环性质利用：承包商的循环指派规则使得问题具有周期性，可以模 $M$ 处理
2. 贪心最优性：在满足匹配条件的情况下，选择延伸最远的区间是最优策略
3. 稀疏性利用：题目保证颜色分布的稀疏性，使得算法在合理时间内完成

总结

该算法通过巧妙的预处理和贪心策略，将复杂的循环匹配问题转化为高效的区间覆盖问题。核心思想是利用问题的特殊结构（循环性、稀疏性）设计针对性的解决方案，避免了暴力搜索的高复杂度。