题解：P17854 [LBA-OI R6 B] 凌云沐雨

Monarch_Richest · 2026-11-08 21:47:34 · 题解

题意

有一个未知的长度为 n 的排列 A。

每次询问可以给出一个下标的有序集合 P=(p_1,p_2,p_3,\dots,p_m)，交互库会取出 A_{p_1},A_{p_2},A_{p_3},\dots,A_{p_m}，将它们离散化成一个长度为 m 的排列，然后返回这个排列的置换环个数。

我们需要在不超过 n-1 次询问内确定整个排列 A。

思路

设：我们已经知道了一些下标 q_1,q_2,q_3,\dots,q_k，其满足 A_{q_1}<A_{q_2}<A_{q_3}<\dots<A_{q_m}。

现在需要确定新下标为 x 的 A_x 会插入到 P=(q_1,q_2,q_3,\dots,q_k,x)，即：将已知的 k 个下标按对应的值升序，再加入新下标 x； 设 A_x 是当前 P 中第 r 的小的数。 则，离散化后的 P：

置换环数量：(r-1)+1=r。

• 从 r 开始跳到原下标 r 的 r+1，然后 r+1 又跳到原下标 r+1 的 r+2，……，依次类推，直到 k+1 跳到 r 形成一个大环；

所以，交互库返回的数 c 就是 A_x 在这 k+1 个数中第几大。

算法

维护一个有序下标序列 ans（初始为 \{1\}，表示目前 A_1 最小）。

然后依次加入下标 x=2,3,\dots,n：

• 询问集合 ans 加 x；
• 插入 x 到 ans 下标为 c 的位置；

因此，处理完后 ans 为按 A 值从小到大排列的下标序列。

所以 A_{ans_i}=i+1（0 \le i < n）。

:::info[正确性证明]

• 假设：处理完前 k 个下标，则 ans 里一定满足：A_{ans_0}<A_{ans_1}<\dots<A_{ans_k}；
• 步骤：加入新下标 x 时，序列为 ans_0,ans_1,\dots,ans_k，前 k 个值严格递增。设 A_x 在其中的排名为 r，则由核心观察，返回的环数 c=r。把 x 插入到 ans 的第 r 个位置后，新的序列仍然按 A 值升序排列。归纳成立。 处理完全部 n 个下标后，ord 是按值升序排列的下标序列，因此，排列被唯一确定。 ::: 询问次数 n-1，足以通过此题。 :::success[AC code]

  #include<bits/stdc++.h>
  typedef long long ll;
  using namespace std;
  const int MAXN=1005;
  int n,k,c;
  int a[MAXN];
  vector<int>p;
  int main()
  {
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>k;
    p.emplace_back(1);
    for(int i=2;i<=n;i++)
    {
        cout<<"\n? "<<i;
        for(int&x:p)
            cout<<' '<<x;
        cout<<' '<<i<<endl;
        cin>>c;
        p.insert(p.begin()+(c-1),i);
    }
    for(int i=0;i<n;i++)
        a[p[i]]=i+1;
    cout<<"\n!";
    for(int i=1;i<=n;i++)
        cout<<' '<<a[i];
    cout<<'\n';
    return 0;
  }

:::