D. 有趣还是恐怖? 详细题解

题目核心理解

给定 $n$ 个节点的无向完全图（对应游戏关卡），部分边已固定为 F/S（数量 $\le \lfloor n/2 \rfloor$）。 你需要将所有 ? 填充为 F/S，满足： 无论节点如何排列成路径，连续同色边的长度一定不超过 $\boldsymbol{\lceil \dfrac{3n}{4} \rceil}$。 要求输出任意合法方案。

---

核心思路

1. 关键构造原理

采用不平衡二分图构造，这是满足最长同色路径限制的核心方法：

• 将节点分为小集合 A 和大集合 B
• 集合内部的边全部染成 S
• 集合之间的边全部染成 F
• 小集合大小取 $\boldsymbol{\lfloor n/4 \rfloor}$ 或 $\boldsymbol{\lfloor n/4 \rfloor-1}$，大集合大小 $\lceil 3n/4 \rceil$

2. 合法性保证

• 内部路径长度 $\le \lceil 3n/4 \rceil-1$，满足题目要求
• 跨集合路径交替分组，长度也不会超限
• 题目允许的上限 $\lceil 3n/4 \rceil$ 完全覆盖构造结果

3. 已有边约束

• 所有已固定的 S 必须在集合内部，不能跨集合
• 已固定的 F 自动满足跨集合规则，无需额外处理
• 利用 $n\le24$，直接枚举子集找到合法的小集合

---

算法流程

1. 设定目标大小：$target = \lfloor n/4 \rfloor$
2. 枚举所有节点子集，筛选大小为 $target$ 或 $target-1$ 的子集
3. 检查该子集是否合法：所有已固定的 S 边都在子集内部
4. 找到合法子集后，按照规则填充所有 ?
   • 同集合 → S
   • 不同集合 → F
5. 保留输入中已有的 ./F/S，输出最终矩阵

---

公式与复杂度分析

小集合大小：

$$size(A) = \left\lfloor \frac{n}{4} \right\rfloor \ \text{或}\ \left\lfloor \frac{n}{4} \right\rfloor - 1 $$

连续同色边上限：

$$\max\_len = \left\lceil \frac{3n}{4} \right\rceil$$

复杂度

• 枚举子集：$O(2^n)$，$n\le24$ 可安全通过
• 构造答案：$O(n^2)$
• 总时间复杂度：$O(2^n + n^2)$

完全支持题目 $n\le 24$ 的范围，在 $2$ 秒时限内稳定运行。