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

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

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