P1747 好奇怪的游戏 思考

· · 个人记录

前言

这是我的解法，没有大佬们的方法那么简洁，但用的是简单的，朴素的方法。

理论

我们先设x_1，y_1中大的为a，小的为b。

我们可以发现，每次移动，坐标都会\pm1或者\pm2，但要注意一点，没有(\pm1,\pm1)这样的组合。

然后就可以找到理论最优：从a开始每一次走2步，直至1。此时步数为\lceil\frac{a-1}{2}\rceil，又因为a是整数，即\lfloor\frac{a}{2}\rfloor步。因为 C++ 会自动向下取整，所以更好算一些。

如果要取这种解法，还需要满足一些条件:

  2. 构成(b-1)的步数必须含有2。

特殊点

我们可以发现，首先(1,2)(2,1)(2,2)就得特判。然后，我们 就可以\color{#22AB22}AC了 还要找更多的特殊点。

当b每加2时，我们可以通过+2,-2来凑数，所以只需找到最小的奇数和偶数步即可。

凑数法:(-1,-1,-1)=>(+1,-2,-2)。故步数超过2时都可以用这种方法避免全是1。

当步数为2时，a=4或5，此时b=3。

但由于a=5时由两个2组成，所以可以排除。

故(4,3)(3,4)应特判。

如有遗漏，请尽快提出！

完

注：测试点太水了，只特判三个点确实可以\color{#22AB22}AC