题意:
(无输入,纯输出题)
一个城市用1000列2行的格子表示,一个小偷藏在城市的某一处。
在每一小时的开始,
在(X, Y)位置的小偷可以移动到
(X - 1, Y), (X + 1, Y),(X - 1, Y - 1), (X - 1, Y + 1), (X + 1, Y - 1), (X + 1, Y + 1)中的任意一个位置。
在每一小时中,警察可以控制搜索两个格子,如果小偷藏在这个格子就会被发现。
请输出一种方案,
使得在2015小时内,对于小偷的初始位置和移动方法的所有可能情况都能保证抓到小偷。
题解:
绝对是签到题…几行代码就没了。
观察小偷的移动方法,发现不能垂直移动。
也就是说,每次移动时X坐标一定会变动1,Y坐标可能变也可能不变。
通过这个很容易发现,如果警察搜索的两个区域的X坐标不同,也就是说两个区域的上或下都有躲避处时,
如果小偷将被发现,那么小偷经过另一种移动序列使其中某一次Y坐标的是否变化反转时,
(这样会让这个时刻小偷的Y坐标变化)
小偷就不会被发现了。所以可以确定搜索的一定是同一列的两个格子。
所以问题转化为一维,于是可以奇偶分析。
考虑从左到右扫一次的方法,只有一种情况会让小偷躲过,
就是警察搜索x,小偷在x+1,下一小时小偷跑到x,警察搜索x+1…
这种情况如果发生,则每一小时内警察和小偷的位置的奇偶性不同。
也就是说第1小时小偷的位置是偶数。
那么我们可以做两次这个过程,要使得两次中某一次的第一小时中小偷在奇数位置。
显然只需要第一次过程进行奇数次搜索就好了,因为题目要求是2015,所以多一次少一次都可以。
(少一次可以是因为1000是偶数,小偷在奇数位置的情况肯定不会发生在1000这个位置)
(因为题目太水就不放代码了……)