题意:给定一个2*N的方格,从左上角开始走,有些格子不能走,问能否一次遍历所有能走的方格
在Gym上看到一场香港的比赛,很好奇就去看了一下,发现第一题很有趣,并且很水,似乎讨论一下奇偶性就行了,然后。。。我Wa了五次。。。
主要是以下三种情况比较坑:
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000+10
struct point{int x,y;}p[MAXN];
int n,m,tot;
bool cmp(point a,point b){return a.x<b.x;}
int main(){
scanf("%d%d",&n,&m);
bool flag=;
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
swap(x,y);
if(x==&&y==){printf("No\n");return ;}
if(x==&&y==)flag=;
p[i].x=x;p[i].y=y;
}
if(flag){
sort(p+,p+m+,cmp);
tot=;
int t=m;
while(t){
if(p[t].x==p[t-].x){
if(p[t].x!=n){printf("No\n");return ;}
else {n--;m-=;}
}
else break;
t-=;
}
for(int i=;i<m;i++){
if(tot==*n-m)break;
if(p[i].y!=p[i+].y){
int dis=p[i+].x-p[i].x;
if(dis==){
if(tot==*n-m-)break;
else{printf("No\n");return ;}
}
else if(dis&){printf("No\n");return ;}
tot+=*(dis-)+;
}
else{
int dis=p[i+].x-p[i].x;
if(!(dis&)){printf("No\n");return ;}
tot+=*(dis-)+;
}
}
}
else{
m++;p[m].x=;p[m].y=;
tot=;
sort(p+,p+m+,cmp);
int t=m;
while(t){
if(p[t].x==p[t-].x){
if(p[t].x!=n){printf("No\n");return ;}
else {n--;m-=;}
}
else break;
t-=;
}
for(int i=;i<m;i++){
if(tot==*n-(m-))break;
if(p[i].y!=p[i+].y){
int dis=p[i+].x-p[i].x;
if(dis&){printf("No\n");return ;}
tot+=*(dis-)+;
}
else{
int dis=p[i+].x-p[i].x;
if(!(dis&)){printf("No\n");return ;}
tot+=*(dis-)+;
}
}
}
printf("Yes\n");
return ;
}