「PA 2019」Sonda 题解

题目分析

问题形式化

给定无向连通图 $G = (V, E)$，其中：

• $|V| = n$，$3 \leq n \leq 400$
• $E$ 未知但保证连通性
• 初始状态：探测器位于 $v_1 = 1$

定义状态转移函数：

$$\text{MoveProbe}(v) = \begin{cases} 1 & \text{如果 } (v_{\text{current}}, v) \in E \text{ 且移动次数为偶数} \\ 0 & \text{否则} \end{cases} $$

目标：找到访问序列 $P = (p_1, p_2, \ldots, p_n)$ 使得：

1. $\{p_1, p_2, \ldots, p_n\} = V$（覆盖所有节点）
2. 对于每个 $p_i$，在访问时调用 $\text{Examine}()$
3. 总移动次数 $\leq 10^6$

核心算法

DFS 遍历策略

设：

• $S \subseteq V$：已访问节点集合
• $A[u][v]$：已知的邻接关系（$1$ 有边，$0$ 无边，$-1$ 未知）
• $\text{pos} \in V$：当前位置

算法框架：

$$\begin{aligned} &\text{DFS}(u): \\ &\quad S \leftarrow S \cup \{u\} \\ &\quad \text{Examine}() \\ &\quad \text{for } v = 1 \text{ to } n: \\ &\quad\quad \text{if } v \neq u \text{ and } v \notin S \text{ and } A[u][v] \neq 0: \\ &\quad\quad\quad \text{if } \text{MoveProbe}(v) \in \{0,1\}: \\ &\quad\quad\quad\quad A[u][v] \leftarrow 1, \quad A[v][u] \leftarrow 1 \\ &\quad\quad\quad\quad \text{DFS}(v) \\ &\quad\quad\quad\quad \text{MoveProbe}(u) \quad \text{（回溯）} \\ &\quad\quad\quad \text{else}: \\ &\quad\quad\quad\quad A[u][v] \leftarrow 0, \quad A[v][u] \leftarrow 0 \end{aligned} $$

复杂度分析

操作次数上界：

• 每对节点最多尝试一次移动：$\binom{n}{2} = \frac{n(n-1)}{2}$
• DFS 回溯移动：最多 $2(n-1)$ 次
• 总操作数：$T(n) \leq \frac{n(n-1)}{2} + 2(n-1)$

代入 $n = 400$：

$$T(400) \leq \frac{400 \times 399}{2} + 2 \times 399 = 79,800 + 798 = 80,598 \ll 10^6 $$

空间复杂度：$O(n^2)$ 存储邻接矩阵。

子任务优化

子任务 1：完全二分图

设二分图划分为 $V = A \cup B$，$|A| = a$，$|B| = b$，$a + b = n$。

性质：

• $\forall u \in A, v \in B: (u,v) \in E$
• $\forall u,v \in A \text{ 或 } u,v \in B: (u,v) \notin E$

优化策略： 一旦确定某个节点属于 $A$ 或 $B$，可以推断所有跨划分的边存在。

子任务 3：2-正则图

图结构：由若干个不相交的环组成。

度数约束：

$$\forall v \in V: \deg(v) = 2$$

探索策略：从任意节点出发，沿着未知边移动，必然形成环状路径。

移动奇偶性处理

设 $m_{\text{even}}$ 为偶数次移动的集合，$m_{\text{odd}}$ 为奇数次移动的集合。

关键观察：虽然 $\text{MoveProbe}$ 的返回值依赖于：

$$r(t) = \mathbb{I}[\text{移动成功}] \cdot \mathbb{I}[t \equiv 0 \pmod{2}] $$

其中 $t$ 是成功移动次数，但移动本身的可行性只取决于边是否存在。

处理技巧：如果需要特定的返回值，可以通过额外的来回移动调整奇偶性：

$$\text{AdjustParity}(u,v): \text{MoveProbe}(v) \rightarrow \text{MoveProbe}(u) \rightarrow \text{MoveProbe}(v) $$

这样在保持位置不变的情况下改变奇偶性。

正确性证明

定理：上述 DFS 算法能够访问所有节点恰好一次。

证明：

1. 连通性保证：由于 $G$ 连通，从节点 $1$ 出发可以到达所有节点
2. 完整性：算法尝试所有可能的移动，不会遗漏可达节点
3. 无重复访问：$S$ 集合确保每个节点只访问一次
4. 终止性：有限图确保算法在有限步骤内结束

边界情况处理：

• 自环：通过 $v \neq u$ 检查排除
• 重复标记：通过 $S$ 集合避免
• 移动失败：通过 $A$ 矩阵记录，避免重复尝试

该算法在给定约束下能够高效可靠地完成图探索任务。