今天开始做IOI的学习笔记, 就从我出生的年份开始吧
IOI 2007 Aliens:
给你三个整数 N, X, Y 表示网格有N * N大， 而 （X，Y）是黑色的图
那个图是这样的：
#.#.# .#.#. #.#.# .#.#. #.#.#
#表示黑色 .表示白色
而整个N*N的网格只有一个这样的图形, 每个箱子有一个偶数 M 为长度和宽度
询问: 问(x,y) 是不是黑色的
300次询问内寻找到中间点
很容易看出来是二分吧？ （一看题目就感觉到了）
先考虑往右边边走：一开始为(x,y)
如果说现在的步数为 L, 那么如果下一个 2*L不是黑色的了就代表说我们的边界点必须在[L,2*L）
那么就代表我们可以倍增法找到第一个 L是黑色 2*L是白色的
为什么我们可以保证这样不会询问到下一个格子呢
如果说 x+L 是黑的，代表（x+L) 还是在格子里, 证明 L<M, 同时去下一个格子最少需要 M+1，因此 x+2*L不可能到达下一个格子
OK, 所以我们找出来我们的四个边界点了
因此我们的四个角落以及中间点也找出来了
接下来就询问四个方向有多少个格子
然后做一点暴力。 答案就出来了。
需要注意的东西：
1. examine必须要写到下一行 & fflush(stdout)
2. 如果我现在x+1就是白的了要特判
评价： erm 难度适中但是打出来代码很幸苦
具体代码的submission:
https://oj.uz/submission/867633
抱歉没有注释但是我觉得我的代码不会丑， 应该能读懂
标签：#.#.#,黑色,Aliens,边界点,2007,IOI From： https://www.cnblogs.com/yonglicp/p/17800982.html