menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[二分]Codeforces1064E【Dwarves, Hats and Extrasensory Abilities】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论

题目概述

交互题,有 $n$ 个点,你需要指定每个点的坐标 $(x,y)$ ,每次指定之后会告诉你这个点的颜色。你需要确定你的点的坐标使得你给出的点能被直线分成两半,输出这条直线。

解题报告

我是zz吧,我一直在想怎么确定两端的颜色然后二分。看了题解之后发现我为什么要先知道两端颜色呢?直接假装左边什么颜色右边什么颜色就好了……最后那条直线可以选左边最后一个颜色上方到右边第一个颜色下方。

示例程序

因为限制非常紧……所以要先来一次确定左边的颜色,这样要好一些(其实我也不知道哪里好了些)

#include<cstdio>
#include<algorithm>
using namespace std;

int n,L,R;char s[10];

inline int Ask(int x,int y) {printf("%d %d\n",x,y);fflush(stdout);scanf("%s",s);return s[0]=='b';}
int main(){
    scanf("%d",&n);L=0;R=1e9;bool fl=Ask(0,1);
    for (int i=2;i<=n;i++) {int mid=L+(R-L>>1);if (Ask(mid,1)^fl) R=mid; else L=mid;}
    printf("%d %d %d %d\n",L,0,R,2);fflush(stdout);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up