题解：P16911 [JLCPC 2026] Manhattan Cycle

__orange__ · 2026-07-23 12:56:23 · 题解

题解

题意简述

给定正整数 n,K，平面上特殊点定义为横、纵坐标均属于 [0,n] 的整点。两点之间允许跳跃的充要条件是两点曼哈顿距离恰好等于 K。

现在需要判断：是否存在一条路径，从某个特殊点出发，经过奇数次跳跃后回到起点。

• 若存在合法路径，输出所有可行方案里跳跃次数的最小值；
• 若不存在任何合法路径，输出 -1。

思路分析

1. 奇偶筛选 奇数步回到起点，要求 K 必须是偶数。K 为奇数直接无解输出 -1。

2. 最小奇数步数判断 最小可行奇数步数为 3。能构造3步回路的条件是 3K \le 4n。 满足条件输出 3，不满足则无解输出 -1。

完整判定规则

1. 如果 K 是奇数：输出 -1；
2. 如果 K 是偶数：
   • 若 3 \times K \le 4 \times n，输出 3；
   • 若 3 \times K > 4 \times n，输出 -1。

C++ 代码

#include<iostream>
using namespace std;
#define ll long long
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--)
    {
        ll n, k; cin >> n >> k;
        if (k & 1) cout << "-1\n";
        else if (3 * k <= 4 * n) cout << "3\n";
        else cout << "-1\n";
    }
    return 0;
}

本人第一篇题解，文章有问题随时都能和我反馈