乔拓云智能建站平台,上海品牌全案设计公司,网站建设伍金手指下拉8,网站怎么做可以再上面输入文字题目#xff1a;戳这里 题意#xff1a;一个点在[1,n]以内#xff0c;我们可以进行4500次查询#xff0c;每次查询之后#xff0c;该点会向左或向右移动0~k步#xff0c;请在4500次查询以内找到该点。 解题思路#xff1a;一边二分#xff0c;一边随机。 交互题似乎有好…题目戳这里 题意一个点在[1,n]以内我们可以进行4500次查询每次查询之后该点会向左或向右移动0~k步请在4500次查询以内找到该点。 解题思路一边二分一边随机。 交互题似乎有好多是二分上次交互题的二分调了好久这次也是。我出数据水平又很低所以至今不知道哪些数据可以卡哪些二分的写法只能改一次交一次。。。 1 #include cstdio2 #include cstring3 #include algorithm4 #include string5 #include vector6 #include map7 #include cmath8 #include iostream9 #include random
10 #include ctime
11 using namespace std;
12 typedef long long ll;
13 const int maxn 1e6 10;
14 char ans[11];
15 bool ask(ll l, ll r)
16 {
17 //printf($$$$);
18 printf(%lld %lld\n, l, r);
19 fflush(stdout);
20 scanf(%s, ans);
21 if(ans[0] Y)
22 {
23 if(l r) exit(0);
24 else return 1;
25 }
26 else return 0;
27 }
28 int na[maxn];
29 int main()
30 {
31 ll n, k;
32 srand(time(NULL));
33 scanf(%lld %lld, n, k);
34 ll l 1, r n;
35 while(l r)
36 {
37 ll mid l (r - l) / 2;
38 if(ask(l, mid))
39 {
40 r mid;//注意这点我的理解是mid可能就是我们要找的点如果用常规写法rmid-1会把这个点跳过去
41 //但我试了几个样例发现在区间不断变化且有随机数的情况下及时rmid-1也能找到答案。。
42 }
43 else
44 {
45 l mid 1;
46 }
47 l max(1ll, l - k);
48 r min(n, r k);
49 mid l rand()%(r - l 1);
50 ask(mid, mid);
51 l max(1ll, l - k);
52 r min(n, r k);
53 }
54 return 0;
55 } View Code 转载于:https://www.cnblogs.com/zmin/p/9606685.html
