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