对称
Teleporter Takahashi
题目链接:https://atcoder.jp/contests/abc289/tasks/abc289_f
题意:给出一个平面上的矩形,从给定的起点开始,每次在矩形内选一个整点,并将起点变为此整点的对称点,询问是否能在有限的操作后到达给定的终点,如果可行给出方案.其中所有的数都满足在$(1,1e6)$内.
分析:面对这种整体不好下手的问题可以先考虑简化的情形.在一维的情况下,从起点经过若干次一条线段上整点的对称到达终点.
还是没有思路,先手玩一波.将x按照A对称,得到2A-x.如果再以A为对称中点转回去,显然没有什么作用.试试做一些小的改动,分别以A-1,A+1为对称中点,可以得到x-2,x+2.那么可以得出,如果线段至少含有两个整点,就一定可以将x变为x+2n $(n\in R)$.
那么,如果起点和终点在线段同侧时的差为d,满足d是2的倍数,一定可以经过若干次这样的对称,其实就是d/2次,让起点和终点重合.如果d是奇数,那么一定无法达到目的.如果线段只含有一个整点,那么起点和终点要么一开始就重合,要么以此整点对称,否则一定不行.
在一维进行对称移动时,另一维每次取同样的对称中心,位置就不会改变,所以每一维可以独立处理.最后把每一维的处理结果叠加起来就是答案序列.