JZOJ 1495. 宝石(附加扫描线讲解)

2024-03-02 08:10

本文主要是介绍JZOJ 1495. 宝石(附加扫描线讲解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

JZOJ 1495. 宝石

题目大意:给你N个 ( K + 1 ) × ( K + 1 ) (K+1)\times(K+1) (K+1)×(K+1)的正方形以及他们左上角的那个顶点的坐标和它的权值,求最大的覆盖的权值。
这一题可以用二维前缀和做,但是无法拿到满分。

满分做法:扫描线。

假如现在有这么两个长方形,权值都为1(不要问为什么是长方形,这里只是为了方便讲解而已),它们摆放如图:
在这里插入图片描述
首先,我们把所有竖着的线给找出来。
在这里插入图片描述
然后,我们就可以分别算出下面三个区域的最大覆盖权值了。
在这里插入图片描述
我们可以把所有的线按横坐标小到大排序,将这个几何图形分成了许多块,对于这一道题,我们可以这样计算:
在这里插入图片描述
绿色边表示在这段区间内加上该矩形的权值,红色边表示减去该矩形的权值。
按照横坐标先排序,然后依次进行这些操作。
我们可以用线段树来实现区间加法。
大家可以结合伪代码理解一下:

struct line{int x,l,r,k;
}l[N*2];
bool cmp(line a,line b)
{if(a.x==b.x) return a.k<b.k;else return a.x<b.x;
}
...
scanf("%d%d%d",&m,&n,&k);
for(int i=1;i<=n;i++)
{scanf("%d%d%d",&x,&y,&z);l[i*2-1]=(line){x,y,y+k,z};l[i*2]=(line){x+k+1,y,y+k,-z};
}
sort(l+1,l+2*n+1,cmp);

注意有n+n条线。
这里解释一下排序每一条线的时候为什么横坐标相等小的要在上面,因为这里需要减掉一些正方形的贡献,再加上一些正方形的贡献,如果先加上再减去的话会重复计算。
为了使代码更简洁,建议减去的时候改为加上该数的相反数。
然后每一次线段树做完区间修改的时候再查询一下整颗线段树内的最大值就可以啦。
操作&查询部分的代码

for(int i=1;i<=n+n;i++)
{sgt.change(1,m,1,l[i].l,l[i].r,l[i].k);if(sgt.tr[1]+sgt.lz[1]>ans) ans=sgt.tr[1]+sgt.lz[1];
}

其实就是整个的核心了。
每一次在这一条线所覆盖的区间内加上这一条线的权值。
然后这一题就可以AC了。
相信线段树实现区间加减和区间求最值大家都会。
然后给出完整的代码:

#include<cstdio>
#include<algorithm>
#define ls (now<<1)
#define rs (now<<1|1)
#define mid ((l+r)>>1)
#define N 50010
using namespace std;
struct line{int x,l,r,k;
}l[N*2];
struct segment_tree{long long tr[N*4],lz[N*4];void change(int l,int r,int now,int L,int R,int a){if(R<l||r<L) return;if(L<=l&&r<=R){lz[now]+=a;return;}change(l,mid,ls,L,R,a);change(mid+1,r,rs,L,R,a);tr[now]=max(tr[ls]+lz[ls],tr[rs]+lz[rs]);}
}sgt;
bool cmp(line a,line b)
{if(a.x==b.x) return a.k<b.k;else return a.x<b.x;
}
int n,m,k,x,y,z;
long long ans;
int main()
{scanf("%d%d%d",&m,&n,&k);for(int i=1;i<=n;i++){scanf("%d%d%d",&x,&y,&z);l[i*2-1]=(line){x,y,y+k,z};l[i*2]=(line){x+k+1,y,y+k,-z};}sort(l+1,l+2*n+1,cmp);for(int i=1;i<=n+n;i++){sgt.change(1,m,1,l[i].l,l[i].r,l[i].k);if(sgt.tr[1]+sgt.lz[1]>ans) ans=sgt.tr[1]+sgt.lz[1];}printf("%lld",ans);return 0;
}

这篇关于JZOJ 1495. 宝石(附加扫描线讲解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/765465

相关文章

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Java集合中的List超详细讲解

《Java集合中的List超详细讲解》本文详细介绍了Java集合框架中的List接口,包括其在集合中的位置、继承体系、常用操作和代码示例,以及不同实现类(如ArrayList、LinkedList和V... 目录一,List的继承体系二,List的常用操作及代码示例1,创建List实例2,增加元素3,访问元

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip?2. 什么是 -i 参数?二、国内镜像源的选择三、如何

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

Redis的Zset类型及相关命令详细讲解

《Redis的Zset类型及相关命令详细讲解》:本文主要介绍Redis的Zset类型及相关命令的相关资料,有序集合Zset是一种Redis数据结构,它类似于集合Set,但每个元素都有一个关联的分数... 目录Zset简介ZADDZCARDZCOUNTZRANGEZREVRANGEZRANGEBYSCOREZ

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

ispunct函数讲解 <ctype.h>头文件函数

目录 1.头文件函数 2.ispunct函数使用  小心!VS2022不可直接接触,否则..!没有这个必要,方源一把抓住VS2022,顷刻 炼化! 1.头文件函数 以上函数都需要包括头文件<ctype.h> ,其中包括 ispunct 函数 #include<ctype.h> 2.ispunct函数使用 简述: ispunct函数一种判断字符是否为标点符号的函

深度学习速通系列:深度学习算法讲解

深度学习算法是一系列基于人工神经网络的算法,它们通过模拟人脑处理信息的方式来学习和解决复杂问题。这些算法在图像识别、语音识别、自然语言处理、游戏等领域取得了显著的成就。以下是一些流行的深度学习算法及其基本原理: 1. 前馈神经网络(Feedforward Neural Networks, FNN) 原理:FNN 是最基本的神经网络结构,它由输入层、隐藏层和输出层组成。信息从输入层流向隐藏层,最