• 蓝桥杯2022初赛——扫雷

    4407. 扫雷

    小明最近迷上了一款名为《扫雷》的游戏。

    其中有一个关卡的任务如下：

    在一个二维平面上放置着 n

    个炸雷，第 i 个炸雷 (xi,yi,ri) 表示在坐标 (xi,yi) 处存在一个炸雷，它的爆炸范围是以半径为 ri

    的一个圆。

    为了顺利通过这片土地，需要玩家进行排雷。

    玩家可以发射 m

    个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj,yj,rj) 表示这个排雷火箭将会在 (xj,yj) 处爆炸，它的爆炸范围是以半径为 rj

    的一个圆，在其爆炸范围内的炸雷会被引爆。

    同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。

    现在小明想知道他这次共引爆了几颗炸雷？

    你可以把炸雷和排雷火箭都视为平面上的一个点。

    一个点处可以存在多个炸雷和排雷火箭。

    当炸雷位于爆炸范围的边界上时也会被引爆。

    输入格式

    输入的第一行包含两个整数 n、m

    。

    接下来的 n

    行，每行三个整数 xi,yi,ri

    ，表示一个炸雷的信息。

    再接下来的 m

    行，每行三个整数 xj,yj,rj

    ，表示一个排雷火箭的信息。

    输出格式

    输出一个整数表示答案。

    数据范围

    对于 40%

    的评测用例：0≤x,y≤109,0≤n,m≤103,1≤r≤10，
    对于 100% 的评测用例：0≤x,y≤109,0≤n,m≤5×104,1≤r≤10

    。

    输入样例：

    1. 2 1
    2. 2 2 4
    3. 4 4 2
    4. 0 0 5

    输出样例：

    2

    样例解释

    示例图如下，排雷火箭 1

    覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2

    也被排除。

    排雷火箭可以排掉地雷，地雷又可以排掉它能排掉范围内的地雷，所以显然是图的遍历问题。

    可是，如果不对原始数据进行处理，直接用邻接表或者临界矩阵来建图，明显会超时。因为点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9。但是先把坐标按x轴从小到大排序，再按y轴从小到大排序，时间复杂度是O(nlgn),再加上建图的时间复杂度O(n*r),查询的时间复杂度O(m*lgn+n)。可以AC。

    这道题我花了数日，研究了数种方法，有map解决，unordered_map解决，有手写hash表解决，能AC的BFS和DFS我都写出来了，不是y总讲的方法，便是在acwing上看到大佬写的代码，自己动手写了一遍。不言而喻，效率比较：手写hash > unordered_map > map,

    不过话说回来，在这道题中让我学到的知识蛮不少的。

    代码中我有一些调试的代码，我没删除，那一部分到也没必要看，我都注释掉了的。

    一共十一种代码，能AC的倒没几种，不过在写的过程中，是满满的收获啊。学到了如何手写hash表，map和unorded_map的效率差别，知道了当自己写的结构体或者pair作为unordered_map的key值的时候，需要自己写一个函数来对他们排序，因为编译器无法知道他们的关系。当然这个函数要用类来封装。想必以后也能用上lower_bound()和upper_bound了吧。虽然都知道这些函数，但是不知道什么时候用，还是自己写的题目太少了。同志，革命尚未成功，吾得急需努力。

    其实算法笔记讲解BFS的时候就已经强调了inq表示结点是否入队，而不是是否访问，否则就会存在多个点进行入队，这和DFS的vis数组是有区别的，当时还不以为然，觉得自己都理解了，现在想想，亦是惭愧！书你倒是看了，但你是否真正的吸收了呢？每学到一个算法，就要去找相应的题目来做，不然你也只是白白浪费时间，多了不说，算法笔记上的树状数组以及lowbit数组你现在是否还能知道它们的意思，KMP算法是否还有印象，快速排序是否还能写出来，组合数的知识还知道多少。。。等等，不光是低头做题，还得总结自己学到的东西，以后遇到能够用自己学过的算法解决的题目的时候，别两眼一蹬，我不会，毫无思路？那就从此处开始，把之前写的算法发成博客吧，也能再温习一遍。

    万丈高楼平地起，莫在浮沙筑高台！

    第一种，图的深度优先遍历，邻接表实现，  由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，  明显会超时。

    1. /**
    2.     图的深度优先遍历，邻接表实现
    3.     由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
    4.     明显会超时
    5. */
    6. /**
    7. #include <iostream>
    8. #include <cstdio>
    9. #include <cmath>
    10. #include <vector>
    11. using namespace std;
    12.  
    13. const int maxn=1010;
    14. struct Node
    15. {
    16.     int x,y,r;
    17. }cir[maxn];
    18. vector<int> adj[maxn];
    19. bool vis[maxn]={false};
    20. int n,m;
    21. int dfs_Trave(int x,int y,int r);
    22. int dfs(int index);
    23. void add(int index);
    24. int main()
    25. {
    26.     scanf("%d%d",&n,&m);
    27.     int x,y,r;
    28.     for(int i=0;i<n;++i)
    29.     {
    30.         scanf("%d%d%d",&x,&y,&r);
    31.         cir[i]={x,y,r};
    32.     }
    33.  
    34.     for(int i=0;i<n;++i)
    35.     {
    36.         add(i);
    37.     }
    38. //    cout << "调试:\n";
    39. //    for(int i=0;i<n;++i)
    40. //    {
    41. //        for(auto b:adj[i])
    42. //            cout << b << ' ';
    43. //        cout << endl;
    44. //    }
    45. //    cout << "jk\n";
    46.     int res=0;
    47.     for(int i=0;i<m;++i)
    48.     {
    49.         scanf("%d%d%d",&x,&y,&r);
    50.        // cout << "r:" << r << endl;
    51.         //printf("r:%d\n",r);
    52.         res+=dfs_Trave(x,y,r);
    53.     }
    54.  
    55.     printf("%d\n",res);
    56.     return 0;
    57. }
    58.  
    59. void add(int index)
    60. {
    61.     for(int i=0;i<n;++i)
    62.         if(i!=index)
    63.         {
    64.             if(cir[index].r>(sqrt(pow(cir[i].x-cir[index].x,2)+pow(cir[i].y-cir[index].y,2))))
    65.                 adj[index].push_back(i);
    66.         }
    67. }
    68.  
    69. int dfs(int index)
    70. {
    71.     //cout << "jinbulai?\n";
    72.     int sum=1;
    73.     vis[index]=true;
    74.     for(int i=0;i<adj[index].size();++i)
    75.     {
    76.         int v=adj[index][i];
    77.         if(vis[v]==false)
    78.             sum+=dfs(v);
    79.     }
    80.     return sum;
    81.  
    82. }
    83.  
    84. int dfs_Trave(int x,int y,int r)
    85. {
    86.    // cout << "r:" << r << endl;
    87.     int sum=0;
    88.     for(int i=0;i<n;++i)
    89.     {
    90.         double L=sqrt(pow(x-cir[i].x,2)+pow(y-cir[i].y,2));
    91.       //  cout << "length:" << L << endl;
    92.         if(r>L)
    93.         {
    94.            // cout << "error: \n";
    95.             if(vis[i]==false)
    96.                 sum+=dfs(i);
    97.         }
    98.     }
    99.     return sum;
    100. }

    第二种， 图的深度优先遍历，邻接表实现，由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，先把坐标按x轴从小到大排序，再按y轴从小到大排序， acwing 最后一组数据通不过，最开始的时候始终找不出原因，现在想想，也能理解，
        当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
        不然建图的时候有O(n^2)的时间复杂度。
        下一个代码我给出了AC的代码；
    */

    1. /**
    2.     图的深度优先遍历，邻接表实现
    3.     由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
    4.     先把坐标按x轴从小到大排序，再按y轴从小到大排序
    5.     acwing 最后一组数据通不过，最开始的时候始终找不出原因，现在想想，也能理解，
    6.     当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
    7.     不然建图的时候有O(n^2)的时间复杂度。
    8.     下一个代码我给出了AC的代码；
    9. */
    11. /**
    12. #include <iostream>
    13. #include <cstdio>
    14. #include <cmath>
    15. #include <algorithm>
    16. #include <vector>
    17. #include <unordered_map>
    18. using namespace std;
    19.  
    20. const int maxn=50010;
    21. struct Node
    22. {
    23.     int x,y,r;
    24.     int cnt;
    25.  
    26.     Node (int _x,int _y) : x(_x),y(_y){}
    27.     Node (int _x,int _y,int _r) : x(_x),y(_y),r(_r){}
    28.     Node (int _x,int _y,int _r,int _cnt) :x(_x),y(_y),r(_r),cnt(_cnt){}
    29.     Node()=default;
    30.     bool operator < (Node const & a) const
    31.     {
    32.         if(x!=a.x)
    33.             return x<a.x;
    34.         return y<a.y;
    35.     }
    36. }cir[maxn];
    37. struct comp
    38. {
    39.     int operator()(const std::pair<int, int>& p) const {
    40.         return p.first ^ p.second;  //返回值为bool，比较符为&，|都比这一个慢，
    41.     }
    42. };
    43. typedef long long LL;
    44. LL squ(int x)
    45. {
    46.     return (LL) x*x;
    47. }
    48. vector<int> adj[maxn];
    49. unordered_map<pair<int,int> ,int,comp> ump;
    50. bool vis[maxn]={false};
    51. int n,m;
    52. int dfs_Trave(int x,int y,int r);
    53. int dfs(int index);
    54. void add(int index);
    55. int main()
    56. {
    57.     scanf("%d%d",&n,&m);
    58.     int x,y,r;
    59.     for(int i=1;i<=n;++i)
    60.     {
    61.         scanf("%d%d%d",&x,&y,&r);
    62.         auto temp=ump[{x,y}];
    63.         if(temp!=0)
    64.         {
    65.            cir[temp].r=max(cir[temp].r,r);
    66.            cir[temp].cnt++;
    67.         }
    68.         else
    69.         {
    70.             cir[i]={x,y,r,1};   //应当用一个全局变量来表示不重复点的下标
    71.             ump[{x,y}]=i;       //
    72.         }
    73.     }
    74.     sort(cir+1,cir+n+1);
    75.  
    76. //    Node temp={2,3,9};
    77. //    auto it=lower_bound(cir+1,cir+n+1,temp);
    78. //    cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
    79. //    Node temp2={2,50,9};
    80. //    it=lower_bound(cir+1,cir+n+1,temp2);
    81. //    cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
    82. //    cout << "调试:\n";
    83. //    for(int i=1;i<=n;++i)
    84. //        cout << cir[i].x << ' ' << cir[i].y << ' ' << cir[i].r << endl;
    85. //    cout << "ok\n";
    86.     for(int i=1;i<=n;++i)
    87.     {
    88.         add(i);
    89.     }
    90. //    cout << "调试:\n";
    91. //    for(int i=0;i<n;++i)
    92. //    {
    93. //        for(auto b:adj[i])
    94. //            cout << b << ' ';
    95. //        cout << endl;
    96. //    }
    97. //    cout << "jk\n";
    98.     int res=0;
    99.     for(int i=0;i<m;++i)
    100.     {
    101.         scanf("%d%d%d",&x,&y,&r);
    102.        // cout << "r:" << r << endl;
    103.         //printf("r:%d\n",r);
    104.         res+=dfs_Trave(x,y,r);
    105.     }
    106.  
    107.     printf("%d\n",res);
    108.     return 0;
    109. }
    110.  
    111. void add(int index)
    112. {
    113.     for(int i=index-1;i>0;--i)
    114.     {
    115.         if(squ(cir[index].r)<squ(cir[i].x-cir[index].x))
    116.             break;
    117.         if(squ(cir[index].r)>=squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
    118.             adj[index].push_back(i);
    119.     }
    120.  
    121.     for(int i=index+1;i<=n;++i)
    122.     {
    123.         if(squ(cir[index].r) < squ(cir[i].x-cir[index].x))
    124.            break;
    125.         if(squ(cir[index].r) >= squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
    126.             adj[index].push_back(i);
    127.     }
    128. }
    129.  
    130. int dfs(int index)
    131. {
    132.     int sum=cir[index].cnt;
    133.     vis[index]=1;
    134.     for(int i=0;i<adj[index].size();++i)
    135.     {
    136.         int v=adj[index][i];
    137.         if(vis[v]==0)
    138.             sum+=dfs(v);
    139.     }
    140.     return sum;
    141.  
    142. }
    143.  
    144. int dfs_Trave(int x,int y,int r)
    145. {
    146.     Node e1={x-r,y,r},e2={x+r,y,r};
    147.     int l=lower_bound(cir+1,cir+n+1,e1)-cir;
    148.     int ri=lower_bound(cir+1,cir+n+1,e2)-cir;
    149.     l=min(l,n),ri=min(ri,n);
    150.     int sum=0;
    151.     for(int i=l;i<=ri;++i)
    152.     {
    153.         if(i==0)
    154.             continue;
    155.         if((squ(r)>=squ(cir[i].x-x)+squ(cir[i].y-y))&&vis[i]==0)
    156.             sum+=dfs(i);
    157.     }
    158.     return sum;
    159. }

    第三个，/**
        图的深度优先遍历，邻接表实现
        由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
        先把坐标按x轴从小到大排序，再按y轴从小到大排序
        当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
        不然建图的时候有O(n^2)的时间复杂度。
        能AC

    1. /**
    2.     图的深度优先遍历，邻接表实现
    3.     由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
    4.     先把坐标按x轴从小到大排序，再按y轴从小到大排序
    5.     当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
    6.     不然建图的时候有O(n^2)的时间复杂度。
    7.     能AC
    8. */
    10. /**
    11. #include <iostream>
    12. #include <cstdio>
    13. #include <cmath>
    14. #include <algorithm>
    15. #include <vector>
    16. #include <unordered_map>
    17. using namespace std;
    18.  
    19. const int maxn=50010;
    20. struct Node
    21. {
    22.     int x,y,r;
    23.     int cnt;
    24.  
    25.     Node (int _x,int _y) : x(_x),y(_y){}
    26.     Node (int _x,int _y,int _r) : x(_x),y(_y),r(_r){}
    27.     Node (int _x,int _y,int _r,int _cnt) :x(_x),y(_y),r(_r),cnt(_cnt){}
    28.     Node()=default;
    29.     bool operator < (Node const & a) const
    30.     {
    31.         if(x!=a.x)
    32.             return x<a.x;
    33.         return y<a.y;
    34.     }
    35. }cir[maxn];
    36. struct comp
    37. {
    38.     int operator()(const std::pair<int, int>& p) const {
    39.         return p.first ^ p.second;  //返回值为bool，比较符为&，|都比这一个慢，
    40.     }
    41. };
    42. typedef long long LL;
    43. LL squ(int x)
    44. {
    45.     return (LL) x*x;
    46. }
    47. vector<int> adj[maxn];
    48. unordered_map<pair<int,int> ,int,comp> ump; //实践上机证明将坐标转化为long long 比这种方式快上一点
    49. bool vis[maxn]={false};
    50. int n,m,n1=0;
    51. int dfs_Trave(int x,int y,int r);
    52. int dfs(int index);
    53. void add(int index);
    54. int main()
    55. {
    56.     scanf("%d%d",&n,&m);
    57.     int x,y,r;
    58.     for(int i=1;i<=n;++i)
    59.     {
    60.         scanf("%d%d%d",&x,&y,&r);
    61.         auto temp=ump[{x,y}];
    62.         if(temp!=0)
    63.         {
    64.            cir[temp].r=max(cir[temp].r,r);
    65.            cir[temp].cnt++;
    66.         }
    67.         else
    68.         {
    69.             cir[++n1]={x,y,r,1};
    70.             ump[{x,y}]=n1;
    71.            // cir[i].cnt=1;
    72.         }
    73.     }
    74.     sort(cir+1,cir+n1+1);
    75.  
    76. //    Node temp={2,3,9};
    77. //    auto it=lower_bound(cir+1,cir+n+1,temp);
    78. //    cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
    79. //    Node temp2={2,50,9};
    80. //    it=lower_bound(cir+1,cir+n+1,temp2);
    81. //    cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
    82. //    cout << "调试:\n";
    83. //    for(int i=1;i<=n;++i)
    84. //        cout << cir[i].x << ' ' << cir[i].y << ' ' << cir[i].r << endl;
    85. //    cout << "ok\n";
    86.     for(int i=1;i<=n1;++i)
    87.     {
    88.         add(i);
    89.     }
    90.     int res=0;
    91.     for(int i=0;i<m;++i)
    92.     {
    93.         scanf("%d%d%d",&x,&y,&r);
    94.         res+=dfs_Trave(x,y,r);
    95.     }
    96.  
    97.     printf("%d\n",res);
    98.     return 0;
    99. }
    100.  
    101. void add(int index)
    102. {
    103.     for(int i=index-1;i>0;--i)
    104.     {
    105.         if(squ(cir[index].r)<squ(cir[i].x-cir[index].x))
    106.             break;
    107.         if(squ(cir[index].r)>=squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
    108.             adj[index].push_back(i);
    109.     }
    110.  
    111.     for(int i=index+1;i<=n1;++i)
    112.     {
    113.         if(squ(cir[index].r) < squ(cir[i].x-cir[index].x))
    114.            break;
    115.         if(squ(cir[index].r) >= squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
    116.             adj[index].push_back(i);
    117.     }
    118. }
    119.  
    120. int dfs(int index)
    121. {
    122.     int sum=cir[index].cnt;
    123.     vis[index]=1;
    124.     for(int i=0;i<adj[index].size();++i)
    125.     {
    126.         int v=adj[index][i];
    127.         if(vis[v]==0)
    128.             sum+=dfs(v);
    129.     }
    130.     return sum;
    131.  
    132. }
    133.  
    134. int dfs_Trave(int x,int y,int r)
    135. {
    136.     Node e1={x-r,y,r},e2={x+r,y,r};
    137.     int l=lower_bound(cir+1,cir+n1+1,e1)-cir;
    138.     int ri=lower_bound(cir+1,cir+n1+1,e2)-cir;
    139.     l=min(l,n1),ri=min(ri,n1);
    140.     int sum=0;
    141.     for(int i=l;i<=ri;++i)
    142.     {
    143.         if(i==0)
    144.             continue;
    145.         if((squ(r)>=squ(cir[i].x-x)+squ(cir[i].y-y))&&vis[i]==0)
    146.             sum+=dfs(i);
    147.     }
    148.     return sum;
    149. }

    第四个， 图的广度优先遍历，邻接表实现
        由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
        先把坐标按x轴从小到大排序，再按y轴从小到大排序
        当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
        不然建图的时候有O(n^2)的时间复杂度。
        能AC

    1. /**
    2.     图的广度优先遍历，邻接表实现
    3.     由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
    4.     先把坐标按x轴从小到大排序，再按y轴从小到大排序
    5.     当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
    6.     不然建图的时候有O(n^2)的时间复杂度。
    7.     能AC
    8. */
    9.  
    10. #include <iostream>
    11. #include <cstdio>
    12. #include <cmath>
    13. #include <algorithm>
    14. #include <vector>
    15. #include <queue>
    16. #include <unordered_map>
    17. using namespace std;
    18.  
    19. const int maxn=50010;
    20. struct Node
    21. {
    22.     int x,y,r;
    23.     int cnt;
    24.  
    25.     Node (int _x,int _y) : x(_x),y(_y){}
    26.     Node (int _x,int _y,int _r) : x(_x),y(_y),r(_r){}
    27.     Node (int _x,int _y,int _r,int _cnt) :x(_x),y(_y),r(_r),cnt(_cnt){}
    28.     Node()=default;
    29.     bool operator < (Node const & a) const
    30.     {
    31.         if(x!=a.x)
    32.             return x<a.x;
    33.         return y<a.y;
    34.     }
    35. }cir[maxn];
    36. struct comp
    37. {
    38.     int operator()(const std::pair<int, int>& p) const {
    39.         return p.first ^ p.second;  //返回值为bool，比较符为&，|都比这一个慢，
    40.     }
    41. };
    42. typedef long long LL;
    43. LL squ(int x)
    44. {
    45.     return (LL) x*x;
    46. }
    47. vector<int> adj[maxn];
    48. unordered_map<pair<int,int> ,int,comp> ump; //实践上机证明将坐标转化为long long 比这种方式快上一点
    49. bool vis[maxn]={false};
    50. int n,m,n1=0;
    51. int bfs_Trave(int x,int y,int r);
    52. int bfs(int index);
    53. void add(int index);
    54. int main()
    55. {
    56.     scanf("%d%d",&n,&m);
    57.     int x,y,r;
    58.     for(int i=1;i<=n;++i)
    59.     {
    60.         scanf("%d%d%d",&x,&y,&r);
    61.         auto temp=ump[{x,y}];
    62.         if(temp!=0)
    63.         {
    64.            cir[temp].r=max(cir[temp].r,r);
    65.            cir[temp].cnt++;
    66.         }
    67.         else
    68.         {
    69.             cir[++n1]={x,y,r,1};
    70.             ump[{x,y}]=n1;
    71.            // cir[i].cnt=1;
    72.         }
    73.     }
    74.     sort(cir+1,cir+n1+1);
    75.  
    76. //    Node temp={2,3,9};
    77. //    auto it=lower_bound(cir+1,cir+n+1,temp);
    78. //    cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
    79. //    Node temp2={2,50,9};
    80. //    it=lower_bound(cir+1,cir+n+1,temp2);
    81. //    cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
    82. //    cout << "调试:\n";
    83. //    for(int i=1;i<=n;++i)
    84. //        cout << cir[i].x << ' ' << cir[i].y << ' ' << cir[i].r << endl;
    85. //    cout << "ok\n";
    86.     for(int i=1;i<=n1;++i)
    87.     {
    88.         add(i);
    89.     }
    90.     int res=0;
    91.     for(int i=0;i<m;++i)
    92.     {
    93.         scanf("%d%d%d",&x,&y,&r);
    94.         res+=bfs_Trave(x,y,r);
    95.     }
    96.  
    97.     printf("%d\n",res);
    98.     return 0;
    99. }
    100.  
    101. void add(int index)
    102. {
    103.     for(int i=index-1;i>0;--i)
    104.     {
    105.         if(squ(cir[index].r)<squ(cir[i].x-cir[index].x))
    106.             break;
    107.         if(squ(cir[index].r)>=squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
    108.             adj[index].push_back(i);
    109.     }
    110.  
    111.     for(int i=index+1;i<=n1;++i)
    112.     {
    113.         if(squ(cir[index].r) < squ(cir[i].x-cir[index].x))
    114.            break;
    115.         if(squ(cir[index].r) >= squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
    116.             adj[index].push_back(i);
    117.     }
    118. }
    119.  
    120. int bfs(int index)
    121. {
    122.     queue<int> q;
    123.     q.push(index);
    124.     int sum=cir[index].cnt;
    125.     while(!q.empty())
    126.     {
    127.         int top=q.front();
    128.         q.pop();
    129.         for(int i=0;i<adj[top].size();++i)
    130.         {
    131.             int v=adj[top][i];
    132.             if(vis[v]==0)
    133.             {
    134.                 vis[v]=1;
    135.                 sum+=cir[v].cnt;
    136.                 q.push(v);
    137.             }
    138.         }
    139.     }
    140.  
    141.     return sum;
    142.  
    143. }
    144.  
    145. int bfs_Trave(int x,int y,int r)
    146. {
    147.     Node e1={x-r,y,r},e2={x+r,y,r};
    148.     int l=lower_bound(cir+1,cir+n1+1,e1)-cir;
    149.     int ri=lower_bound(cir+1,cir+n1+1,e2)-cir;
    150.     l=min(l,n1),ri=min(ri,n1);
    151.     int sum=0;
    152.     for(int i=l;i<=ri;++i)
    153.     {
    154.         if(i==0)
    155.             continue;
    156.         if((squ(r)>=squ(cir[i].x-x)+squ(cir[i].y-y))&&vis[i]==0)
    157.         {
    158.             vis[i]=1;
    159.             sum+=bfs(i);
    160.         }
    161.     }
    162.     return sum;
    163. }

    第五个，/**
        map，将坐标用pair<int,int>存在map中
    */
    /**
        1)每输入一个排雷火箭，就算出它排掉了多少雷，但是由于一个位置有多个雷
        ，所以要把这个位置的地雷数给记录下来；
        acwing通过5/11
    */

    1. /**
    2.     map，将坐标用pair<int,int>存在map中
    3. */
    4. /**
    5.     1)每输入一个排雷火箭，就算出它排掉了多少雷，但是由于一个位置有多个雷
    6.     ，所以要把这个位置的地雷数给记录下来；
    7.     acwing通过5/11
    8. */
    9. /**
    10. #include <iostream>
    11. #include <cstdio>
    12. #include <cmath>
    13. #include <vector>
    14. #include <map>
    15. using namespace std;
    16.  
    17. typedef long long LL;
    18. LL squ(int x)
    19. {
    20.     return (LL) x*x;
    21. }
    22.  
    23. map<pair<int,int>,pair<int,int> > mp;
    24. map<pair<int,int>,int > vis;
    25. int n,m;
    26. int dfs_Trave(int x,int y,int r);
    27. int dfs(pair<pair<int,int>,pair<int,int> > index);
    28. int main()
    29. {
    30.     scanf("%d%d",&n,&m);
    31.     int x,y,r;
    32.     for(int i=0;i<n;++i)
    33.     {
    34.         scanf("%d%d%d",&x,&y,&r);
    35.         auto temp=make_pair(x,y);
    36.         auto it=mp.find(temp);
    37.         if(it==mp.end())
    38.         {
    39.             vis[temp]=0;
    40.             auto val=make_pair(r,1);
    41.             mp[temp]=val;
    42.         }
    43.         else
    44.         {
    45.             if(r>it->second.first)
    46.             {
    47.                 auto val=make_pair(r,it->second.second+1);
    48.                 mp[temp]=val;
    49.             }
    50.             else
    51.             {
    52.                 auto val=make_pair(it->second.first,it->second.second+1);
    53.                 mp[temp]=val;
    54.             }
    55.         }
    56.  
    57.     }
    58.  
    59.     int res=0;
    60.     for(int i=0;i<m;++i)
    61.     {
    62.         scanf("%d%d%d",&x,&y,&r);
    63.         res+=dfs_Trave(x,y,r);
    64.     }
    65.  
    66.     printf("%d\n",res);
    67.     return 0;
    68. }
    69.  
    70. int dfs(pair<pair<int,int>,pair<int,int> > index)
    71. {
    72.     int x=index.first.first,y=index.first.second,r=index.second.first,num=index.second.second;
    73.     int sum=num;
    74.     //cout << "调试:" << sum << endl;
    75.     vis[index.first]=1;
    76.     for(int l=x-r;l<=x+r;++l)
    77.         for(int s=y+r;s>=y-r;--s)
    78.         {
    79.             if(squ(r) >= squ(l-x) + squ(s-y))
    80.             {
    81.                 auto temp=make_pair(l,s);
    82.                 auto it=mp.find(temp);
    83.                 if(it!=mp.end())
    84.                 {
    85.                     if(vis[temp]==0)
    86.                         sum+=dfs(*it);
    87.                 }
    88.             }
    89.         }
    90.     return sum;
    91.  
    92. }
    93.  
    94. int dfs_Trave(int x,int y,int r)
    95. {
    96.     int sum=0;
    97.     for(int l=x-r;l<=x+r;++l)
    98.         for(int s=y+r;s>=y-r;--s)
    99.         {
    100.             if(squ(r) >= squ(l-x) + squ(s-y))
    101.             {
    102.                 auto temp=make_pair(l,s);
    103.                 auto it=mp.find(temp);
    104.                 if(it!=mp.end())
    105.                 {
    106.                     if(vis[temp]==0)
    107.                         sum+=dfs(*it);
    108.                 }
    109.             }
    110.         }
    111.     return sum;
    112. }
    113. */
    114.

    第六个，/**
        2)先把排掉的雷给记录下来，最后统一计算，只记录半径，不用记录每个位置有多少雷；
        当相应的就需要把所有的地雷的位置给记录下来，即使他们是相同的位置这就是cir数组的作用
        acwing也是通过5/11
    */

    1. /**
    2.     2)先把排掉的雷给记录下来，最后统一计算，只记录半径，不用记录每个位置有多少雷；
    3.     当相应的就需要把所有的地雷的位置给记录下来，即使他们是相同的位置这就是cir数组的作用
    4.     acwing也是通过5/11
    5. */
    7. /**
    8. #include <iostream>
    9. #include <cstdio>
    10. #include <cmath>
    11. #include <vector>
    12. #include <map>
    13. using namespace std;
    14.  
    15. typedef long long LL;
    16. LL squ(int x)
    17. {
    18.     return (LL) x*x;
    19. }
    20. const int maxn=50010;
    21. struct Node
    22. {
    23.     int x,y,r;
    24. }cir[maxn];
    25. map<pair<int,int>,int > mp;
    26. map<pair<int,int>,int > vis;
    27. int n,m;
    28. void dfs_Trave(int x,int y,int r);
    29. void dfs(pair<pair<int,int>,int > index);
    30. int main()
    31. {
    32.     scanf("%d%d",&n,&m);
    33.     int x,y,r;
    34.     for(int i=0;i<n;++i)
    35.     {
    36.         scanf("%d%d%d",&x,&y,&r);
    37.         cir[i]={x,y,r};
    38.         auto temp=make_pair(x,y);
    39.         auto it=mp.find(temp);
    40.         if(it==mp.end())
    41.         {
    42.             vis[temp]=0;
    43.             mp[temp]=r;
    44.         }
    45.         else
    46.         {
    47.             if(r>it->second)
    48.                 mp[temp]=r;
    49.         }
    50.     }
    51.  
    52.     int res=0;
    53.     for(int i=0;i<m;++i)
    54.     {
    55.         scanf("%d%d%d",&x,&y,&r);
    56.         dfs_Trave(x,y,r);
    57.     }
    58.  
    59.     for(int i=0;i<n;++i)
    60.     {
    61.         auto temp=make_pair(cir[i].x,cir[i].y);
    62.         if(vis[temp]!=0)
    63.             ++res;
    64.     }
    65.     printf("%d\n",res);
    66.     return 0;
    67. }
    68.  
    69. void dfs(pair<pair<int,int>,int > index)
    70. {
    71.     int x=index.first.first,y=index.first.second,r=index.second;
    72.     vis[index.first]=1;
    73.     for(int l=x-r;l<=x+r;++l)
    74.         for(int s=y+r;s>=y-r;--s)
    75.         {
    76.             if(squ(r) >= squ(l-x) + squ(s-y))
    77.             {
    78.                 auto temp=make_pair(l,s);
    79.                 auto it=mp.find(temp);
    80.                 if(it!=mp.end())
    81.                 {
    82.                     if(vis[temp]==0)
    83.                         dfs(*it);
    84.                 }
    85.             }
    86.         }
    87.  
    88. }
    89.  
    90. void dfs_Trave(int x,int y,int r)
    91. {
    92.     for(int l=x-r;l<=x+r;++l)
    93.         for(int s=y+r;s>=y-r;--s)
    94.         {
    95.             if(squ(r) >= squ(l-x) + squ(s-y))
    96.             {
    97.                 auto temp=make_pair(l,s);
    98.                 auto it=mp.find(temp);
    99.                 if(it!=mp.end())
    100.                 {
    101.                     if(vis[temp]==0)
    102.                         dfs(*it);
    103.                 }
    104.             }
    105.         }
    106. }
    107. */

    第七个，/**
        unorder_map解决，将坐标用pair<int,int>存在unordered_map中
    */
    /**
        1)对于没有默认的哈希函数的类型，如自定义的 class 类型，pair 类型等，我们就必须自己
        指定一个哈希函数。这也是为什么直接构建 pair 类型的 unordered_set
        如 unordered_set<pair<int, int>> uset 会出现问题
        acwing通过5/11
    */

    1. /**
    2.     unorder_map解决，将坐标用pair<int,int>存在unordered_map中
    3. */
    4. /**
    5.     1)对于没有默认的哈希函数的类型，如自定义的 class 类型，pair 类型等，我们就必须自己
    6.     指定一个哈希函数。这也是为什么直接构建 pair 类型的 unordered_set
    7.     如 unordered_set<pair<int, int>> uset 会出现问题
    8.     acwing通过5/11
    9. */
    10.  
    11. #include <iostream>
    12. #include <cstdio>
    13. #include <cmath>
    14. #include <vector>
    15. #include <unordered_map>
    16. using namespace std;
    17.  
    18. typedef long long LL;
    19. LL squ(int x)
    20. {
    21.     return (LL) x*x;
    22. }
    23. const int maxn=50010;
    24. /*
    25. struct cmp
    26. {
    27.     bool operator()(pair<int,int> const &p) const
    28.     {
    29.         return p.first<p.second;
    30.     }
    31. };
    32. */
    33. //struct cmp
    34. //{
    35. //    std::size_t operator()(const std::pair<int, int>& p) const {
    36. //        return p.first ^ p.second;
    37. //    }
    38. //};
    39.  
    40. struct cmp
    41. {
    42.     int operator()(const std::pair<int, int>& p) const {
    43.         return p.first ^ p.second;  //返回值为bool，比较符为&，|都比这一个慢，
    44.     }
    45. };
    46. struct Node
    47. {
    48.     int x,y,r;
    49. }cir[maxn];
    50. unordered_map<pair<int,int>,int ,cmp> mp;
    51. unordered_map<pair<int,int>,int ,cmp> vis;
    52. int n,m;
    53. void dfs_Trave(int x,int y,int r);
    54. void dfs(pair<pair<int,int>,int > index);
    55. int main()
    56. {
    57. //    int a=123456789,b=123456;
    58. //    int c=a&b;
    59. //    cout << c << endl;
    60.     scanf("%d%d",&n,&m);
    61.     int x,y,r;
    62.     for(int i=0;i<n;++i)
    63.     {
    64.         scanf("%d%d%d",&x,&y,&r);
    65.         cir[i]={x,y,r};
    66.         auto temp=make_pair(x,y);
    67.         auto it=mp.find(temp);
    68.         if(it==mp.end())
    69.         {
    70.             vis[temp]=0;
    71.             mp[temp]=r;
    72.         }
    73.         else
    74.         {
    75.             if(r>it->second)
    76.                 mp[temp]=r;
    77.         }
    78.     }
    79. /*
    80.     cout << "调试:\n";
    81.     for(auto val:mp)
    82.         cout << val.first.first << ' ' << val.first.second << ' ' << val.second << endl;
    83.         */
    84.     int res=0;
    85.     for(int i=0;i<m;++i)
    86.     {
    87.         scanf("%d%d%d",&x,&y,&r);
    88.         dfs_Trave(x,y,r);
    89.     }
    90.  
    91.     for(int i=0;i<n;++i)
    92.     {
    93.         auto temp=make_pair(cir[i].x,cir[i].y);
    94.         if(vis[temp]!=0)
    95.             ++res;
    96.     }
    97.     printf("%d\n",res);
    98.     return 0;
    99. }
    100.  
    101. void dfs(pair<pair<int,int>,int > index)
    102. {
    103.     int x=index.first.first,y=index.first.second,r=index.second;
    104.     vis[index.first]=1;
    105.     for(int l=x-r;l<=x+r;++l)
    106.         for(int s=y+r;s>=y-r;--s)
    107.         {
    108.             if(squ(r) >= squ(l-x) + squ(s-y))
    109.             {
    110.                 auto temp=make_pair(l,s);
    111.                 auto it=mp.find(temp);
    112.                 if(it!=mp.end())
    113.                 {
    114.                     if(vis[temp]==0)
    115.                         dfs(*it);
    116.                 }
    117.             }
    118.         }
    119.  
    120. }
    121.  
    122. void dfs_Trave(int x,int y,int r)
    123. {
    124.     for(int l=x-r;l<=x+r;++l)
    125.         for(int s=y+r;s>=y-r;--s)
    126.         {
    127.             if(squ(r) >= squ(l-x) + squ(s-y))
    128.             {
    129.                 auto temp=make_pair(l,s);
    130.                 auto it=mp.find(temp);
    131.                 if(it!=mp.end())
    132.                 {
    133.                     if(vis[temp]==0)
    134.                         dfs(*it);
    135.                 }
    136.             }
    137.         }
    138. }

    第八个，/**
        将坐标转换为一个long long数值，存在unorder_map中；
        acwing通过了6/11；
    */

    1. /**
    2.     将坐标转换为一个long long数值，存在unorder_map中；
    3.     acwing通过了6/11；
    4. */
    5.  
    6. #include <iostream>
    7. #include <cstdio>
    8. #include <cmath>
    9. #include <vector>
    10. #include <string>
    11. #include <unordered_map>
    12. using namespace std;
    13.  
    14. typedef long long LL;
    15. LL squ(int x)
    16. {
    17.     return (LL) x*x;
    18. }
    19. const int maxn=50010,inf=1e9;
    20.  
    21. LL hash_val(int x,int y)
    22. {
    23.     return x*(inf+1ll)+y;
    24. }
    25. /*
    26. struct cmp
    27. {
    28.     bool operator()(pair<int,int> const &p) const
    29.     {
    30.         return p.first<p.second;
    31.     }
    32. };
    33. */
    34. //struct cmp
    35. //{
    36. //    std::size_t operator()(const std::pair<int, int>& p) const {
    37. //        return p.first ^ p.second;
    38. //    }
    39. //};
    40.  
    41. //struct cmp
    42. //{
    43. //    int operator()(const LL, int>& p) const {
    44. //        return p.first < p.second;
    45. //    }
    46. //};
    47. //struct Node
    48. //{
    49. //    int x,y,r;
    50. //}cir[maxn];
    51. vector<LL> cir;
    52. unordered_map<LL,int> mp;
    53. unordered_map<LL,int> vis;
    54. int n,m;
    55. void dfs_Trave(int x,int y,int r);
    56. void dfs(int x,int y,int r);
    57. int main()
    58. {
    59.  
    60. //    int a=123456789,b=123456;
    61. //    int c=a&b;
    62. //    cout << c << endl;
    63.  
    64. //    int a=123456789,b=45612;
    65. //    cout << hash_val(a,b) << endl;
    66.  
    67.     scanf("%d%d",&n,&m);
    68.     int x,y,r;
    69.     for(int i=0;i<n;++i)
    70.     {
    71.         scanf("%d%d%d",&x,&y,&r);
    72.         //cir[i]={x,y,r};
    73.         LL temp=hash_val(x,y);
    74.         //string temp=to_string(val);
    75.         cir.push_back(temp);
    76. //        mp[temp]=r;
    77. //        vis[temp]=0;
    78.         auto it=mp.find(temp);
    79.         if(it==mp.end())
    80.         {
    81.             vis[temp]=0;
    82.             mp[temp]=r;
    83.         }
    84.         else
    85.         {
    86.             if(r>it->second)
    87.                 mp[temp]=r;
    88.         }
    89.     }
    90.  
    91. //    cout << "调试:\n";
    92. //    for(auto val:mp)
    93. //        cout << val.first << ' ' << val.second  << endl;
    94. //    cout << "\ntiaoshi\n";
    95. //    for(auto a:vis)
    96. //        cout << a.first << ' ' << a.second << endl;
    97.     int res=0;
    98.     for(int i=0;i<m;++i)
    99.     {
    100.         scanf("%d%d%d",&x,&y,&r);
    101.         dfs_Trave(x,y,r);
    102.     }
    103.  
    104. //    cout << "\ntiaoshi2:\n";
    105. //    for(auto a:vis)
    106. //        cout << a.first << ' ' << a.second << endl;
    107.     for(int i=0;i<n;++i)
    108.     {
    109.         auto temp=cir[i];
    110.         if(vis[temp]!=0)
    111.             ++res;
    112.     }
    113.     printf("%d\n",res);
    114.     return 0;
    115. }
    116.  
    117. void dfs(int x,int y,int r)
    118. {
    119.     LL val=hash_val(x,y);
    120.    // int x=index.first.first,y=index.first.second,r=index.second;
    121.     vis[val]=1;
    122.     for(int l=x-r;l<=x+r;++l)
    123.         for(int s=y+r;s>=y-r;--s)
    124.         {
    125.             if(squ(r) >= squ(l-x) + squ(s-y))
    126.             {
    127.                 auto temp=hash_val(l,s);
    128.                 auto it=mp.find(temp);
    129.                 if(it!=mp.end())
    130.                 {
    131.                     if(vis[temp]==0)
    132.                         dfs(l,s,it->second);
    133.                 }
    134.             }
    135.         }
    136.  
    137. }
    138.  
    139. void dfs_Trave(int x,int y,int r)
    140. {
    141.     for(int l=x-r;l<=x+r;++l)
    142.         for(int s=y+r;s>=y-r;--s)
    143.         {
    144.             if(squ(r) >= squ(l-x) + squ(s-y))
    145.             {
    146.                 LL temp=hash_val(l,s);
    147.                 //string temp=to_string(val);
    148.                 auto it=mp.find(temp);
    149.                 if(it!=mp.end())
    150.                 {
    151.                     if(vis[temp]==0)
    152.                         dfs(l,s,it->second);
    153.                 }
    154.             }
    155.         }
    156. }

    第九个，

    /**
        将坐标转换为string，存在unordered_map中
        在acwing只能过4/11；

    */

    1. /**
    2.     将坐标转换为string，存在unordered_map中
    3.     在acwing只能过4/11；
    5. */
    6.  
    7. #include <iostream>
    8. #include <cstdio>
    9. #include <cmath>
    10. #include <vector>
    11. #include <string>
    12. #include <unordered_map>
    13. using namespace std;
    14.  
    15. typedef long long LL;
    16. LL squ(int x)
    17. {
    18.     return (LL) x*x;
    19. }
    20. const int maxn=50010,inf=1e9;
    21.  
    22. LL hash_val(int x)
    23. {
    24.     return x*(inf+1ll);
    25. }
    26. /*
    27. struct cmp
    28. {
    29.     bool operator()(pair<int,int> const &p) const
    30.     {
    31.         return p.first<p.second;
    32.     }
    33. };
    34. */
    35. //struct cmp
    36. //{
    37. //    std::size_t operator()(const std::pair<int, int>& p) const {
    38. //        return p.first ^ p.second;
    39. //    }
    40. //};
    41.  
    42. //struct cmp
    43. //{
    44. //    int operator()(const LL, int>& p) const {
    45. //        return p.first < p.second;
    46. //    }
    47. //};
    48. //struct Node
    49. //{
    50. //    int x,y,r;
    51. //}cir[maxn];
    52. vector<string> cir;
    53. unordered_map<string,int> mp;
    54. unordered_map<string,int> vis;
    55. int n,m;
    56. void dfs_Trave(int x,int y,int r);
    57. void dfs(int x,int y,int r);
    58. int main()
    59. {
    60. //    int a=123456789,b=123456;
    61. //    int c=a&b;
    62. //    cout << c << endl;
    63.  
    64. //    int a=123456789,b=45612;
    65. //    cout << hash_val(a,b) << endl;
    66.  
    67. //    int a=122,b=456;
    68. //    string s=to_string(a) +' ' +to_string(b);
    69. //    cout << s << endl;
    70.     scanf("%d%d",&n,&m);
    71.     int x,y,r;
    72.     for(int i=0;i<n;++i)
    73.     {
    74.         scanf("%d%d%d",&x,&y,&r);
    75.         //cir[i]={x,y,r};
    76.         LL val=hash_val(x);
    77.         string temp=to_string(val)+' ' +to_string(y);
    78.         cir.push_back(temp);
    79. //        mp[temp]=r;
    80. //        vis[temp]=0;
    81.         auto it=mp.find(temp);
    82.         if(it==mp.end())
    83.         {
    84.             vis[temp]=0;
    85.             mp[temp]=r;
    86.         }
    87.         else
    88.         {
    89.             if(r>it->second)
    90.                 mp[temp]=r;
    91.         }
    92.     }
    93.  
    94. //    cout << "调试:\n";
    95. //    for(auto val:mp)
    96. //        cout << val.first << ' ' << val.second  << endl;
    97. //    cout << "\ntiaoshi\n";
    98. //    for(auto a:vis)
    99. //        cout << a.first << ' ' << a.second << endl;
    100.     int res=0;
    101.     for(int i=0;i<m;++i)
    102.     {
    103.         scanf("%d%d%d",&x,&y,&r);
    104.         dfs_Trave(x,y,r);
    105.     }
    106.  
    107. //    cout << "\ntiaoshi2:\n";
    108. //    for(auto a:vis)
    109. //        cout << a.first << ' ' << a.second << endl;
    110.     for(int i=0;i<n;++i)
    111.     {
    112.         auto temp=cir[i];
    113.         if(vis[temp]!=0)
    114.             ++res;
    115.     }
    116.     printf("%d\n",res);
    117.     return 0;
    118. }
    119.  
    120. void dfs(int x,int y,int r)
    121. {
    122.     LL val=hash_val(x);
    123.     string temp=to_string(val) +' ' + to_string(y);
    124.    // int x=index.first.first,y=index.first.second,r=index.second;
    125.     vis[temp]=1;
    126.     for(int l=x-r;l<=x+r;++l)
    127.         for(int s=y+r;s>=y-r;--s)
    128.         {
    129.             if(squ(r) >= squ(l-x) + squ(s-y))
    130.             {
    131.                 LL val=hash_val(l);
    132.                 string temp=to_string(val)+' ' +to_string(s);
    133.                 auto it=mp.find(temp);
    134.                 if(it!=mp.end())
    135.                 {
    136.                     if(vis[temp]==0)
    137.                         dfs(l,s,it->second);
    138.                 }
    139.             }
    140.         }
    141.  
    142. }
    143.  
    144. void dfs_Trave(int x,int y,int r)
    145. {
    146.     for(int l=x-r;l<=x+r;++l)
    147.         for(int s=y+r;s>=y-r;--s)
    148.         {
    149.             if(squ(r) >= squ(l-x) + squ(s-y))
    150.             {
    151.                 LL val=hash_val(l);
    152.                 string temp=to_string(val)+' ' + to_string(s);
    153.                 auto it=mp.find(temp);
    154.                 if(it!=mp.end())
    155.                 {
    156.                     if(vis[temp]==0)
    157.                         dfs(l,s,it->second);
    158.                 }
    159.             }
    160.         }
    161. }

    第十个，/**
        dfs实现图的遍历
        手写hash表：把每个点唯一表示一个值，然后存到一个数组中，由于最大值为1e9，
        所以可以把x坐标乘以一个(1e9+1)+y的坐标表示一个long long 值，也不会溢出，
        即表示为一个两位的进制数，不过这个进制是1e9+1；
        能AC;
    */

    1. /**
    2.     dfs实现图的遍历
    3.     手写hash表：把每个点唯一表示一个值，然后存到一个数组中，由于最大值为1e9，
    4.     所以可以把x坐标乘以一个(1e9+1)+y的坐标表示一个long long 值，也不会溢出，
    5.     即表示为一个两位的进制数，不过这个进制是1e9+1；
    6.     能AC;
    7. */
    8. #include <iostream>
    9. #include <cstdio>
    10. #include <vector>
    11. #include <cmath>
    12. #include <cstring>
    13. using namespace std;
    14.  
    15. const int maxn=1e9,mod=7000003;
    16. int test=999997;    //测试数是否为素数
    17. typedef long long LL;
    18. struct Node
    19. {
    20.     int x,y,r;
    21. }cir[mod];
    22. LL hs[mod]={0};
    23. int id[mod]={0},vis[mod]={0};
    24. int m,n;
    25. void dfs(int x,int y,int r);
    26. void dfs_Trave(int x,int y,int r);
    27. LL hash_val(int x,int y)    //将二维坐标转换为一个hash值
    28. {
    29.     return (maxn+1ll)*x+y;
    30. }
    31.  
    32. int hash_key(int x,int y)
    33. {
    34.     LL val=hash_val(x,y);
    35.     int k=1,flag=-1;
    36.     int key=(val%mod+mod)%mod;
    37.     while(hs[key]!=-1&&hs[key]!=val)    //此处需要hs[key]!=key,因为后面需要查找用到二维坐标，
    38.     {                                   //返回一个key值
    39.         key+=k*k*flag;  //由于一个坐标最开始对应的key值也许被其他坐标占用了，这就需要查找
    40.         ++k;            //一个没被用到的值，但考虑到一个值一个值的加，元素容易扎堆都被使用了，
    41.         flag*=-1;       //于是我们就用平方探查法来查找
    42.         key=(key%mod+mod)%mod;  //防止出现负值
    43.     }
    44.     return key;
    45. }
    46.  
    47. LL squ(int x)
    48. {
    49.     return (LL) x*x;
    50. }
    51.  
    52. void is_primer(int n)
    53. {
    54.     for(int i=2;i<=sqrt(n);++i)
    55.         if(n%i==0)
    56.         {
    57.             cout << " not is primer ;\n";
    58.             return;
    59.         }
    60.     cout << "is primer\n";
    61.     return;
    62. }
    63.  
    64. int main()
    65. {
    66.     is_primer(test);
    67.     memset(hs,-1,sizeof(hs));
    68.     scanf("%d%d",&n,&m);
    69.     int x,y,r;
    70.     for(int i=0;i<n;++i)
    71.     {
    72.         scanf("%d%d%d",&x,&y,&r);
    73.         cir[i]={x,y,r};
    74.         auto key=hash_key(x,y);
    75.         if(hs[key]==-1) //这一个if语句需不需要都行
    76.             hs[key]=hash_val(x,y);
    77.         if(!id[key]||r>id[key]) //如果id[key]第一次被使用，或者此点的半径比之前的大，
    78.             id[key]=r;          //那么更新这个点的半径
    79.     }
    80.  
    81.     int res=0;
    82.     for(int i=0;i<m;++i)
    83.     {
    84.         scanf("%d%d%d",&x,&y,&r);
    85.         dfs_Trave(x,y,r);
    86.     }
    87.  
    88.     for(int i=0;i<n;++i)
    89.     {
    90.         auto key=hash_key(cir[i].x,cir[i].y);
    91.         if(vis[key]!=0)
    92.             ++res;
    93.     }
    94.     printf("%d\n",res);
    95.     return 0;
    96. }
    97.  
    98. void dfs(int x,int y,int r)
    99. {
    100.     int key=hash_key(x,y);
    101.     vis[key]=1;
    102.     for(int l=x-r;l<=x+r;++l)   //遍历（x，y）周围可以炸到的所有点
    103.         for(int s=y+r;s>=y-r;--s)
    104.         {
    105.             if(squ(r) >= squ(l-x) + squ(s-y))
    106.             {
    107.                 int key=hash_key(l,s);
    108.                 if(hs[key]!=-1) //如果这个点处有炸弹
    109.                 {
    110.                     if(vis[key]==0) //如果这个点处的炸弹没被拆除掉
    111.                         dfs(l,s,id[key]);
    112.                 }
    113.             }
    114.         }
    115.  
    116. }
    117.  
    118. void dfs_Trave(int x,int y,int r)
    119. {
    120.     for(int l=x-r;l<=x+r;++l)   //遍历（x，y）周围可以炸到的所有点
    121.         for(int s=y+r;s>=y-r;--s)
    122.         {
    123.             if(squ(r) >= squ(l-x) + squ(s-y))
    124.             {
    125.                 int key=hash_key(l,s);
    126.                 if(hs[key]!=-1) //如果这个点处有炸弹
    127.                 {
    128.                     if(vis[key]==0) //如果这个点处的炸弹没被拆除掉
    129.                         dfs(l,s,id[key]);
    130.                 }
    131.             }
    132.         }
    133. }

    第十一个， 用BFS实现图的遍历，
        手写hash表：把每个点唯一表示一个值，然后存到一个数组中，由于最大值为1e9，
        所以可以把x坐标乘以一个(1e9+1)+y的坐标表示一个long long 值，也不会溢出，
        即表示为一个两位的进制数，不过这个进制是1e9+1；
        true coding，能AC

    值得一提的是，vis[key]应当在进入bfs的队列便更新这个值已被访问，否则取出一个坐标的时候再更新，会导致一个点多次入队，浪费许多时间，acwing上最后一组数据超时，问题便出现在这儿

    其实算法笔记讲解BFS的时候就已经强调了inq表示结点是否入队，而不是是否访问，这和DFS的vis数组是有区别的，当是还不以为然，觉得自己都理解了，现在想想，亦是惭愧！书你倒是看了，但你是否真正的吸收了呢？每学到一个算法，就要去找相应的题目来做，不然你也只是白白浪费时间，多了不说，算法笔记上的树状数组以及lowbit数组你现在是否还能知道它们的意思，KMP算法是否还有印象，快速排序是否还能写出来，组合数的知识还知道多少。。。等等，不光是低头做题，还得总结自己学到的东西，以后遇到能够用自己学过的算法解决的题目的时候，别两眼一蹬，我不会？那就从此处开始，把之前写的算法发成博客吧，也能再温习一遍。

    1.  
    2. /**
    3.     用BFS实现图的遍历，
    4.     手写hash表：把每个点唯一表示一个值，然后存到一个数组中，由于最大值为1e9，
    5.     所以可以把x坐标乘以一个(1e9+1)+y的坐标表示一个long long 值，也不会溢出，
    6.     即表示为一个两位的进制数，不过这个进制是1e9+1；
    7.     true coding，能AC
    8. */
    9. /**
    10. #include <iostream>
    11. #include <cstdio>
    12. #include <vector>
    13. #include <queue>
    14. #include <cmath>
    15. #include <cstring>
    16. using namespace std;
    17.  
    18. const int maxn=1e9,mod=700001,ne=50010;
    19. int test=700001;    //测试数是否为素数
    20. typedef long long LL;
    21. struct Node
    22. {
    23.     int x,y,r;
    24. }cir[ne];
    25. LL hs[mod]={0};
    26. int id[mod]={0},vis[mod]={0};
    27. int m,n;
    28. void bfs(Node zd);
    29. void bfs_Trave(int x,int y,int r);
    30. LL hash_val(int x,int y)    //将二维坐标转换为一个hash值
    31. {
    32.     return (maxn+1ll)*x+y;
    33. }
    34.  
    35. int hash_key(int x,int y)
    36. {
    37.     LL val=hash_val(x,y);
    38.     int k=1,flag=-1;
    39.     int key=(val%mod+mod)%mod;
    40.     while(hs[key]!=-1&&hs[key]!=val)    //此处需要hs[key]!=key,因为后面需要查找用到二维坐标，
    41.     {                                   //返回一个key值
    42.         key+=k*k*flag;  //由于一个坐标最开始对应的key值也许被其他坐标占用了，这就需要查找
    43.         ++k;            //一个没被用到的值，但考虑到一个值一个值的加，元素容易扎堆都被使用了，
    44.         flag*=-1;       //于是我们就用平方探查法来查找
    45.         key=(key%mod+mod)%mod;  //防止出现负值
    46.     }
    47.     return key;
    48. }
    49.  
    50. LL squ(int x)
    51. {
    52.     return (LL) x*x;
    53. }
    54.  
    55. void is_primer(int n)
    56. {
    57.     for(int i=2;i<=sqrt(n);++i)
    58.         if(n%i==0)
    59.         {
    60.             cout << " not is primer ;\n";
    61.             return;
    62.         }
    63.     cout << "is primer\n";
    64.     return;
    65. }
    66.  
    67. int main()
    68. {
    69.     //is_primer(test);
    70.     memset(hs,-1,sizeof(hs));
    71.     scanf("%d%d",&n,&m);
    72.     int x,y,r;
    73.     for(int i=0;i<n;++i)
    74.     {
    75.         scanf("%d%d%d",&x,&y,&r);
    76.         cir[i]={x,y,r};
    77.         auto key=hash_key(x,y);
    78.         if(hs[key]==-1) //这一个if语句需不需要都行
    79.             hs[key]=hash_val(x,y);
    80.         if(!id[key]||r>id[key]) //如果id[key]第一次被使用，或者此点的半径比之前的大，
    81.             id[key]=r;          //那么更新这个点的半径
    82.     }
    83.  
    84.     int res=0;
    85.     for(int i=0;i<m;++i)
    86.     {
    87.         scanf("%d%d%d",&x,&y,&r);
    88.         bfs_Trave(x,y,r);
    89.     }
    90.  
    91.     for(int i=0;i<n;++i)
    92.     {
    93.         auto key=hash_key(cir[i].x,cir[i].y);
    94.         if(vis[key]!=0)
    95.             ++res;
    96.     }
    97.     printf("%d\n",res);
    98.     return 0;
    99. }
    100.  
    101. void bfs(Node zd)
    102. {
    103.     queue<Node> q;
    104.     q.push(zd);
    105.     while(!q.empty())
    106.     {
    107.         Node temp=q.front();
    108.         int x=temp.x,y=temp.y,r=temp.r;
    109.         q.pop();
    110.         int key=hash_key(x,y);
    111.        // vis[key]=1;
    112.         for(int l=x-r;l<=x+r;++l)   //遍历（x，y）周围可以炸到的所有点
    113.             for(int s=y+r;s>=y-r;--s)
    114.             {
    115.                 if(squ(r) >= squ(l-x) + squ(s-y))
    116.                 {
    117.                     int key=hash_key(l,s);
    118.                     if(hs[key]!=-1) //如果这个点处有炸弹
    119.                     {
    120.                         if(vis[key]==0) //如果这个点处的炸弹没被拆除掉
    121.                         {
    122.                             q.push({l,s,id[key]});
    123.                             vis[key]=1; //值得一提的是，vis[key]应当在进入bfs的队列便更新这个值已被访问
    124.                         }               //，否则取出一个坐标的时候再更新，会导致一个点多次入队
    125.                     }                   //，浪费许多时间，acwing上最后一组数据超时，问题便出现在这儿
    126.                 }
    127.             }
    128.     }
    129.  
    130. }
    131.  
    132. void bfs_Trave(int x,int y,int r)
    133. {
    134.     for(int l=x-r;l<=x+r;++l)   //遍历（x，y）周围可以炸到的所有点
    135.         for(int s=y+r;s>=y-r;--s)
    136.         {
    137.             if(squ(r) >= squ(l-x) + squ(s-y))
    138.             {
    139.                 int key=hash_key(l,s);
    140.                 if(hs[key]!=-1) //如果这个点处有炸弹
    141.                 {
    142.                     if(vis[key]==0) //如果这个点处的炸弹没被拆除掉
    143.                     {
    144.                         vis[key]=1;
    145.                         bfs({l,s,id[key]});
    146.                     }
    147.                 }
    148.             }
    149.         }
    150. }
    151. */

    最后一个代码，是acwing上看的，因为我写的BFS始终由一组数据通不过，便对照着他的写，但还是有一组数据通不过，根本原因还是BFS入队的时候便要更新坐标已入队，否则会造成一个点多次入队，这一点必须谨记。和上一个一个代码唯一的不同便是这个id数组记录的是cir数组的下标，也就是存储在cir数组里的下标，上一个id存储的相同点的最大半径。

    1. /**借鉴正确代码
    2. */
    4. /**
    5. #include <iostream>
    6. #include <cstdio>
    7. #include <vector>
    8. #include <queue>
    9. #include <cmath>
    10. #include <cstring>
    11. using namespace std;
    12.  
    13. const int maxn=1e9,mod=1e6 + 7,ne=50010;
    14. int test=700001;    //测试数是否为素数
    15. typedef long long LL;
    16. struct Node
    17. {
    18.     int x,y,r;
    19. }cir[ne];
    20. LL hs[mod]={0};
    21. int id[mod]={0};    //id存储的是坐标在数组cir中对应的下标
    22. bool vis[ne]={0};
    23. int m,n;
    24. void bfs(int index);
    25. void bfs_Trave(int x,int y,int r);
    26. LL hash_val(int x,int y)    //将二维坐标转换为一个hash值
    27. {
    28.     return (maxn+1ll)*x+y;
    29. }
    30.  
    31. int hash_key(int x,int y)
    32. {
    33.     LL val=hash_val(x,y);
    34.     int key=(val%mod+mod)%mod;
    35.     while(hs[key]!=-1&&hs[key]!=val)    //此处需要hs[key]!=key,因为后面需要查找用到二维坐标，
    36.     {                                   //返回一个key值
    37.        key++;
    38.         if(key == mod) key = 0;  //防止出现负值
    39.     }
    40.     return key;
    41. }
    42.  
    43. LL squ(int x)
    44. {
    45.     return (LL) x*x;
    46. }
    47.  
    48.  
    49. int main()
    50. {
    51.     memset(hs,-1,sizeof(hs));
    52.     scanf("%d%d",&n,&m);
    53.     int x,y,r;
    54.     for(int i=1;i<=n;++i)
    55.     {
    56.         scanf("%d%d%d",&x,&y,&r);
    57.         cir[i]={x,y,r};
    58.         auto key=hash_key(x,y);
    59.         if(hs[key]==-1) //这一个if语句需不需要都行
    60.             hs[key]=hash_val(x,y);
    61.         if(!id[key]||r>cir[id[key]].r) //如果id[key]第一次被使用，或者此点的半径比之前的大，
    62.             id[key]=i;          //那么更新这个点的坐标下标
    63.     }
    64.  
    65.     int res=0;
    66.     for(int i=0;i<m;++i)
    67.     {
    68.         scanf("%d%d%d",&x,&y,&r);
    69.         bfs_Trave(x,y,r);
    70.     }
    71.  
    72.     for(int i=1;i<=n;++i)
    73.     {
    74.         auto key=hash_key(cir[i].x,cir[i].y);
    75.         int pos=id[key];
    76.         if(pos&&vis[pos])
    77.             ++res;
    78.     }
    79.     printf("%d\n",res);
    80.     return 0;
    81. }
    82.  
    83. void bfs(int index)
    84. {
    85.     queue<int> q;
    86.     q.push(index);
    87.     vis[index]=1;
    88.     while(!q.empty())
    89.     {
    90.         int temp=q.front();
    91.         int x=cir[temp].x,y=cir[temp].y,r=cir[temp].r;
    92.         q.pop();
    93.         //int key=hash_key(x,y);
    94.         //vis[temp]=1;  //在这儿将temp号的值赋为1便是错的，不知道原因
    95.         for(int l=x-r;l<=x+r;++l)   //遍历（x，y）周围可以炸到的所有点
    96.             for(int s=y+r;s>=y-r;--s)
    97.             {
    98.                 if(squ(r) >= squ(l-x) + squ(s-y))
    99.                 {
    100.                     int key=hash_key(l,s);
    101.                     if(id[key]&&!vis[id[key]]) //如果这个点处有炸弹
    102.                     {
    103.                         int pos=id[key];//如果这个点处的炸弹没被拆除掉
    104.                             q.push(pos);
    105.                             vis[pos]=1;
    106.                     }
    107.                 }
    108.             }
    109.     }
    110.  
    111. }
    112.  
    113. void bfs_Trave(int x,int y,int r)
    114. {
    115.     for(int l=x-r;l<=x+r;++l)   //遍历（x，y）周围可以炸到的所有点
    116.         for(int s=y+r;s>=y-r;--s)
    117.         {
    118.             if(squ(r) >= squ(l-x) + squ(s-y))
    119.             {
    120.                 int key=hash_key(l,s);
    121.                 if(id[key]&&!vis[id[key]]) //如果这个点处有炸弹
    122.                 {                    //如果这个点处的炸弹没被拆除掉
    123.                         bfs(id[key]);
    124.                 }
    125.             }
    126.         }
    127. }

  • 相关阅读:
    【数据结构】栈
    计算机网络-第六章 应用层（1）
    【附源码】Python计算机毕业设计芮城县十全十美火锅店点餐系统
    java八股文面试[设计模式]——结构型模式
    python的jira库的调用简单记录
    分享一份 .NET Core 简单的自带日志系统配置，平时做一些测试或个人代码研究，用它就可以了
    计算机操作系统
    14Maven与Tomcat面试题
    linux下mv命令移动目录的二种情况
    Java 入门笔记
  • 原文地址：https://blog.csdn.net/qq_51825761/article/details/125476155