[CF1153E]Serval and Snake(二分)

题目链接

题解

人生第一道交互题,感觉很神奇(还好并不难)
考虑以下情况:

  1. 如果我们没有框中头尾,势必有一条“进入”矩形的边,就有一条“出去”的边。
  2. 如果我们只框中头或尾,肯定少一条“进入”或“出去”的边。
  3. 如果我们同时框中了头尾,肯定少两条“进入”或“出去”的边。

综上,当ask的答案为奇数时,我们框中了头或尾,为偶数时可能同时框中,可能同时没框中。

可以先确定头尾是否在同一列

  1. 不在同一列,分别对它们所在列二分,找到对应的点。
  2. 在同一列,再二分行数,找到对应的点。

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注