目录
显示
题目链接
题解
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);
}