20190810 夏洛特——charlotte
思路：
设$Dis=A到B的哈曼顿距离$,$T=Tb-Ta$
如果$T<Dis$,则一定不能到达直接输出$No$
如果$T=Dis$,则一定能到达,输出$Yes$
如果$T>Dis$,分为两类:
如果$T-Dis$为偶数,则多余的路程可以来回走动,最后一定恰好能到达
如果$T-Dis$为奇数,则一定不能通过来回走动消耗多余路程,一定到达不了
最后只要按照Ti排序,检查相邻两个点是否合法即可
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &F)
{
F=0;int R=1;char CH=getchar();
while(!isdigit(CH)&&CH!='-') CH=getchar();
if(CH=='-') R=-1;else F=(CH^48);CH=getchar();
while(isdigit(CH)) F=(F<<1)+(F<<3)+(CH^48),CH=getchar(); F*=R;
}
struct place{
int ti,xi,yi;
friend bool operator < (place a,place b){return a.ti<b.ti;}
}pi[100010];
int jl(int i){return abs(pi[i].xi-pi[i-1].xi)+abs(pi[i].yi-pi[i-1].yi);}
int main()
{
//freopen("charlotte.in","r",stdin);
//freopen("charlotte.out","w",stdout);
int T;
read(T);
while(T--)
{
int n;
read(n);
for(int i=1;i<=n;i++)
read(pi[i].ti),read(pi[i].xi),read(pi[i].yi);
sort(pi+1,pi+n+1);
int fl=0;
for(int i=1;i<=n;i++)
{
if(pi[i].ti-pi[i-1].ti<jl(i)) {fl=1,puts("No");break;}
else if((pi[i].ti-pi[i-1].ti-jl(i))%2) {fl=1,puts("No");break;}
}
if(!fl) puts("Yes");
}
return 0;
}
|