• 扫雷（蓝桥杯）

    题目描述

    小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下， 在一个二维平面上放置着 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，表示一个排雷火箭的信息。      

    输出一个整数表示答案。

    样例输入

    2 1
2 2 4
4 4 2
0 0 5

    样例输出

    2

    提示

    示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2 也被排除。

    蓝桥杯2022年第十三届省赛真题扫雷

    对于 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. 

    第一种

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

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #define int long long
    7. using namespace std;
    8. const int N=5e3+10;
    9. bool st[N];
    10. int n,m;
    11. //存炸弹
    12. struct node
    13. {
    14. 	int x,y,r;
    15. }stu[N];
    16. vector<int>v[N];
    17. //判断是否在这颗雷是否在这个圆
    18. bool sqr(int x,int y,int xx,int yy,int r)
    19. {
    20. 	if((xx-x)*(xx-x)+(yy-y)*(yy-y)<=r*r) return true;
    21. 	return false;
    22. }
    23. //连成一个连通图 雷在这个雷的范围内的就扩展
    24. void add(int idx)
    25. {
    26. 	int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r;
    27. 	for(int i=1;i<=n;i++)
    28. 	{
    29. 		if(i!=idx)
    30. 		{
    31. 			if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);
    32. 		}
    33. 	}
    34. }
    35. //看有多少颗符合要求的炸弹
    36. int dfs(int idx)
    37. {
    38. 	int sum=1;
    39. 	st[idx]=1;
    40. 	for(int i=0;isize();i++)
    41. 	{
    42. 		int j=v[idx][i];
    43. 		if(!st[j])
    44. 		{
    45. 			st[j]=1;
    46. 		 sum+=dfs(j);
    47. 		}
    48. 	}
    49. 	return sum;
    50. }
    51. //计算这颗排雷火箭能炸多少地雷
    52. int dfs_Trave(int x,int y,int r)
    53. {
    54. 	int sum=0;
    55. 	for(int i=1;i<=n;i++)
    56. 	{
    57. 		if(sqr(stu[i].x,stu[i].y,x,y,r))
    58. 		{
    59. 			if(!st[i])
    60. 			sum+=dfs(i);
    61. 		}
    62. 	}
    63. 	return sum;
    64. }
    65. signed main()
    66. {
    67. 	cin>>n>>m;
    68. 	for(int i=1;i<=n;i++)
    69. 	{
    70. 		int x,y,r;cin>>x>>y>>r;
    71. 		stu[i]={x,y,r};
    72. 	}
    73. 	for(int i=1;i<=n;i++)
    74. 	{
    75. 		add(i);
    76. 	}
    77. 	int sum=0;
    78. 	for(int i=1;i<=m;i++)
    79. 	{
    80. 		int x,y,r;cin>>x>>y>>r;
    81. 		sum+=dfs_Trave(x,y,r);
    82. 	}
    83. 	cout<
    84. 	return 0;
    85. }

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

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #define int long long
    9. using namespace std;
    10. typedef pair<int,int>PII;
    11. const int N=5e4+10;
    12. bool st[N];
    13. mapint>mp;
    14. int n,m,n1=0;
    15. //存炸弹
    16. struct node
    17. {
    18. 	int x,y,r,cnt;
    19.     bool operator < (node const & a) const
    20.     {
    21.         if(x!=a.x)
    22.             return x
    23.         return y
    24.     }
    25. }stu[N];
    26. /*
    27. bool cmp(node xx,node yy)
    28. {
    29. 	if(xx.x==yy.x) return xx.y
    30. 	return xx.x
    31. }*/
    32. vector<int>v[N];
    33. //判断是否在这颗雷是否在这个圆
    34. bool sqr(int x,int y,int xx,int yy,int r)
    35. {
    36. 	if((xx-x)*(xx-x)+(yy-y)*(yy-y)<=r*r) return true;
    37. 	return false;
    38. }
    39. //连成一个连通图 雷在这个雷的范围内的就扩展
    40. void add(int idx)
    41. {
    42. 	int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r;
    43. 	for(int i=idx-1;i>=0;i--)
    44. 	{
    45. 		if(r<(x-stu[i].x)) break;
    46. 		if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);
    47. 	}
    48. 	for(int i=idx+1;i<=n1;i++)
    49. 	{
    50. 		if(r<(stu[i].x-x)) break;
    51. 		if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);
    52. 	}
    53. }
    54. //看有多少颗符合要求的炸弹
    55. int dfs(int idx)
    56. {
    57. 	int sum=stu[idx].cnt;
    58. 	st[idx]=1;
    59. 	for(int i=0;isize();i++)
    60. 	{
    61. 		int j=v[idx][i];
    62. 		if(!st[j])
    63. 		{
    64. 			st[j]=1;
    65. 		 sum+=dfs(j);
    66. 		}
    67. 	}
    68. 	return sum;
    69. }
    70. //计算这颗排雷火箭能炸多少地雷
    71. int dfs_Trave(int x,int y,int r)
    72. {
    73. 	node e1={x-r,y,r,1},e2={x+r,y,r,1};
    74. 	int l1=lower_bound(stu+1,stu+1+n1,e1)-stu;
    75. 	int r1=upper_bound(stu+1,stu+1+n1,e2)-stu;
    76. 	int sum=0;
    77. 	for(int i=l1;i<=r1;i++)
    78. 	{
    79. 		if(sqr(stu[i].x,stu[i].y,x,y,r))
    80. 		{
    81. 			if(!st[i])
    82. 			sum+=dfs(i);
    83. 		}
    84. 	}
    85. 	return sum;
    86. }
    87. signed main()
    88. {
    89. 	cin>>n>>m;
    90. 	for(int i=1;i<=n;i++)
    91. 	{
    92. 		int x,y,r;cin>>x>>y>>r;
    93. 		int id=mp[{x,y}];
    94. 		if(id!=0)
    95. 		{
    96. 			stu[id].r=max(stu[id].r,r);
    97. 			stu[id].cnt++;
    98. 		}
    99. 		else
    100. 		{
    101. 			int xx=1;
    102. 		    n1++;
    103. 		    stu[n1].x=x;
    104. 		    stu[n1].y=y;
    105. 		    stu[n1].r=r;
    106. 		    stu[n1].cnt=1;
    107. 			mp[{x,y}]=n1;
    108. 		}
    109. 	}
    110. 	sort(stu+1,stu+1+n1);
    111. 	for(int i=1;i<=n1;i++)
    112. 	{
    113. 		add(i);
    114. 	}
    115. 	int sum=0;
    116. 	for(int i=1;i<=m;i++)
    117. 	{
    118. 		int x,y,r;cin>>x>>y>>r;
    119. 		sum+=dfs_Trave(x,y,r);
    120. 	}
    121. 	cout<
    122. 	return 0;
    123. }

    第二种

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

    AC版

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #define int long long
    9. using namespace std;
    10. typedef pair<int,int>PII;
    11. const int N=5e4+10;
    12. mapint>mp;
    13. bool st[N];
    14. vector<int>v[N];
    15. int n,m,n1;
    16. struct node
    17. {
    18. 	int x,y,r,num;
    19. 	bool operator < (node const &a) const
    20. 	{
    21. 		if(x!=a.x) return x
    22. 		return y
    23. 	}
    24. }stu[N];
    25. bool sqr(int x1,int y1,int x2,int y2,int r)
    26. {
    27. 	if((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<=r*r) return true;
    28. 	return false;
    29. }
    30. void add(int idx)
    31. {
    32. 	int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r;
    33. 	for(int i=idx-1;i>=0;i--)
    34. 	{
    35. 		if(r<(x-stu[i].x)) break;
    36. 		if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);
    37. 	}
    38. 	for(int i=idx+1;i<=n1;i++)
    39. 	{
    40. 		if(r<(stu[i].x-x)) break;
    41. 		if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);
    42. 	}
    43. }
    44. int bfs(int idx)
    45. {
    46. 	int sum=stu[idx].num;
    47. 	queue<int>q;
    48. 	q.push(idx);
    49. 	st[idx]=1;
    50. 	while(q.size())
    51. 	{
    52. 		int t=q.front();
    53. 		q.pop();
    54. 		for(int i=0;isize();i++)
    55. 		{
    56. 			int j=v[t][i];
    57. 			if(!st[j])
    58. 			{
    59. 				st[j]=1;
    60. 				sum+=bfs(j);
    61. 			}
    62. 		}
    63. 	}
    64. 	return sum;
    65. }
    66. int bfs_Trave(int x,int y,int r)
    67. {
    68. 	node e1={x-r,y,r,1},e2={x+r,y,r,1};
    69. 	int l1=lower_bound(stu+1,stu+1+n1,e1)-stu;
    70. 	int r1=upper_bound(stu+1,stu+1+n1,e2)-stu;
    71. 	int sum=0;
    72. 	for(int i=l1;i<=r1;i++)
    73. 	{
    74. 		if(sqr(stu[i].x,stu[i].y,x,y,r))
    75. 		{
    76. 			if(!st[i])
    77. 			sum+=bfs(i);
    78. 		}
    79. 	}
    80. 	return sum;
    81. }
    82. signed main()
    83. {
    84.     cin>>n>>m;
    85.     for(int i=1;i<=n;i++)
    86. 	{
    87. 		int x,y,r;cin>>x>>y>>r;
    88. 		int xx=mp[{x,y}];
    89. 		if(xx!=0)
    90. 		{
    91. 			stu[xx].r=max(stu[xx].r,r);
    92. 			stu[xx].num++;
    93. 		}
    94. 		else
    95. 		{
    96. 		   n1++;
    97. 		   stu[n1]={x,y,r,1};
    98. 		   mp[{x,y}]=n1;
    99. 		}
    100. 	   }   
    101. 	   sort(stu+1,stu+1+n1);
    102. 	for(int i=1;i<=n1;i++)
    103. 	{
    104. 		add(i);
    105. 	}
    106. 	int sum=0;
    107. 	for(int i=0;i
    108. 	{
    109. 		int x,y,r;cin>>x>>y>>r;
    110. 		sum+=bfs_Trave(x,y,r);
    111. 	}
    112. 	cout<
    113. 	return 0;
    114. }

  • 相关阅读:
    数字孪生智慧工厂三维可视化系统解决方案，打造新一代智慧工厂
    python构造函数使print输出不同颜色的文本
    Python 使用OpenCV计算机视觉（一篇文章从零毕业）【附带停车场车位智能识别项目】预计7月初更新完毕
    FFmpeg进阶-给视频添加马赛克效果
    【Unity】苹果(IOS)开发证书保姆级申请教程
    如何使用大语言模型来绘制图画
    Hbase安装和使用
    使用WPS生成二维码，手机扫码访问主机的资源
    美国拒绝分享系统漏洞，中国打造首个桌面操作系统根社区应对
    Java-微服务-谷粒商城-1-环境搭建&项目初始化
  • 原文地址：https://blog.csdn.net/m0_74015873/article/details/137207344