[Note] 构造策略

[L4] 构造策略

1. 生态位

• 识别:

  1. 题面要求输出满足某种约束的“任意一种方案”。

  2. 解空间巨大（如 $2^N$ 或 $N!$），标准搜索/动态规划因复杂度过高而“失效”。

  3. 存在极其苛刻的边界限制，暗示了解的唯一性或某种强规律性。

• 地位: 偏数学构造思维，一般作为“掀桌用”。它不搜索解，它生成解。

• 用途: 绕过复杂的计算过程，直接利用数学性质（如奇偶性、对称性、周期性）生成答案。

2. 逻辑支点

2.1 核心思维：自由度最大化

• 中译中: “在不违规的前提下，怎么自由怎么来。”

• 策略: 识别出题目中的“硬约束”和“软约束”。

  • 硬约束: 必须满足的（如 $k=2$ 连续和为合数）。

  • 软约束: 题目没规定，但你可以随便填的。

• 技巧: 在非关键位置填入“最安全”的值（如 inf、0 或循环序列），把所有的“余量”都留给最难处理的冲突点。

3. 实战部署

• 构造题无固定模板（哭。

4. 知识关联

• 如果你想找“各玩各的”:

  • TZC25L 合数封印: 奇偶分区。

• 如果你想找“标记禁区”或“别无选择”:

  • CF2167E khba Loves to Sleep!：把距离阈值转化为禁区补集容量。

• 如果你想找“约束冲突消解”:

  • CF2157C Meximum Array 2: 利用极大值 inf 破局。

• 如果你想找“位移与平移”:

  • CF2164D Copy String: 位移 offset 映射。

• 如果你想找“结论杀”:

  • CF2183B Yet Another MEX Problem: 性质发现后的极简构造。

• 关联笔记:

  • 贪心策略: 贪心是构造的“最优选择器”。

  • [[41_数论基础]]: 提供奇偶、质合等底层性质支撑。

  • 浅谈二分答案：通过二分确定构造的“极限参数”。