至【牛客tracker 每日一题】
至
时间限制：1秒 空间限制：1024M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
⭐我喜欢在雨天屋檐下追溯滞后的频率
Bingbong 给定一个大小为2 × n 2×n2×n（2 22行n nn列）的矩阵，我们使用( i , j ) (i,j)(i,j)表示矩阵中从上往下数第i ii行和从左往右数第j jj列的位置，初始时每个位置都为空地。Bing 初始位于( x 1 , y 1 ) (x_1,y_1)(x1,y1)，Bong 初始位于( x 2 , y 2 ) (x_2,y_2)(x2,y2)，两个人的位置可以重复。
他们每次移动会以向上、向下或者向右移动一个单元格，直到移动到终点( 2 , n ) (2,n)(2,n)，前提是不能超出边界。
一个位置若放置了障碍物，则无法进入。现在你可以在矩阵上放置任意数量的障碍物（也可以不放置障碍物），需要满足以下条件：
- 两个人的初始位置和终点不得放置障碍物。
- 两个人都至少存在一条路径可以到达( 2 , n ) (2,n)(2,n)。
- 使得B i n g BingBing和B o n g BongBong两个人移动到终点的最短路径长度相等。
请判断是否存在满足条件的放置方法，若存在输出Y E S YESYES，否则输出N O NONO。
输入描述：
第一行输入一个整数n ( 1 ≦ n ≦ 1 0 5 ) n(1≦n≦10^5)n(1≦n≦105)，表示矩阵的列长。
第二行输入两个整数x 1 , y 1 ( 1 ≦ x 1 ≦ 2 ; 1 ≦ y 1 ≦ n ) x_1,y_1(1≦x_1≦2; 1≦y_1≦n)x1,y1(1≦x1≦2;1≦y1≦n)，表示B i n g BingBing的起始位置。
第三行输入两个整数x 2 , y 2 ( 1 ≦ x 2 ≦ 2 ; 1 ≦ y 2 ≦ n ) x_2,y_2(1≦x_2≦2; 1≦y_2≦n)x2,y2(1≦x2≦2;1≦y2≦n)，表示B o n g BongBong的起始位置。
输出描述：
请判断是否存在满足条件的放置方法，若存在输出Y E S YESYES，否则输出N O NONO。
示例1
输入：
6 1 1 1 1输出：
YES示例2
输入：
6 1 1 1 2输出：
NO解题思路
首先检查起始位置的列是否超过n nn，若超过则直接输出N O NONO；随后根据两人起始位置的行是否相同分类判断，若行相同，列相同则初始最短路径长度一致，输出Y E S YESYES，列不同则无法通过放置障碍物调整路径长度使其相等，输出N O NONO；若行不同，先排除某位置列为n nn且行的关系导致无法调整的边界情况，再判断列的差值是否为1 11且满足行与列的位置条件（如x 1 > x 2 x_1>x_2x1>x2时y 1 ≠ n − 1 y_1≠n-1y1=n−1等），满足则可通过放置障碍物调整路径长度使其相等，输出Y E S YESYES，否则输出N O NONO；该方法通过分析起始位置的行和列的数学关系，避免模拟路径和障碍物放置，时间复杂度为O ( 1 ) O(1)O(1)，适配n nn达1 e 5 1e51e5的规模，精准判断是否存在符合条件的放置方法。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=5e2+20;intmain(){ll n;cin>>n;ll x1,x2,y1,y2;cin>>x1>>y1;cin>>x2>>y2;if(y1>n||y2>n)cout<<"NO"<<endl;elseif(x1==x2){if(y1==y2)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}else{if((x1>x2&&y1==n)||(x1<x2&&y2==n))cout<<"NO"<<endl;elseif((y1-y2==1)||(y2-y1==1)&&((x1>x2&&y1!=n-1)||(x2>x1&&y2!=n-1)))cout<<"YES";elsecout<<"NO"<<endl;}return0;}