题目大意

给定 $n$ 根绳子，每根绳子长度为 $s_i$，上面有 $m_i$ 个节点，第 $j$ 个节点距离绳子左端点为 $p_{i,j}$。要求将这些绳子从左到右排列成一个序列，使得连接后所有相邻节点之间的距离相等。求一个可行排列或判断无解。

解题思路

关键观察

1. 间距一致性：设最终相邻节点间的固定距离为 $L$，则所有节点在连接后的整体序列中必须满足等差数列关系。

2. 绳子端点特征：

   • 对于第 $i$ 根绳子，定义：
     • 左端特征：li[i] = p[i][0]（第一个节点到左端的距离）
     • 右端特征：ri[i] = s_i - p[i][m_i-1]（最后一个节点到右端的距离）
   • 当绳子 $i$ 和绳子 $j$ 相连时，需要满足：ri[i] + li[j] = L

3. 图论建模：

   • 将每根绳子视为图中的节点
   • 从绳子 $i$ 到绳子 $j$ 连边，当且仅当 ri[i] + li[j] = L
   • 问题转化为在图中寻找一条哈密顿路径（经过每个节点恰好一次）

算法框架

1. 特殊情况处理：

   • 当 $n = 1$ 时，直接输出该绳子
   • 当所有绳子的内部节点间距一致时，$L$ 必须等于该固定间距

2. 确定间距 $L$：

   • 小数据 ($n \leq 100$)：枚举所有可能的 li[i] + ri[j] 作为 $L$
   • 大数据：统计出现频率较高的右端特征，尝试与对应的左端特征组合

3. 检查可行性：

   • 对于候选的 $L$，检查度数约束：
     • 对于特征值 $x$，设 ma[x] 为左端特征为 $x$ 的绳子数量
     • 设 mb[x] 为右端特征为 $x$ 的绳子数量
     • 需要满足：对于所有 $x$，|ma[x] - mb[L-x]| ≤ 1
   • 确定路径的起点 $S$ 和终点 $T$：
     • 起点：左端特征出现次数比对应右端特征多1的绳子
     • 终点：右端特征出现次数比对应左端特征多1的绳子

4. 构造路径：

   • 使用 DFS 或 Hierholzer 算法在特征匹配图中寻找欧拉路径
   • 验证路径是否包含所有绳子

复杂度分析

• 时间复杂度：$O(n \log n + \sum m_i)$，主要来自排序和图的遍历
• 空间复杂度：$O(n)$，用于存储各种映射和邻接表

代码实现要点

1. 特征提取：快速计算每根绳子的左右端特征
2. 度数统计：使用 unordered_map 统计各特征的出现次数
3. 路径搜索：基于栈的 DFS 实现路径构造
4. 边界处理：仔细处理 $n=1$、无解、唯一解等情况

总结

本题的核心在于将几何约束转化为图论问题，通过特征匹配和度数分析来寻找可行解。算法结合了数学观察、图论建模和启发式搜索，是一道综合性较强的题目。