蓝桥杯每日一真题——[蓝桥杯 2022 省 B] 扫雷(dfs+二分)

这篇具有很好参考价值的文章主要介绍了蓝桥杯每日一真题——[蓝桥杯 2022 省 B] 扫雷(dfs+二分)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

[蓝桥杯 2022 省 B] 扫雷

题目描述

小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下,在一个二维平面上放置着 n n n 个炸雷,第 i i i 个炸雷 ( x i , y i , r i ) \left(x_{i}, y_{i}, r_{i}\right) (xi,yi,ri) 表示在坐标 ( x i , y i ) \left(x_{i}, y_{i}\right) (xi,yi) 处存在一个炸雷,它的爆炸范围是以半径为 r i r_{i} ri 的一个圆。

为了顺利通过这片土地,需要玩家进行排雷。玩家可以发射 m m m 个排雷火箭,小明已经规划好了每个排雷火箭的发射方向,第 j j j 个排雷火箭 ( x j , y j , r j ) \left(x_{j}, y_{j}, r_{j}\right) (xj,yj,rj) 表示这个排雷火箭将会在 ( x j , y j ) \left(x_{j}, y_{j}\right) (xj,yj) 处爆炸,它的爆炸范围是以半径为 r j r_{j} rj 的一个圆,在其爆炸范围内的炸雷会被引爆。同时,当炸雷被引爆时,在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷?

你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

输入格式

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

接下来的 n n n 行, 每行三个整数 x i , y i , r i x_{i}, y_{i}, r_{i} xi,yi,ri, 表示一个炸雷的信息。

再接下来的 m m m 行,每行三个整数 x j , y j , r j x_{j}, y_{j}, r_{j} xj,yj,rj, 表示一个排雷火箭的信息。

输出格式

输出一个整数表示答案。

样例

样例输入

2 1
2 2 4
4 4 2
0 0 5

样例输出

2

提示

【样例说明】

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

蓝桥杯每日一真题——[蓝桥杯 2022 省 B] 扫雷(dfs+二分)

【评测用例规模与约定】

对于 40 % 40 \% 40% 的评测用例: 0 ≤ x , y ≤ 1 0 9 , 0 ≤ n , m ≤ 1 0 3 , 1 ≤ r ≤ 10 0 \leq x, y \leq 10^{9}, 0 \leq n, m \leq 10^{3}, 1 \leq r \leq 10 0x,y109,0n,m103,1r10.

对于 100 % 100 \% 100% 的评测用例: 0 ≤ x , y ≤ 1 0 9 , 0 ≤ n , m ≤ 5 × 1 0 4 , 1 ≤ r ≤ 10 0 \leq x, y \leq 10^{9}, 0 \leq n, m \leq 5 \times 10^{4}, 1 \leq r \leq 10 0x,y109,0n,m5×104,1r10.

蓝桥杯 2022 省赛 B 组 H 题。

思路

1.这个一看就是一个深度优先遍历的题如果直接深度优先搜索做只能得40分,别问我怎么知道的。
2.这个题不能用并查集做,如果把那些老默跟着高启强干,不知道哪个老默就先死了(炸了),所以只能用深度优先遍历做
3.那么深度优先遍历就要减去一些范围我们知道这个玩意的x在小于x-r的范围上是肯定不会爆炸的,在大于x+r的范围上也是肯定不会爆炸的,所以排除掉这些以外的点进行深度优先遍历就行了,而找到边界值的最快的方法是二分查找所以这个题就有一下思路

· 1:输入数据,用结构体和数组存
struct boom
{
    long long x;
    long long y;
    long long r;
    bool zha;
};

struct huojian
{
    long long x;
    long long y;
    long long r;
};

int main()
{

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        boom b;
        cin >> b.x >> b.y >> b.r;
        b.zha = false;
        booms.push_back(b);
    }
    for (int i = 0; i < m; i++)
    {
        /* code */
        huojian h;
        cin >> h.x >> h.y >> h.r;
        huojians.push_back(h);
    }

· 2:sort一下变成有序,就可以用二分了;
bool cmp(boom b1, boom b2)
{
    return (b1.x < b2.x);
}
 sort(booms.begin(), booms.end(), cmp);

· 3:dfs遍历
void dfs(long long x, long long y, long long ri)
  for (int i = 0; i < m; i++)
    {
        dfs(huojians[i].x, huojians[i].y, huojians[i].r);
    }
    
· 4:在dfs遍历的同时进行二分操作缩小范围
long long lmid, rmid, l = 0, r = n - 1;
    // 找左边界左边界外的都排除掉
    while (l <= r)
    {
        lmid = (l + r) / 2; // 取中点
        // 把小于r的外面的炸弹排除掉先
        if (booms[lmid].x < x - ri)
        {
            l = lmid + 1;
        }
        else if (booms[lmid].x == x - ri)
        {
            break;
        }
        else
        {
            r = lmid - 1;
        }
    }
    lmid = l; // 确认左边界

    // 找右边界,右边界外的都排除掉
    l = 0, r = n-1;
    while (l <= r)
    {
        rmid = (l + r) / 2;
        if (booms[rmid].x < x + ri)
        {
            l = rmid + 1;
        }
        else if (booms[rmid].x == x + ri)
        {
            break;
        }
        
        else
        {
            r = rmid - 1;
        }
    }
    rmid = r;
注意

在使用sort的时候 sort(booms.begin(), booms.end(), cmp);如果用vector的话要这样写,如果按传统数组那样写会报错。

这个题的精髓就是要用二分缩小一下范围。

当然在考场上直接用dfs也能得到40分呢~~~~~~多良心···

全部代码:

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;
int n, m;

int res = 0;
struct boom
{
    long long x;
    long long y;
    long long r;
    bool zha;
};

struct huojian
{
    long long x;
    long long y;
    long long r;
};

vector<boom> booms;
vector<huojian> huojians;

double dis(double x1, double x2, double y1, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool cmp(boom b1, boom b2)
{
    return (b1.x < b2.x);
}

void dfs(long long x, long long y, long long ri)
{
    long long lmid, rmid, l = 0, r = n - 1;
    // 找左边界左边界外的都排除掉
    while (l <= r)
    {
        lmid = (l + r) / 2; // 取中点
        // 把小于r的外面的炸弹排除掉先
        if (booms[lmid].x < x - ri)
        {
            l = lmid + 1;
        }
        else if (booms[lmid].x == x - ri)
        {
            break;
        }
        else
        {
            r = lmid - 1;
        }
    }
    lmid = l; // 确认左边界

    // 找右边界,右边界外的都排除掉
    l = 0, r = n-1;//2023.3.30这里错了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    while (l <= r)
    {
        rmid = (l + r) / 2;
        if (booms[rmid].x < x + ri)
        {
            l = rmid + 1;
        }
        else if (booms[rmid].x == x + ri)
        {
            break;
        }
        
        else
        {
            r = rmid - 1;
        }
    }
    rmid = r;

    for (long long i = lmid; i <= rmid; i++)
    {
        if (!booms[i].zha && dis(booms[i].x, x, booms[i].y, y) <= ri)
        {
            booms[i].zha = true;
            res++;
            dfs(booms[i].x, booms[i].y, booms[i].r);
        }
    }
}

int main()
{

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        boom b;
        cin >> b.x >> b.y >> b.r;
        b.zha = false;
        booms.push_back(b);
    }
    for (int i = 0; i < m; i++)
    {
        /* code */
        huojian h;
        cin >> h.x >> h.y >> h.r;
        huojians.push_back(h);
    }
    sort(booms.begin(), booms.end(), cmp);

    for (int i = 0; i < m; i++)
    {
        dfs(huojians[i].x, huojians[i].y, huojians[i].r);
    }
    cout << res;
    system("pause");
}

如果数据不是那么水在圆的四个角角上的话,会超时的这时候就建议用哈希来做:

点击去看文章来源地址https://www.toymoban.com/news/detail-408352.html

到了这里,关于蓝桥杯每日一真题——[蓝桥杯 2022 省 B] 扫雷(dfs+二分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2022蓝桥杯C++B组国赛真题题解

    目录 A:2022 B:钟表 C:卡牌 D:最大数字 E:出差 F:费用报销 G:故障 H:机房 I:齿轮 J:搬砖 问题描述 将 2022 拆分成 10 个互不相同的正整数之和, 总共有多少种拆分方法? 注意交换顺序视为同一种方法, 例如 2022=1000+1022 和 1022+1000 就视为同一种方法。 答案提交 这是一道结果填空的

    2024年02月06日
    浏览(44)
  • 华为OD机试真题Java_2022-2023-题目0178-不含101的数

    小明在学习二进制时,发现了一类不含 101 101 101 的数, 也就是将数字用二进制表示,不能出现 101 101 101 。 现在给定一个正整数区间 [ l , r ] [l,r] [ l , r ] ,请问这个区间内包含了多少个不含 101 101 101 的数? 输入一行,包含两个正整数 l , r ( 1 ≤ l r ≤ 1 0 9 ) l,r (1 leq l r leq

    2024年02月05日
    浏览(46)
  • 题目3180:蓝桥杯2023年第十四届省赛真题-互质数的个数======及探讨互质专题

    https://www.dotcpp.com/oj/problem3162.html 已AC。 (1)首先大家要知道什么叫互质: 以及它们的性质: 在数论中,对正整数n,欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数(由高斯所命名)或是欧拉总计函数(totient fu

    2023年04月24日
    浏览(47)
  • 2022 第十四届蓝桥杯模拟赛第二期题目题解(比赛时使用方法)

    目录 第一题:最小的2022 第二题:经过天数 第三题:特殊的十六进制数 第四题:矩阵的最小路径 第五题:质数拆分 第六题:拷贝时间 第七题:单词去重 第八题:最短回文串 第九题:多少个X? 第十题:最小交换 问题描述 请找到一个大于 2022 的最小数,这个数转换成二进

    2023年04月11日
    浏览(71)
  • ​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第6天

    专题前瞻:复习并查集、Tire字符串、双指针、二分 目录 第一道真题(日志统计) 输出描述 输入输出样例 第二道真题(合根植物) 输出描述 输入输出样例 第三道模拟题(acwing):Trie字符串统计 第四道真题(扫地机器人) 题目描述 输出描述 按从小到大的顺序输出热帖 

    2023年04月08日
    浏览(36)
  • 【蓝桥杯】每日四道填空题(两道真题+两道模拟题)| 第四天

    专栏: 蓝桥杯——每日四道填空题(两道真题+两道模拟题) 离蓝桥杯已经不到一个月时间了,赶快刷起来吧,填空题一定别丢分!! ୧ ꒰•̀ᴗ•́꒱ ୨ 另一个专栏是: 蓝桥杯——编程题刷题营(每日四题,两道模拟,两道真题) 目录 第一道真题(2016年省赛):寒假作

    2023年04月08日
    浏览(45)
  • 《蓝桥杯真题》:2022单片机省赛第二场_客观题(第十三 / 13届第二场)

    声明:我仅是贴出我认为正确的答案,不是标准答案! 解析:打开ISP看到下面两个文件类型,我就选了 BC 解析:比赛给的《STC15系列单片机用户手册》P301,可以看到是可以位寻址的都能够被8整除,不能够被8整除的无法进行位操作,SCON的地址为98H,P4的地址为C0H,可以位寻址

    2023年04月08日
    浏览(53)
  • 最短路+二分题目整理

    题目链接 (qquad) 题目要求 最小化最大 费用,显然是使用二分答案,二分答案首先应该看 限制 和 目标 ,此处的限制是血量限制,而目标是费用目标。这种情况我们可以二分费用,然后在图上跑最短路判定血量是否满足。 (qquad) 对于 check 函数,我们去判定是否存在一条道

    2024年02月01日
    浏览(41)
  • 蓝桥杯:作物杂交 (DFS)

    目录 题目描述 输入描述 输出描述 输入输出样例 输入 输出 样例说明  思路(DFS): AC代码(Java): 题目链接         作物杂交是作物栽培中重要的一步。已知有 N种作物 (编号 1 至 N ),第 i 种作物从播种到成熟的时间为 Ti​。作物之间两两可以进行杂交,杂交时

    2023年04月08日
    浏览(38)
  • 蓝桥杯-dfs(一)

    本文主要是【算法】——dfs使用的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一句:狠狠沉淀,顶峰相见 整数n划分成k份的方案

    2024年01月22日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包