题解

题面描述

小美在一个无限大的二维坐标系上运动，初始位置为 $(x,y)$。她有一个长度为 $n$ 的整数数组 $\{a_1,a_2,\dots,a_n\}$，表示每次移动的“距离”。在第 $i$ 次移动时，她需要选择一对整数 $(l,r)$ 满足

然后将当前位置由 $(x,y)$ 变为 $(x + l,\;y + r)$。
问：经过 $n$ 次移动后，小美能否恰好到达目标位置 $(p,q)$？

思路

1. 移动能力分析

   • 当 $a_i = 0$ 时，唯一可能是 $l = 0, r = 0$，即“停在原地”。
   • 当 $a_i = 1$ 时，可能的移动有四种：$$(l,r) = (1,0),\;(-1,0),\;(0,1),\;(0,-1)$$ 即上下左右各走一步。

2. 总体可达性条件

   • 令$$m = \sum_{i=1}^{n} a_i$$ 则恰有 $m$ 次“有效”移动（每次都走一格），其余 $n-m$ 次保持不动。
   • 从起点 $(x,y)$ 到终点 $(p,q)$ 的曼哈顿距离为$$D = |p - x| + |q - y|.$$
   • 要想恰好到达目标，必须满足：

   1. 可走步数要够：$D \le m;$
   2. 步数的“奇偶”要匹配：$m - D\equiv 0\pmod{2}.$

   • 理由：
     • 最少需要 $D$ 步才能凑齐水平和竖直的距离差，若 $m < D$，再多的停留操作也填补不了距离。
     • 如果 $m > D$，多出的步数必须通过“多走回头路”来消耗，每多走两步就可回到同一点，因此需要 $(m-D)$ 为偶数。

C++

#include <bits/stdc++.h>
using namespace std;
// 主函数
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;                   // 测试组数
    while (T--) {
        long long n;
        cin >> n;               // 数组长度
        long long m = 0;        // 有效步数总和
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;           // 读入 a_i
            m += a;             // 累加有效步数
        }
        long long x, y, p, q;
        cin >> x >> y >> p >> q;  // 读入起点和终点
        // 计算曼哈顿距离
        long long D = llabs(p - x) + llabs(q - y);
        // 判断可达性：步数够且步数-距离为偶数
        if (D <= m && (m - D) % 2 == 0) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

Python

import sys
input = sys.stdin.readline

def main():
    T = int(input())  # 测试组数
    for _ in range(T):
        n = int(input().strip())
        a = list(map(int, input().split()))
        # 有效步数总和
        m = sum(a)
        x, y, p, q = map(int, input().split())
        # 计算曼哈顿距离
        D = abs(p - x) + abs(q - y)
        # 可达性判断
        if D <= m and (m - D) % 2 == 0:
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());  // 测试组数
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine());
            long m = 0;
            // 累加有效步数
            for (int i = 0; i < n; i++) {
                m += Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            long p = Long.parseLong(st.nextToken());
            long q = Long.parseLong(st.nextToken());
            // 计算曼哈顿距离
            long D = Math.abs(p - x) + Math.abs(q - y);
            // 判断并输出
            if (D <= m && (m - D) % 2 == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

题目内容

小美正在一个无限大的二维坐标轴上运动，初始时她位于坐标$(x,y)$。

她将基于一个由$n$个整数组成的数组{$a_1,a_2,...,a_n$}进行移动，对于第$i$次移动，她都需要选择这样两个整数$l$和$r$，满足$|1|+|r|=a_i$，随后移动到$(x +l, y +r)$这个位置。

现在请问，$n$次移动后，她能否恰好移动到$(p, q)$ 这个位置。

输入描述

第一行一个整数$t(1≤t≤1000)$，表示数据组数。对于每组数据格式为:

第一行一个整数$n(1≤n≤10^5)$，表示数组长度。

第二行$n$个整数，第$i$个整数为$a_i(0 ≤ a_i≤ 1)$，表示每次移动的距离。

第三行四个整数$x,y,p,q(-10^{18} ≤x,y,p,q≤ 10^{18})$，分别表示起点的横纵坐标，终点的横纵坐标。

数据保证单个测试文件$\sum n≤10^5$

输出描述

对于每组数据输出一个字符串，若可以恰好移动到$(p,q)$输出"$YES$"，否则输出"$NO$"。

样例1

输入

2
2
0 0
1 1 1 1
3 
1 1 1
1 1 2 2

输出

YES
NO