题目来源:codeforces1039B Subway Pursuit

题目大意:

在1到n里有一个运动的点,要求找到这个点,每次可以查询一个区间内有没有这个点,每次这个点往左或者往右移动1到k个位置,要求要在4500次查询内找到这个点的位置

输入格式:

一行两个整数n,k

输出格式:

每行输出两个整数l,r表示查询区间

表示蒟蒻一直不知道交互题怎么做......而且看到原题的超长英文内心也是懵逼的......真的是什么都不会......

最后终于会做了!(假的,其实是抄了题解啊)所以就特来写一篇博客记录一下。

对于这个题呢,其实官方tutorial是这样说的:

Notice that we can make segment in which we are located small enough using binary search. Let [l;r] be the last segment about which we knew for sure that train is in it (at the beginning it's [1;n]). Let m=l+r2. Let's ask about segment [l;m]. If we receive answer «YES», after this query train for sure will be in segment [l−k;m+k], otherwise in [m−k;r+k]. So, after each query length of segment is divided by 2 and increased by 2k. After segment length becomes irreducible (4k), let's ask about some random station in this segment. If we guessed right, let's finish the program, otherwise make the binary search again.

To get the OK let's make one more observation: for all binary searches except the first one initial segment can be made [l−k;r+k]

instead of [1;n].

也就是二分的意思。

因为每次一个区间分成两半,每一半的两端都会因为k的存在,而两端分别增加k个单位长度,也就是每一次增加4k个单位长度。

那么在区间长度大于4k的时候我们显然可以二分处理,但是之后在区间长度小于等于4k的时候可以考虑使用随机化进行询问。

题目要求我们在l==r且回答询问为True的时候结束程序,所以记得要及时判断is_solved变量并及时return掉。

#include<iostream>
#include<vector>
#include<random>
#include<ctime>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
bool is_solved = false;
bool Request(long long a, long long b){
cout<<a<<' '<<b<<endl;
string answer;
cin>>answer;
if(answer=="Yes"&&a==b)
is_solved=true;
return answer=="Yes";
}
void Solve(long long n,int k){
long long min_x=1,max_x=n;
while (!is_solved){
if (max_x-min_x<=k*4){
if (k==0){
Request(min_x,max_x);
return;
}
long long a=max_x-min_x+1;
long long b=min_x+(((long long)rand()*rand())%a+a)%a;
Request(b,b);
if (is_solved)
return;
min_x=max(min_x-k,(long long)1);
max_x=min(max_x+k,n);
}
long long middle_x=(min_x + max_x)/2;
if (Request(min_x,middle_x)){
min_x=max((long long)1,min_x-k);
max_x=min(middle_x + k,n);
}
else{
min_x=max((long long)1,middle_x+1-k);
max_x=min(n,max_x+k);
}
}
}
int main(){
long long n;
int k;
cin >>n>>k;
Solve(n,k);
}

最新文章

  1. C#定时执行
  2. UIScrollView和delegate的通信
  3. api接口验证shal()
  4. 让我欲罢不能的node.js
  5. 网络异步编程(C#)团购课
  6. Ubuntu下设置Tomcat成为服务(开机启动)
  7. POJ 3687 Labeling Balls【拓扑排序 优先队列】
  8. 一个解析cgi参数的SHELL脚本
  9. 除法(Division ,UVA 725)-ACM集训
  10. Java系统变量设置方式
  11. iOS中的界面多选功能--(UICollectionView)
  12. 关于rem自适应的一点研究
  13. 关于json_encode转数组为json对象时里有数组格式数据的问题
  14. 嵌入式程序设计中C/C++代码的优化
  15. ZABBIX 3.4 监控服务器TCP连接状态(六)
  16. 「About Blockchain(一)」达沃斯年会上的区块链
  17. linux tomcat 绑定域名
  18. Volley overview
  19. 在linux下使用sqlcmd
  20. vue中使用better-scroll实现滑动效果

热门文章

  1. 强大的vim配置文件,让编程更随意 (转载)
  2. DM368 NAND Flash启动
  3. Lucene的查询及高级内容
  4. 利用fetch进行POST传参
  5. 解决:EXCEL复制粘贴,精度丢失
  6. Unity3d收藏链接/ 小马哥视频
  7. 磁盘io测试工具
  8. [SoapUI] UrlEncode编码/UrlDecode解码网站
  9. efcore dbfirst 通过数据库表反向生成model
  10. mariadb主从备份