【二分+交互】codeforces B. Glad to see you!

只需要找到2个被选中的，首先，注意到将区间二等分时左侧区间为[l,mid],右侧区间为[mid+1,r]，dui（mid,mid+1)进行询问，就可以得到这两个区间中哪个最近的离边界最近（如果不存在，距离可理解为无穷远），这样就确保了某一个区间必定存在至少一个被选中的，重复此过程，就一定能找到一个被选中的，设该位置为x。k>=2 所以此位置左侧、右侧中至少有一个有。先对左侧重复该过程，对结果进行和x的询问。因为如果那个位置是被选定的，则结果一定为0<=0，如果符合，直接输出，不然一定在右侧区域，对右侧区域重复该过程即可。

【Accepted】

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cmath>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <queue>
 9 #include <deque>
10 #include <stack>
11 #include <string>
12 #include <bitset>
13 #include <ctime>
14 #include<algorithm>
15 #include<cstring>
16 using namespace std;
17 typedef long long ll;
18 const int maxn=1e5+5;
19 int n,k;
20 bool query(int x,int y)
21 {
22     if(x<=0||y>n)
23         return false;
24     string res;
25     cout<<"1 "<<x<<" "<<y<<endl;
26     cin>>res;
27     return res=="TAK";
28  } 
29 int get(int l,int r)
30 {
31     if(l>r)
32     {
33         return -1;
34     }
35     while(l<r)
36     {
37         int mid=(l+r)>>1;
38         if(query(mid,mid+1))
39         {
40             r=mid;
41         }
42         else
43         {
44             l=mid+1;
45         }
46     }
47     return l;
48 }
49 int main()
50 {
51     
52     cin>>n>>k;
53     int x,y;
54     x=get(1,n);
55     y=get(1,x-1);
56     if(!query(y,x))
57     {
58         y=get(x+1,n);
59     }
60     cout<<"2 "<<x<<" "<<y<<endl; 
61     return 0;
62 }

View Code

注意：

get函数和query函数没有if判断，就会出错，比如x为1

而且在左侧找到了y之后要判断是否符合。

不要用while(~scanf())，只读单组；print之后fflush(stdout)否则IDLENESS LIMIT EXCEEDED