[Div2]「CodePlus 2018 4 月赛」喵呜

[Div2]「CodePlus 2018 4 月赛」喵呜
a=b=1
因为每次移动时,小猫的两个坐标奇偶性同时改变,所以不难发现此时小猫能从(x,y)到达(p,q)的条件是|x-p||y-q|的奇偶性相同,只要发现了这个性质,也容易推导出小
猫从(x,y)到达(p,q)的最少步数为min(|x-p|,|y-q|)。这部分数据主要给正解写挂选
b=1
容易知道小猫能够到达的树的编号一定能写作x+ka的形式,所以我们把符合这种形式
的编号的树单独拿出来,就把问题完全转化为了 的情形,用上面相同的方法即可通
过这部分数据。

进一步分析b=1时的解法,我们可以得出结论,小猫能从(x,y)到达(p,q)的条件为:
1. a能整除|x-p|b能整除|y-q|
2. \frac{|x-p|}{a}=\frac{|y-q|}{b}
同理,所需的最少步数为min(\frac{|x-p|}{a},\frac{|y-q|}{b}),故最终在O(1)的时间复杂度内即可通过
本题。

发表评论

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