OI

【NOIP2017】D2T1奶酪&NOIP2017游记

NOIP2017已经过去一个多月了。比赛一结束就各种忙，当场的情形还是会时不时的脑内闪回，最近终于得闲回顾。

一共只拿了105分，结束了第一次参加的比赛。D1T2大模拟complexity看完题虽然棘手，却感觉蛮好玩，有一种写编译器的感觉……虽然写完心很累，要处理的点太多，大样例还错一堆，不过还算搞到40分；D2T2本来就没底的，最小生成树都不会写的我凭着考前两天抱佛脚的Dijkstra竟也骗到了35分；而D2T3似乎送的分没拿全，30分；虽然考得不好，心情却迷之愉快（

这次最遗憾的是两天的第一题，竟然全都爆零了；D1的那题是个小学奥数，我也认栽了；可D2T1的奶酪很常规，是我考下来自认为唯一能拿分的题……当时看到成绩的时候也有些懵了。

考场上就想到这应该就直接搜出来：每个节点间判断是否联通，在从底端的点往上搜。整个写下来也有条有理（比起那D1T2大模拟(*/ω＼*)）。还不紧不慢地写个结构体存节点，邻接矩阵存联通，再DFS，搜到上界就停。打完了也很开心呀，觉得没什么问题，小样例也过了，而大样例错了几个，我想可能是精度问题，毕竟sqrt了一下，应该还是能得点分的，问题博大；结果就爆零了……

回头重做，首先一个大问题是根本没有考虑一个点顶天立地的情况，存开始/结束节点时还手贱写了个else，直接gg。回头数据发下来，第一个点就是这个问题。

这里一改，再测，70分，嗯，就是精度问题了。把sqrt改成平方原数，double改long long再测，嗯，超时了。

又回过头优化dfs，把点从小到大先排序，再把走过的点剪掉，总算是AC了。

这么回过头一看，发现也该我爆零了，吃了缺经验的亏……

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    struct node{
        long long x,y,z;
    };
    struct node a[1005]={0};
    int start[1005]={0},end[1005]={0},flag,n;
    long long h,r;
    int map[1005][1005]={0};
    long long dist(int p1,int p2){
        long long x1,y1,z1,x2,y2,z2;
        x1=a[p1].x;
        y1=a[p1].y;
        z1=a[p1].z;
        x2=a[p2].x;
        y2=a[p2].y;
        z2=a[p2].z;
        return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
    }
    int judge(int p1,int p2){
        if(dist(p1,p2)<=2*r*2*r)return 1;
        return 0;
    }
    int visited[1005]={0};
    void dfs(int i){
        if(flag)return;
        int j;
        for(j=i;j<=n;j++)
            if(map[i][j]&&!visited[j]){
                visited[j]=1;
                if(end[j])
                  flag=1;
                else dfs(j);
                visited[j]=0;
            }
    }
    void qqsort(int l,int r){
        int i,j;
        long long mid;
        struct node t;
        i=l;
        j=r;
        mid=a[(i+j)/2].z;
        do{
            while(a[i].z<mid)i++;
            while(a[j].z>mid)j--;
            if(i<=j){
                t=a[i];
                a[i]=a[j];
                a[j]=t;
                i++;
                j--;
            }
        }while(i<=j);
        if(i<r)qqsort(i,r);
        if(j>l)qqsort(l,j);
    }
    int main(){
        int t,i,j,k;
        scanf("%d",&t);
        for(i=1;i<=t;i++){
            flag=0;
            scanf("%d%lld%lld",&n,&h,&r);
            for(j=1;j<=n;j++){
                start[j]=0;
                end[j]=0;
            }
            for(j=1;j<=n;j++)
                scanf("%lld%lld%lld",&a[j].x,&a[j].y,&a[j].z);
            qqsort(1,n);
            for(j=1;j<=n;j++){
              if(a[j].z-r<=0)start[j]=1;
              if(a[j].z+r>=h)end[j]=1;
              for(k=j+1;k<=n;k++)
                  if(judge(j,k)){
                      map[j][k]=1;
                      map[k][j]=1;
                  }
                  else{
                      map[j][k]=0;
                      map[k][j]=0;
                  }
            }
            for(j=1;j<=n;j++){
              if(start[j]&&end[j]){
                  flag=1;
                  break;
              }
              if(start[j])dfs(j);
              else break;
              if(flag)break;
            }
            if(flag)printf("Yes\n");
            else printf("No\n");
        }
        return 0;
}