找规律 发表于 2018-10-15 分类于 ACM , 学习笔记 , 思维 阅读次数: 4 本文字数: 538 阅读时长 ≈ 1 分钟 nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 无限大的棋盘有一只走‘日’的马呆在0,0处,也是坐标原点,(存在四个象限),给你(x,y)问你要至少跳多少步才能跳过去 不妨设x>y x≤2y,可以证明当x和y足够大的时候 (x+y)mod3=0时,我们只需要x+y3步,这些步数由两种跳跃组成,他们分别是(1,2)和(2,1) (x+y)mod3=1时,我们选择(1,-2)或者(-2,1)来跳跃,跳跃之后(x+y)mod3=0所以一共需要x+y3+1步 同理(x+y)mod3=2时一共需要x+y3+2步 综合为需要x+y3+((x+y)mod3)步 同样分析出x>2y在x和y足够大的时候,需要y+x−2y4×2+(x−2y)%4步 那么这个足够大是多少呢?是x>3&&y>3