题解：P13761 Chess

· · 题解

题意

在一个 n 行 m 列的棋盘上有一个象棋中的象在 (1,1) 的位置，每一步可以按规则移动或不移动（即原题面中移动己方的帅）。另有一个对方的将在 (n,m) 的位置，移动顺序为 (n,m)\to (n-1,m)\to(n-1,m-1)\to(n,m-1) 循环。请输出象吃掉将的最小步数，或判断无解，此时输出 -1。

解法

由于象的移动规则是横向移动两格且纵向移动两格，所以象的横纵坐标一定是奇数，且对 4 取模的值相等。判断将所在的四个位置是否满足条件，由于将的 4 个位置中只有一个横纵坐标均为奇数，故只有这一个位置是象可能可达的，对其判断第二个条件（模 4 相等）。

到这里，无解情况和最终象走到的位置已经判出来了，直接输出步数即可。计算步数非常简单，答案为 \lfloor\dfrac{\max(n,m)}{2}\rfloor，手推可以很容易得出。不需要判断塞象眼的情况，棋盘上没有棋子能够塞象眼且影响最终结果。这一点也易证。

注意：将的位置是变化的，即我们确定的将的位置每 \mathbf 4 轮移动才会出现一次。需要对答案加上一个小于 4 的数以保证其对 4 取模的正确性。

感谢 @Fine_Dust_Z 大佬指出需要开 unsigned long long。

Upd：不会爆 long long，因为之前代码的 13 行写出负数了，开 unsigned long long 就玄学通过了。

代码

所以当开了 long long WA 时，就试试开 unsigned long long，也许就过了呢。

不过下面是只开 long long 的正解。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, mod4;
signed main(){
    cin >> n >> m;
    if ( (n & 1) &&  (m & 1)) mod4 = 1;
    if (!(n & 1) &&  (m & 1)) mod4 = 2, n --;
    if (!(n & 1) && !(m & 1)) mod4 = 3, n --, m --;
    if ( (n & 1) && !(m & 1)) mod4 = 0, m --;
    if (n % 4 != m % 4){ cout << -1; return 0; }
    int ans = max(n, m) >> 1;
    ans += (mod4 + 4 - (ans % 4)) % 4; // 这里的 ans 要对 4 取模防出现负数
    cout << ans;
    return 0;
}

最终 AC 记录。