[loj 2841]「JOISC 2018 Day 4」图书馆

题目链接

https://loj.ac/problem/2841

题解

Subtask 1

我们一次只取两本书。

显然,当这两本书相邻的时候,只需要取一次,否则需要取两次。

根据这一性质,在 \(O(n^2)\) 的时间内枚举所有数对,即可还原数列。

期望得分:19 pts。

Subtask 2

注意到如果我们对一个集合 \(S\) 进行询问,则返回的次数等于 \(S\) 的大小,减去其中相邻的图书对数。

我们记 \(adj(S)\) 表示 \(S\) 中相邻的图书对数,从而有 \(adj(S)=|S|-query(S)\)。

进一步,我们选取一本不在 \(S\) 中的图书 \(x\),根据上式,我们可以得到,\(adj(S \cup x)-adj(S)=adj(x)\)。

利用这个性质,我们可以想到一种二分的做法:首先我们用暴力的方式找到最左端的书,然后利用上面的性质,在候选集合中二分,从而找到每本书相邻的书。

最终询问次数为 \(O(n+2n \log n)\),期望得分:100 pts。

#include "library.h"
#include <iostream>
using namespace std;
vector<int> q,ord,ans;
int dfs(int N,int x,int l,int r)
{
 if(l==r)return ord[l];
 int mid=(l+r)>>1;
 for(int i=0;i<N;i++)
  q[i]=0;
 for(int i=l;i<=mid;i++)
  q[ord[i]]=1;
 int res1=(mid-l+1)-Query(q);
 q[x]=1;
 int res2=(mid-l+2)-Query(q);
 if(res2>res1)return dfs(N,x,l,mid);
 else return dfs(N,x,mid+1,r);
}
void Solve(int N)
{
 for(int i=0;i<N;i++)
 {
  q.push_back(1);
  ord.push_back(i);
 }
 if(N==1)
 {
  ans.push_back(1);
  Answer(ans);
  return;
 }
 for(int i=0;i<N;i++)
 {
  q[i]=0;
  int res=Query(q);
  if(res==1)
  {
   ans.push_back(i);
   ord.erase(lower_bound(ord.begin(),ord.end(),i));
   break;
  }
  q[i]=1;
 }
 for(int i=1;i<N;i++)
 {
  int cur=dfs(N,ans[i-1],0,N-i-1);
  ans.push_back(cur);
  ord.erase(lower_bound(ord.begin(),ord.end(),cur));
 }
 for(int i=0;i<N;i++)
  ans[i]++;
 Answer(ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据