差分前缀和题目集

简介: 差分前缀和题目集

1.一维前缀和


sum[i]=sum[i-1] + a[i];


1.P5638 【CSGRound2】光骓者的荣耀

2.P2671 NOIP2015 普及组 求和(前缀和数组应用)

求和题解


2.二维前缀和(处理矩形的面积的权值)


sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];(只用一个数组,防止爆空间)


1.P1719 最大加权矩形(二维前缀和遍历所有矩形)

2.P2004 领地选择(二维前缀和遍历固定大小矩形)

3.P2280 [HNOI2003]激光炸弹

(二维前缀和遍历固定大小矩形,把每一个坐标看作矩形的一个块)


3.一维差分


i 到 j  加 k
cf[i]+=k;
cf[j+1]-=k;
sum[i]=sum[i-1]+cf[i];


1.P3397 地毯(差分数组)

2.P3406 海底高铁(实际问题应用)

3.P2879 [USACO07JAN] Tallest Cow S(实际问题应用)

4.P4552 [Poetize6] IncDec Sequence


目录
相关文章
|
安全 Java Android开发
构建高效安卓应用:探究Kotlin与Java的性能对比
【2月更文挑战第22天】 在移动开发的世界中,性能优化一直是开发者们追求的关键目标。随着Kotlin在安卓开发中的普及,许多团队面临是否采用Kotlin替代Java的决策。本文将深入探讨Kotlin和Java在安卓平台上的性能差异,通过实证分析和基准测试,揭示两种语言在编译效率、运行时性能以及内存占用方面的表现。我们还将讨论Kotlin的一些高级特性如何为性能优化提供新的可能性。
696 0
|
安全 Linux PHP
轻松搭建Linux宝塔面板并实现公网访问Discuz论坛,让您的论坛更具吸引力
轻松搭建Linux宝塔面板并实现公网访问Discuz论坛,让您的论坛更具吸引力
|
网络协议 网络安全
Ansible模块介绍——防火墙模块
Ansible模块介绍——防火墙模块
442 0
|
Web App开发 移动开发 前端开发
技术经验分享:canvas+howler.js解决同页面视频、音频同时播放问题
技术经验分享:canvas+howler.js解决同页面视频、音频同时播放问题
409 0
|
10月前
|
Dart 搜索推荐 IDE
Windows下Zed编辑器配置Dart环境
本文介绍了Dart编程语言及其主要框架Flutter的优势,并推荐使用轻量级编辑器Zed进行Dart开发。详细步骤包括Dart环境的安装与配置,Zed编辑器的安装与个性化设置,以及如何在Zed中编写并运行Dart的HelloWorld程序。通过自定义任务实现Dart文件的快速运行,提高了开发效率。
Pyqt5--属性动画-文本移动(Pyside6适用)
Pyqt5--属性动画-文本移动(Pyside6适用)
466 1
Pyqt5--属性动画-文本移动(Pyside6适用)
|
分布式计算 DataWorks Java
MaxCompute操作报错合集之DataWorks中udf开发完后,报错了,如何解决
MaxCompute是阿里云提供的大规模离线数据处理服务,用于大数据分析、挖掘和报表生成等场景。在使用MaxCompute进行数据处理时,可能会遇到各种操作报错。以下是一些常见的MaxCompute操作报错及其可能的原因与解决措施的合集。
|
人工智能 运维 Kubernetes
带你读《云原生架构白皮书2022新版》——云原生技术中台 CNStack 产品家族
带你读《云原生架构白皮书2022新版》——云原生技术中台 CNStack 产品家族
563 72
|
存储 Windows
windows server 2019 云服务器看不见硬盘的解决方案
windows server 2019 云服务器看不见硬盘的解决方案
464 0
|
安全 应用服务中间件 Linux
Centos 7.2搭建局域网yum源
Centos 7.2搭建局域网yum源
475 0