• 【基本算法题-2022.7.31】12. 激光炸弹


    每日一题包含七大板块,现在从最基本的算法题开始,此类题型包括位运算、递推、递归、二分、排序、贪心等,从简单到复杂,跟我一起从点滴积累,到最终一举成名,打遍天下!✨


    💻基本算法题12. 激光炸弹

    地图上有 N 个目标,用整数 Xi,Yi 表示目标在地图上的位置,每个目标都有一个价值 Wi。

    注意: 不同目标可能在同一位置。

    现在有一种新型的激光炸弹,可以摧毁一个包含 R×R 个位置的正方形内的所有目标。

    激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 x,y 轴平行。

    求一颗炸弹最多能炸掉地图上总价值为多少的目标。

    输入格式
    第一行输入正整数 N 和 R,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。

    接下来 N 行,每行输入一组数据,每组数据包括三个整数 Xi,Yi,Wi,分别代表目标的 x 坐标,y 坐标和价值,数据用空格隔开。

    输出格式
    输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。

    数据范围
    0≤R≤109
    0 0≤Xi,Yi≤5000
    0≤Wi≤1000

    输入样例:

    2 1
    0 0 1
    1 1 1
    
    • 1
    • 2
    • 3

    输出样例:

    1
    
    • 1

    🍀题解 — 二维前缀和

    一维前缀和

    对于一个数列,如果要计算任一区间内所有数字的和,可以暴力枚举该区间内每个数字并相加,其时间复杂度为O(N)。

    前缀和,顾名思义就是第几个数之前的数之和,可以使用DP来预处理(复杂度O(N)),dp[i]表示到第i个数(包括它自身)为止前面所有数的和,从而得出状态转移方程dp[i+1] = dp[i] + num[i+1]num[i+1]表示数组中第i+1个数字。这样要计算闭区间[i,j]的和就是dp[j]-dp[i-1] DP预处理后计算复杂度O(1))。

    二维前缀和

    建立在一维前缀和的基础上,如果要求一个矩阵内任意一个子矩阵中所有数字之和,就可以使用二维前缀和。此处还是使用DP进行预处理,dp[i][j]表示矩阵起始点与(i,j)两点之间所组成的矩阵内所有数字之和。也就是说二维前缀和实际上就是二维数组上的前缀和了。一维数组的前缀和也是一个一维数组,同样地,二维数组的前缀和也是一个二维的数组。

    可以得出dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[i][j]

    本题详细思路可以对照注释进行理解。

    📝代码展示

    #include 
    #include 
    #define x first
    #define y second
    using namespace std;
    typedef long long LL;
    typedef pair<LL, LL> PLL;
    
    PLL calc(LL n, LL m) {
        if(n == 0) return {0, 0};
        LL len = 1ll << (n - 1); // n - 1级图构成n级图平移时的单位长度
        LL cnt = 1ll << (n - 1) * 2; // n - 1级图中所含的元素个数
        LL cnk = m / cnt; // 在n级图中,编号为m的元素所属块的编号
        LL idx = m % cnt; // 在n级图中,编号为m的元素在所属块中的编号
        PLL pos = calc(n - 1, idx); // 在n级图中,编号为m的元素在所属块中的坐标
        LL x = pos.x, y = pos.y;
        // 根据n级图中某个块的编号和这个块中某个元素的坐标,确定n - 1级图的坐标变换
        // 注意:离散坐标系跟实数坐标系有些许差别,不考虑这些差别
        // 结果必然是抓耳挠腮。hh
        if(cnk == 0) return {y, x}; // 没有平移,虽是旋转,坐标关系容易确定
        if(cnk == 1) return {x, y + len}; // 单纯平移
        if(cnk == 2) return {x + len, y + len}; // 单纯平移
        if(cnk == 3) return {len * 2 - y - 1, len - x - 1}; // 旋转又平移
    }
    
    LL rounding(double a) {
        LL b;
        if(a > 0) b = (a * 2 + 1) / 2;
        else b = (a * 2 - 1) / 2;  
        return b;
    }
    
    int main() {
        int times;
        cin >> times;
        while(times--) {
            LL n, a, b;
            cin >> n >> a >> b;
            PLL pa = calc(n, a - 1);
            PLL pb = calc(n, b - 1);
            //double x = pa.x - pb.x, y = pa.y - pb.y;
            //printf("%.0lf\n", sqrt(x * x + y * y) * 10.00);
            LL x = pa.x - pb.x, y = pa.y - pb.y;
            double dist = sqrt(x * x + y * y);
            cout << rounding(dist) << endl;
        }
        return 0;
    }
    
    • 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

    在这里插入图片描述

    【🎯知识点:深入理解二维前缀和】

    在这里插入图片描述
    从上图中可以看出,前缀和数组里每一个位置都表示原数组当前index左上方的数字的和。
    比如像图里面画的:prefixSum[3, 3] = src[0~2, 0~2]的和;
    二维前缀和数组要怎么计算出来呢?
    可以分为四种情况

    1. i ==0 && j == 0,只有一个直接赋值即可:prefixSum[0, 0] = src[0, 0]。
    2. i==0,最左边的一排,图中黄色部分,prefixSum[0, j] = prefixSum[0, j-1] + src[0, j];
    3. j==0,最上面一排,途中红色部分,prefixSum[i, o] = prefixSum[i-1, 0] + src[i, 0];
    4. i!=0 || j!=0,图中绿色部分,prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] + src[i][j] - prefixSum[i - 1][j - 1];

    持续更新,喜欢的话欢迎点赞👍、收藏⭐️+关注✌️哟~

  • 相关阅读:
    为何数据库也云原生了?
    基于拟蒙特卡洛模拟法的随机潮流计算matlab程序
    Redis 的大 Key 对持久化有什么影响?
    std::integer_sequence 源码分析
    【Ascend310】【Mindspore】安装mindspore后无法进行跑通样例
    【路径规划-PRM路径规划】基于RRT算法避障路径规划附完整matlab代码
    所有 Windows 用户请注意:该高危零日漏洞已被利用 7 周
    写了一个javaScript数据类型判断的工具(npm--genius-type)
    pytest测试框架使用基础08 通过Yaml实现数据驱动
    【Rust】——Vector集合
  • 原文地址:https://blog.csdn.net/weixin_46020266/article/details/126090127