CodeForces - 1370F2 The Hidden Pair (Hard Version)(交互题+二分)

题目链接：点击查看

题目大意：给出一棵无向无根树，事先确定好了两个点 s 和 t ，现在需要通过询问找到这两个点

每次询问可以给出一个点集，系统会返回点集中距离点 s 和点 t 距离之和最小的那个点以及其距离，如果有多个符合条件的点，会返回任意一个，比如询问了点集 A = { s1 , s2 , ... , sk } ，则系统会返回一个点 v ∈ A 并且 dist( s , v ) + dist( t , v ) 最小

简单版本的是可以询问 14 次，困难版本的是只能询问 11 次

题目分析：14 和 11 次对应着数据范围 1000 ，应该是 logn 的算法，所以我们应该尽量往上面靠拢

首先因为无从下手，所以可以先问一遍全部的点，获得到一个点 rt ，且距离之和为 len，画画图应该不难看出，点 rt 满足的一个性质是，一定位于点 s 到点 v 的这条路径上

下面的转换可能比较难想，但是如果想到了的话剩下的就比较简单了

我们可以以点 rt 点为根，遍历一遍整棵树后跑出每个点的深度，此时对于每个点的深度以及 dist( s , v ) + dist( t , v )，可以看出这两个值之间满足着单调性，这样我们就可以在深度上二分找到：距离之和等于 len 的最大深度的那个点，这个点就是 s 或者 t 中的一个点，再用找到的这个点建树，询问深度为 len 的那一层的所有点，得到的答案就是另外一个点了

如果初始时设置 l = 1 , r = n ，那么 F1 就这样解决了，主要是该如何解决 F2？

很显然，询问全部的 n 个点，和知道其中一个点后再通过一次操作得到另外一个点，这两次操作是无可避免的，优化点只能出自于二分上面 ，对于二分，我们可以做的优化就是缩小初始的范围了

因为初始时找到的 rt 一定是位于 s 到 t 的路径上的，又因为我们是要借助二分寻找距离之和等于 len 的最大深度，那么当这个 rt 在 s 到 t 这条路径的最中间时，左端点最小，取到了  的位置，相应的，我们如果假设 rt 这个点初始时就是 s 点或者 t 点的话，那么右端点最多也就是 len 了，所以右端点我们设置为 min( len , max_deep ) 就好了，max_deep 是建树后的最大深度

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;int n,max_deep;vector<int>node[N],deep[N];pair<int,int> query(int dep) {printf("? %d",deep[dep].size());for(auto v:deep[dep])printf(" %d",v);puts("");fflush(stdout);int rt,len;scanf("%d%d",&rt,&len);return make_pair(rt,len); }void dfs(int u,int fa,int dep) {max_deep=max(max_deep,dep);deep[dep].push_back(u);for(auto v:node[u]){if(v==fa)continue;dfs(v,u,dep+1);} }void build(int rt) {max_deep=0;for(int i=0;i<=n;i++)deep[i].clear();dfs(rt,-1,0); }pair<int,int> get_root() {printf("? %d",n);for(int i=1;i<=n;i++)printf(" %d",i);puts("");fflush(stdout);int rt,len;scanf("%d%d",&rt,&len);return make_pair(rt,len); }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d",&n);for(int i=1;i<=n;i++)node[i].clear();for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}pair<int,int>temp=get_root();int rt=temp.first,len=temp.second;build(rt);int l=(len+1)/2,r=min(max_deep,len),s;while(l<=r){int mid=l+r>>1;temp=query(mid);int p=temp.first,d=temp.second;if(d==len){s=p;l=mid+1;}elser=mid-1;}build(s);int t=query(len).first;printf("! %d %d\n",s,t);fflush(stdout);scanf("%*s");}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1370F2 The Hidden Pair (Hard Version)(交互题+二分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。