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

codeforces.com/contest/809/problem/B

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

【Accepted】

 #include <iostream>

 #include <stdio.h>

 #include <cmath>

 #include <vector>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <string>

 #include <bitset>

 #include <ctime>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int n,k;

 bool query(int x,int y)

 {

     if(x<=||y>n)

         return false;

     string res;

     cout<<"1 "<<x<<" "<<y<<endl;

     cin>>res;

     return res=="TAK";

  }

 int get(int l,int r)

 {

     if(l>r)

     {

         return -;

     }

     while(l<r)

     {

         int mid=(l+r)>>;

         if(query(mid,mid+))

         {

             r=mid;

         }

         else

         {

             l=mid+;

         }

     }

     return l;

 }

 int main()

 {

     cin>>n>>k;

     int x,y;

     x=get(,n);

     y=get(,x-);

     if(!query(y,x))

     {

         y=get(x+,n);

     }

     cout<<"2 "<<x<<" "<<y<<endl;

     return ;

 }

注意：

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

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

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

巴特西

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

最新文章

热门文章