目录
codeforces1064E Dwarves, Hats and Extrasensory Abilities题意：题解：Code:
codeforces1064E Dwarves, Hats and Extrasensory Abilities
题目传送们
题意：
一道交互题，在一个[0,1e9][0,1e9]的二维空间中，你总共需要选出\(N\)个点，每次向交互库询问一个点\((x,y)\)，然后交互库返回这个点的颜色，最终你需要划出一条直线将空间分成两个平面，使得每一个平面中只有一种颜色的点。
题解：
首先注意到如果我们随机取点然后询问的话，那么很容易就会出现无解的情况，所以我们询问一定是要按照某种策略来询问。我们最终的目标是把白色和黑色的点分开来，所以我们需要尽量的把白色的点和黑色的点分别聚在一起。所以我们就有了一个算法: 先询问点(0,0)，记下这个点的颜色\(C\)，然后在一条直线上二分着询问:每次询问一个点\((mid,0)\)，如果这个点的颜色和\(C\)相同，那么我们就在[mid+1,r]之中二分，反之则在[l,mid-1]中二分。原因是如果询问的点与\(C\)相同，那么如果我们下一次继续在[l,mid-1]中二分，如果返回的值为另一重颜色，那么就会破坏我们设定的同一颜色都聚在一块的设定。如果觉得不稳的话，就分别在垂直于\(X\)轴和垂直于\(Y\)的两条直线上二分，这样点是绝对够的。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
int n;
/*==================Define Area================*/
int Ask(int x,int y) {
printf("%d %d\n",x,y);
fflush(stdout);
char res[15];
scanf("%s",res);
if(res[0]=='b') return 1;
else return 0;
}
void Answer(int x,int y,int xx,int yy) {
printf("%d %d %d %d\n",x,y,xx,yy);
return ;
}
int main() {
scanf("%d",&n);
if(n==1) {
Ask(0,0);
Answer(1,0,0,1);
return 0;
}
else {
int Right=0,Up=0;
int nowx=0,nowy=0;
int c=n/2;
int l=0,r=1e9;
int C=Ask(nowx,nowy);
for(int i=1;i<=c;i++) {
int mid=(l+r)>>1;
int col=Ask(nowx,mid);
if(col==C) {
l=mid+1;
Right=max(Right,mid);
}
else r=mid-1;
}
l=0,r=1e9;
for(int i=1;i<=n-c-1;i++) {
int mid=(l+r)>>1;
int col=Ask(mid,nowy);
if(col==C) {
l=mid+1;
Up=max(Up,mid);
}
else r=mid-1;
}
Answer(0,Right+1,Up+1,0);
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9794568.html
相关资源：JAVA上百实例源码以及开源项目
