题解

问题分析

这是一个交互式排列恢复问题。我们需要通过查询来还原一个隐藏的排列 $P$，每次查询可以获取一个排列 $V$ 在隐藏排列 $P$ 下的相邻元素绝对差之和。

关键观察

1. 查询性质：query(V) 返回 $\sum_{i=1}^{N-1} |P[V[i]] - P[V[i+1]]|$
2. 循环移位技巧：通过循环移位构造查询序列来获取不同位置的信息
3. 差分约束：相邻位置的差值信息可以转化为对排列值的约束

算法思路

差分系统 + 深度优先搜索：

第一阶段：信息收集

1. 生成随机排列：创建一个随机排列用于查询
2. 循环查询：对每个位置 $i$，构造循环移位序列 $[i, i+1, \dots, n, 1, \dots, i-1]$
3. 计算差值：通过查询结果推导出相邻位置的差值约束

第二阶段：排列重建

1. DFS搜索：从某个起始值开始，深度优先搜索所有满足差值约束的排列
2. 剪枝优化：
   • 值域范围约束：所有值必须在合理范围内
   • 唯一性约束：值不能重复
   • 步数限制：防止搜索过深

第三阶段：答案构造

1. 归一化处理：将找到的排列值调整到 $1$ 到 $n$ 的范围
2. 逆映射：根据初始随机排列进行逆变换得到最终答案

核心代码逻辑

信息收集

rep(i, 1, n) {
    ord.clear();
    rep(j, i, n) ord.eb(j);
    rep(j, 1, i - 1) ord.eb(j);
    D[i] = ask();  // 获取位置i的差值信息
}

DFS搜索

void dfs(int pos, int l, int r, int cur) {
    // 边界检查和剪枝
    if (r - l > n - 1 || vis[cur]) return;
    
    // 终止条件检查
    if (pos == n && abs(a[1] - a[n]) == D[1]) {
        rep(i, 1, n) res[i] = a[i];
        ok = 1;
        return;
    }
    
    // 双向搜索
    vis[cur] = 1;
    if (step <= lim) dfs(pos + 1, l, r, cur + D[pos + 1]);
    if (step <= lim) dfs(pos + 1, l, r, cur - D[pos + 1]);
    vis[cur] = 0;
}

复杂度分析

• 查询次数：$O(N)$ 次查询
• 搜索复杂度：最坏 $O(2^N)$，但通过剪枝在实际中可行
• 空间复杂度：$O(N)$

算法特点

1. 随机化：使用随机排列避免最坏情况
2. 完整性：通过DFS确保找到所有可能的解
3. 高效性：在约束范围内快速收敛

算法标签

• 交互式算法
• 深度优先搜索
• 排列恢复
• 差分约束
• 随机化算法
• 剪枝优化