[BalticOI 2022 Day1] Art Collection 题解

FFTotoro · 2024-06-22 18:35:16 · 题解

考虑对于每个元素单独计算排名。假设我们现在要求 x 在 P 中的排名（设该排名为 y），可以考虑如下的询问构造：

• R_1=\{x,\ldots\}
• R_2=\{\ldots,x\}

其中两者 \ldots 的部分需要是一样的；设 \ldots 内部的贡献为 \Delta，即与 x 无关的贡献。

根据题意，可以得出 \mathrm{answer}(R_1)=y+\Delta，\mathrm{answer}(R_2)=N-y-1+\Delta，于是 y=\dfrac{\mathrm{answer}(R_1)-\mathrm{answer}(R_2)+N-1}{2}。直接按这种方法对于每个元素构造两个排列可以做到 2N 次询问，可获得 70 分。

考虑压缩询问次数，即考虑合并一些元素的询问：观察到 R_2 为 R_1 向左循环位移一位得到的结果，于是令初始排列为 \{1,2,\ldots,N\}，每次将其向左循环位移一位继续询问，即可依次得出元素 1,2,\ldots,N 的排名。

放代码（代码中的数组均为 0-indexed）：

#include<bits/stdc++.h>
using namespace std;
void answer(vector<int>);
int publish(vector<int>);
void solve(int n){
  vector<int> a(n),r(n);
  for(int i=0;i<n;i++){
    vector<int> v;
    for(int j=i;j<n;j++)
      v.emplace_back(j+1);
    for(int j=0;j<i;j++)
      v.emplace_back(j+1);
    a[i]=publish(v);
  } // 循环位移构造询问
  for(int i=0;i<n;i++)
    r[a[i]-a[(i+1)%n]+n-1>>1]=i+1;
    // 计算排名并存入答案
  answer(r);
}