二分交互题总结
简单版
bool query(int x){cout<<x<<endl;cout.flush();string ans;cin>>ans;return (ans==">=");
}
void solve()
{int n;cin>>n;int l=1,r=n;if(n==1)return cout<<"! 1"<<endl,void();if(n==2){if(query(2))return cout<<"! 2"<<endl,void();else return cout<<"! 1"<<endl,void();}int cnt=0;while (l<r){int mid=(l+r+1)>>2;// cout<<l<<' '<<r<<endl;if(query(mid)){l=mid;}else r=mid-1;// cout<<l<<' '<<r<<endl;}cout<<"! "<<l<<endl;
}
进阶
限制四次之内找到 x ′ ∈ [ x 2 , 2 x ] x'\in[{x\over2},2x] x′∈[2x,2x]
思路：
- x越大 范围越大
- 打表 找5e9内 [ x 2 , 2 x ] [{x\over2},2x] [2x,2x]的所有区间 每个区间设置一个固定输出值
- 打完表惊奇地发现区间个数只有16个，四次份 2 4 2^4 24个段，能确定 x ′ x' x′的范围
- 每次回答问的数y是否＞x，0为 y ≤ x y\leq x y≤x
- 设计问下边界，因为越小区间越短越密集越精确
- 最后输出区间中间的数
int lo[17],hi[17];
void solve()
{int n;cin>>n;if(n==1)return cout<<"! 1"<<endl,void();int k=2;lo[1]=1,hi[1]=4;// cout<<lo[1]<<' '<<hi[1]<<endl;while (hi[k-1]<n){lo[k]=hi[k-1]+1;hi[k]=min(lo[k]*4,n);//注意上边界卡在n内 否则会输出超出[1,n]的数// cout<<lo[k]<<' '<<hi[k]<<endl;k++;}int l=1,r=k-1;while (l<r){int mid=(l+r+1)>>1;cout<<"? "<<lo[mid]<<endl;cout.flush();int re;cin>>re;if(re==1){r=mid-1;}else{l=mid;}}cout<<"! "<<min(lo[l]*2,hi[l])<<endl;//一开始输出答案忘了换行 竟然T了
}