当前位置：首页 > news >正文

数据结构优化DP总结

news 来源：原创 2025/5/9 0:33:52

单调栈：Codeforces Round 622 (Div. 2) C2. Skyscrapers (hard version)

简单来讲就是最后需要呈现出一个单峰数组，使得总高度最高。

最开始想到暴力枚举每一个元素都充当最高的“单峰”，但是这里的 n 过大，这样枚举肯定会TLE。

那就考虑能不能单调线性的考虑每个元素作为最高点的时候的解是多少呢？

这里就需要借助我们的 单调栈，维护一个单调递增的序列：

这里仅以正序遍历为例：f[i]表示的是以i为单峰时1 — i 所有数组能产生的最大贡献，根据单调栈的性质，stk.top()就是上一个最近的小于 a[i] 的元素的下标，所以加上这中间所有的楼产生的贡献（由于单调栈的性质，这段中所有大于a[i] 的元素一定会被弹出，同时减去他们之前产生的贡献）。

#include<bits/stdc++.h>using namespace std;#define int long longsigned main() {int n, sum = 0;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];}stack<int> stk;vector<int> f(n + 1, 0);sum = 0;for (int i = 1; i <= n; i++) {while(stk.size() && a[stk.top()] >= a[i]) {//先弹出所有大于a[i]的楼的下标，因为保证要单增int j = stk.top();stk.pop();sum -= (j - (stk.empty() ? 0 : stk.top())) * a[j];// 减去这些楼之前所产生的贡献}sum += (i - (stk.empty() ? 0 : stk.top())) * a[i]; //加上目前这栋楼所产生的贡献stk.push(i);f[i] += sum;}sum = 0;while(!stk.empty()) stk.pop(); for (int i = n; i >= 1; i--) {while(stk.size() && a[stk.top()] >= a[i]) {int j = stk.top();stk.pop();sum -= ((stk.empty() ? n + 1 : stk.top()) - j) * a[j];}sum += ((stk.empty() ? n + 1 : stk.top()) - i) * a[i];stk.push(i);f[i] += sum - a[i];}auto p = max_element(f.begin() + 1, f.end()) - f.begin();//cout << p << endl;for (int i = p - 1; i >= 1; i--) {a[i] = min(a[i], a[i + 1]);}for (int i = p + 1; i <= n; i++) {a[i] = min(a[i], a[i - 1]);}for (int i = 1; i <= n; i++) {cout << a[i] << " \n"[i == n];}return 0;
}

建议先熟练掌握单调栈再来理解这题。

树状数组：Codeforces Round 1013 (Div. 3) F. Igor and Mountain

其实也不一定需要树状数组，用前缀和也能达到一样的效果，只是树状数组比较好写，不费脑子。

简单来说就是如果暴力枚举转移的话会超时，所以就需要记录下整个区间的某种贡献，然后一起转移，这样就可以省下很多的时间。

i64 mod = 998244353;double get_dist(int a, int b, int c, int d) {double dx = fabs(a - c);double dy = fabs(b - d);return sqrt(dx * dx + dy * dy);
}template <typename T>
class Fenwick {
public:int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n + 1, T{});}void add(int x, const T &v) {for (int i = x; i <= n; i += i & -i) {a[i] = (a[i] + v % mod + mod) % mod;}}// 查询位置 [1, x] 的前缀和T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = (ans + a[i] % mod + mod) % mod;}return ans;}// 查询区间 [l, r] 的区间和T rangeSum(int l, int r) {return (sum(r) - sum(l - 1) + mod) % mod;}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i] <= k) {x += i;cur = cur + a[x];}}return x;}
};void solve()
{int n, m, d1, d2;cin >> n >> m >> d1;for (int i = 0; i <= d1; i++) {if(i * i + 1 <= d1 * d1) {d2 = i;}}vector<string> g(n + 1);for (int i = 1; i <= n; i++) {cin >> g[i];g[i] = ' ' + g[i];}int ans = 0;vector<Fenwick<int>> f(n + 1, Fenwick<int>(m + 1)), nf(f);for (int j = 1; j <= m; j++) {if (g[n][j] == 'X') {f[n].add(j, 1);}}for (int j = 1; j <= m; j++) {if (g[n][j] == 'X') {nf[n].add(j, f[n].rangeSum(max(1LL, j - d1), min(j + d1, m)));}}// for (int j = 1; j <= m; j++) {//     cout << nf[n].rangeSum(j, j) << ' ';// }// cout << endl;for (int i = n - 1; i >= 1; i--) {for (int j = 1; j <= m; j++) {if (g[i][j] == 'X') {f[i].add(j, nf[i + 1].rangeSum(max(1LL, j - d2), min(j + d2, m)));}}for (int j = 1; j <= m; j++) {if (g[i][j] == 'X') {nf[i].add(j, f[i].rangeSum(max(1LL, j - d1), min(j + d1, m)));}}}ans = nf[1].sum(m);cout << (ans + mod) % mod << endl;
}

数据结构优化DP总结

单调栈：Codeforces Round 622 (Div. 2) C2. Skyscrapers (hard version) 简单来讲就是最后需要呈现出一个单峰数组，使得总高度最高。最开始想到暴力枚举每一个元素都充当最高的“单峰”，但是这里的 n 过大，这样枚举肯定会TLE。 …...

编程日记 2025/5/9 0:33:52

Linux网络相关概念和重要知识（4）（序列化和反序列化、TCP协议、会话和守护进程）

目录 1.序列化和反序列化 （1）为什么需要序列化 （2）序列化方案 ①json ②json序列化代码模板 ③json反序列化代码模板 ④将自定义方案和json结合 2.TCP协议（传输控制协议） （1&#xff09…...

编程日记 2025/5/8 22:49:20

[MySQL初阶]MySQL数据库基础

MySQL数据库基础 1. 数据库基础1.1 什么是数据库1.2 主流数据库2. 数据库的基本使用2.1 连接服务器2.2 使用案例2.3 数据逻辑存储3. MySQL架构与分类3.1 MySQL架构3.2 SQL分类4. 存储引擎4.1 存储引擎基本概念4.2 存储引擎基本操作1. 数据库基础 1.1 什么是数据库存储数据用…...

编程日记 2025/5/8 22:33:35

【mysql 的安装及使用】

MySQL 9.0 一、下载MySQL[MySQL 9.0 下载] [(https://dev.mysql.com/downloads/mysql/)选择自定义，选择合适安装路径二、检查安装情况配置环境变量打开命令行查看版本创建数据库在MySQL中，可以使用create database语句来创建数据库。以下是创建一个名为my_db的数据库的示例：…...

编程日记 2025/5/8 22:43:20

d202542

一、142.环形链表I 142. 环形链表 II - 力扣（LeetCode） 用set统计一下如果再次出现那么就环的第一个return返回就行 public ListNode detectCycle(ListNode head) {Set<ListNode> set new HashSet<>();ListNode cur head;while(cur ! …...

编程日记 2025/5/8 23:05:52

vscode代码片段的设置与使用

在 Visual Studio Code (VS Code) 中，可以通过自定义**代码片段（Snippets）**快速插入常用代码模板。以下是详细设置步骤： 步骤 1：打开代码片段设置按下快捷键 Ctrl Shift P（Windows/Linux）或…...

编程日记 2025/5/8 23:13:09

3D 地图渲染-区域纹理图添加

引入-初始化地图（关键代码） // 初始化页面引入高德 webapi -- index.html 文件 <script src https://webapi.amap.com/maps?v2.0&key您申请的key值></script>// 添加地图容器 <div idcontainer ></div>// 地图初始化应该…...

编程日记 2025/5/8 23:32:13

spring-security原理与应用系列：HttpSecurity.filters

目录 AnyRequestMatcher WebSecurityConfig HttpSecurity AbstractInterceptUrlConfigurer AbstractAuthenticationProcessingFilter 类图在前面的文章《spring-security原理与应用系列：securityFilterChainBuilders》中，我们遗留了一个问题&…...

编程日记 2025/5/8 23:18:00

每日总结4.2

蓝桥杯刷题： 1. 方格分割（dfs,选中心点，开始上下左右遍历，达到边界时数量加一） #include <bits/stdc.h> using namespace std; bool vis[10][10]; int mp[10][10]; int ans0; int dx[4]{1,0,0,-1}; int dy[4]{…...

编程日记 2025/5/8 23:18:00

架构师面试（二十五）：分布式存储 Leader 设计

问题在非常多的分布式存储系统中，如：Zookeeper、Etcd、Kafka等，往往会存在一个【Leader】角色，并由该角色负责数据的写入，这样设计最主要的原因是什么呢？ A. 唯一负责数据写入的 Leader 角色可以避免并…...

编程日记 2025/5/8 23:49:29

文章目录 MyCat分片规则详解1. rule1 (基于id的func1算法)2. sharding-by-date (按日期分片)3. rule2 (基于user_id的func1算法)4. sharding-by-intfile (基于枚举值分片)5. auto-sharding-long (长整型范围分片)6. mod-long (取模分片)7. sharding-by-murmur (MurmurHash分片)…...

编程日记 2025/5/8 23:20:58

系统分析师备考启动

以考促学：软件高级系统分析师。一、考试目的： 1、练习三遍读书法、快速阅读、番茄工作法、第一性原理、思维导图等学习方法和学习工具的使用。 2、掌握知识、编织知识网、顺便拿证。二、组织形式： 小组统一安排学习内容，每…...

编程日记 2025/5/8 17:12:41

轻量级搜索接口技术解析：快速实现关键词检索的Java/Python实践

Hi，你好！ 轻量级搜索接口技术解析：快速实现关键词检索的Java/Python实践接口特性与适用场景本接口适用于需要快速集成搜索能力的开发场景，支持通过关键词获取结构化搜索结果。典型应用场景包括： 垂直领域信息检索…...

编程日记 2025/5/8 23:15:00

防爆风扇选型指南：根据风量风压匹配应用场景

在化工、石油、煤矿等存在易燃易爆气体或粉尘的危险环境中，通风设备的安全性能至关重要，防爆风扇成为保障生产环境安全与空气流通的关键装备。正确选型是确保其发挥最佳效能的前提，而根据风量风压匹配应用场景则是选型的核心要点。风量&am…...

编程日记 2025/5/8 23:38:09

Laravel 中使用 JWT 作用户登录，身份认证

什么是JWT： JWT 全名 JSON Web Token，是一种开放标准 (RFC 7519)。用于在网络应用环境间安全地传输信息作为 JSON 对象。它是一种轻量级的认证和授权机制，特别适合分布式系统的身份验证。核心特点紧凑格式：体积小&#x…...

编程日记 2025/5/6 16:02:15

Git安装

1、下载Git https://git-scm.com/ 2、双击【Git-2.44.0-64-bit.exe】安装： 2-1、选择自定义安装目录：F:\software\Git 2-2、一直点击next，直到安装成功。 2-3、在git项目文件夹，右键出现Git GUI Here和Git Bash Here就说明成…...

编程日记 2025/5/8 23:08:51

bit与byte的区别与联系？

李升伟整理 byte 和 bit 是计算机中常用的数据单位，它们的主要区别和联系如下： 1. 定义 bit（比特）：计算机中最小的数据单位，表示一个二进制位，值为0或1。 byte（字节&#xff09…...

编程日记 2025/5/3 10:39:44

程序化广告行业（51/89）：Cookie映射与移动设备ID映射解析

程序化广告行业（51/89）：Cookie映射与移动设备ID映射解析在当今数字化营销的浪潮中，程序化广告已经成为企业精准触达目标客户的重要手段。作为一名对程序化广告充满兴趣的学习者，我希望通过这篇博客和大家一起深入探索…...

编程日记 2025/5/8 23:42:24

从吉卜力漫画到艺术创造：GPT-4o多种风格绘图Prompt大全

在3月底，GPT-4o掀起了一阵吉卜力绘图浪潮，大家纷纷输入一张图片，让4o模型进行风格化迁移，其中吉卜力风格的漫画在社交媒体上最为火热。在大家争议4o的训练数据是否侵权和4o背后的技术原理的时候，我们先来玩一玩&#x…...

编程日记 2025/5/8 23:29:39

48. 旋转图像

leetcode Hot 100系列文章目录一、核心操作二、外层配合操作三、核心模式代码总结一、核心操作先上下翻转再沿着对角线翻转提示：小白个人理解，如有错误敬请谅解！ 二、外层配合操作三、核心模式代码代码如下： class S…...

编程日记 2025/5/7 8:02:07

【Linux篇】自主Shell命令行解释器

📌 个人主页： 孙同学_ 🔧 文章专栏：Liunx 💡 关注我，分享经验，助你少走弯路！ 文章目录 1. 获取用户名的接口2. 等待用户输入接口3. 将上述代码进行面向对象式的封装4. 命令行解析5.…...

编程日记 2025/5/6 17:41:40

leetcode 2873. 有序三元组中的最大值 I

欢迎关注更多精彩关注我，学习常用算法与数据结构，一题多解，降维打击。文章目录题目描述题目剖析&信息挖掘解题思路方法一暴力枚举法思路注意复杂度代码实现方法二公式拆分动态规划思路注意复杂度代码实现题目描述 [2873] 有序三元…...

编程日记 2025/5/6 4:13:35

深度学习 Deep Learning 第14章自编码器

深度学习 Deep Learning 第14章自编码器内容概要本章深入探讨了自编码器（Autoencoders），这是一种用于特征学习和降维的神经网络架构。自编码器通过编码器和解码器两个部分，将输入数据映射到一个内部表示（编码&…...

编程日记 2025/5/9 0:30:59

全国产传感器的可靠性、MTBF计算、极限测试与加速寿命测试

全国产传感器的可靠性是指传感器在规定条件下和规定时间内完成规定功能的能力。它是衡量传感器性能的重要指标之一，直接影响传感器的使用寿命和系统稳定性。武汉利又德的小编来和大家分享一下关于全国产传感器的可靠性以及MTBF计算、极限测试与加速寿命测试的小知识…...

编程日记 2025/5/3 15:35:13

【算法中的数学】裴蜀定理（Bézout’s Identity）总结

裴蜀定理（Bzout’s Identity）总结裴蜀定理是数论中的一个重要定理，描述了整数线性组合与最大公约数（GCD）之间的关系。 1. 裴蜀定理的内容对于任意两个整数 a a a 和 b b b，设它们的最大公约数为 d …...

编程日记 2025/5/7 8:49:03

unity点击button后不松开通过拖拽显示模型松开后模型实例化

using System.Collections; using UnityEngine; using UnityEngine.EventSystems; using UnityEngine.UI;[RequireComponent(typeof(Button))] // 确保脚本挂在Button上 public class DragButtonSpawner : MonoBehaviour, IPointerDownHandler, IDragHandler, IPointerUpHandle…...

编程日记 2025/5/9 0:32:21

计算机网络复习吉林大学

1、信息交换的三种方式：电路交换，分组交换，报文交换。从通信资源的分配角度来看，交换就是按照某种方式动态地分配传输线路的资源。电路交换：（星形结构替代全连接） 电话交换机接通电话的方式…...

编程日记 2025/5/8 11:14:26

超级好用的小软件，连接电脑和手机。

将手机变成电脑摄像头的高效工具Iriun Webcam是一款多平台软件，能够将手机摄像头变成电脑的摄像头，通过简单的设置即可实现视频会议、直播、录制等功能。它支持Windows、Mac和Linux系统，同时兼容iOS和Android手机，操作简单&#x…...

编程日记 2025/4/27 11:14:24

【JavaScript】十三、事件监听与事件类型

文章目录 1、事件监听1.1 案例：击关闭顶部广告1.2 案例：随机点名1.3 事件监听的版本 2、事件类型2.1 鼠标事件2.1.1 语法2.1.2 案例：轮播图主动切换 2.2 焦点事件2.2.1 语法2.2.2 案例：模拟小米搜索框 2.3 键盘事件2.3.1 语法2.3.…...

编程日记 2025/5/2 21:33:15

微服务架构技术栈选型避坑指南：10大核心要素深度拆解

微服务架构的技术栈选型直接影响系统的稳定性、扩展性和可维护性。以下从10大核心要素出发，结合主流技术方案对比、兼容性评估、失败案例及优化策略，提供系统性选型指南。 1. 服务框架与通信关键考量点扩展性：框架需支持定制化扩展&#x…...

编程日记 2025/5/8 22:51:00

虚拟试衣间微信小程序解决方案

目录项目名称：云尚衣橱核心功能模块：技术栈选型：架构设计概览：详细功能点实现思路：数据库设计 (MongoDB 示例): 开发步骤建议：关键注意事项和挑战：项目名称：云尚衣橱核心功能模块：用户系统 (User System) 我的衣柜 (My Wardrobe) 虚拟试衣间 (Vir…...

编程日记 2025/5/9 0:20:51

C++STL——容器-vector(含部分模拟实现，即地层实现原理）(含迭代器失效问题）

目录容器——vector 1.构造模拟实现 2.迭代器模拟实现： 编辑 3.容量模拟实现： 4.元素的访问模拟实现 5.元素的增删查改迭代器失效问题： 思考问题【注】：这里的模拟实现所写的参数以及返回值，都是…...

编程日记 2025/5/6 4:46:14

MoLe-VLA：通过混合层实现的动态跳层视觉-语言-动作模型实现高效机器人操作

25年3月来自南京大学、香港理工、北大和香港科技大学的论文“MoLe-VLA: Dynamic Layer-skipping Vision Language Action Model via Mixture-of-Layers for Efficient Robot Manipulation”。多模态大语言模型 (MLLM) 在理解复杂语言和视觉数据方面表现出色，使通用…...

编程日记 2025/5/6 23:27:45

《数字图像处理》教材寻找合作者

Rafael Gonzalez和Richard Woods所著的《数字图像处理》关于滤波器的部分几乎全错，完全从零开始写，困难重重。关于他的问题已经描述在《数字图像处理（面向新工科的电工电子信息基础课程系列教材）》。现寻找能够共同讨论、切磋、…...

编程日记 2025/5/7 0:31:43

uni-app 框架调用蓝牙，获取 iBeacon 定位信标的数据，实现室内定位场景

背景：最近需要对接了一个叫 iBeacon 定位信标硬件设备，这个设备主要的作用是，在信号不好的地方，或者室内实现定位，准确的找到某个东西。就比如地下停车场，商城里，我们想知道这个停车场的某个…...

编程日记 2025/5/6 17:33:00

Java面试黄金宝典29

1. 什么是普通索引和唯一性索引定义： 普通索引：是最基本的索引类型，它为数据表中的某一列或多列建立索引，以加快数据的查询速度。它不限制索引列的值重复，允许存在多个相同的值。唯一性索引：在普通索引的基…...

编程日记 2025/5/8 14:10:36

C语言常见3种排序

主要是三种排序方法：冒泡排序、选择排序、插入排序。文章目录一、冒泡排序 1.代码： 2.工作原理： 3.具体过程： 二、选择排序 1.代码 2. 工作原理 3.具体过程： 三、插入排序 1.代码 2.工作原理 3.具体过程总结一、…...

编程日记 2025/4/29 8:15:14

Nyquist插件基础：LISP语法-自定义函数

1 Nyquist插件基础：LISP语法-自定义函数在 Nyquist 里，自定义函数能够让你把特定的操作封装起来，实现代码复用和逻辑模块化。下面详细介绍如何在 Nyquist 中定义和使用自定义函数。 1.1.1 1. 基本函数定义在 Nyquist 中使用 defun 来定义…...

编程日记 2025/5/6 13:16:14

Visual-RFT：视觉强化微调

文章目录速览摘要1. 引言2. 相关工作大型视觉语言模型（LVLMs）强化学习 3. 方法3.1. 初步带可验证奖励的强化学习DeepSeek R1-Zero和GRPO 3.2. Visual-RFT3.2.1. 视觉感知中的可验证奖励检测任务中的IoU奖励分类任务中的CLS奖励 3.2.2 数据准备 4. 实验4…...

编程日记 2025/5/6 14:11:45

快速入手-基于DRF的过滤、分页、查询配置（十五）

1、过滤需要安装插件 pip install django-filter 2、注册 INSTALLED_APPS [ "django.contrib.admin", "django.contrib.auth", "django.contrib.contenttypes", "django.contrib.sessions", "django.contrib.messages",…...

编程日记 2025/5/8 15:47:51

gcc 链接顺序，静态库循环依赖问题

链接过程由链接器 ld 负责。通常 GCC 间接驱动之。越底层的库，在链接命令行中的位置应越靠后。文章目录链接过程※ 但是对于静态库，链接器仅提取当前未解析符号所需的对象文件，未使用的对象文件会被丢弃。静态库（.a&#xff09…...

编程日记 2025/4/7 17:11:38

linux内核漏洞检测利用exp提权

案例一dirtycow（CVE-2016-5159） 有个前置知识就是获取liunx的内核 hostnamectl uname -a 然后这个内核漏洞进行提权的步骤也是和手工win进行提权差不多也是需要使用辅助工具在本地进行辅助检测然后去nomi-sec/PoC-in-GitHub： &#…...

编程日记 2025/5/3 17:14:12

【学Rust写CAD】21 2D 点(point.rs)

源码 //matrix/point.rs use std::ops::Mul; use super::algebraic_units::{Zero, One}; use super::generic::Matrix;/// 点坐标结构体 #[derive(Debug, Clone, Copy, PartialEq)] pub struct Point<X, Y>(Matrix<X, Y, One, Zero, Zero, One>);impl<X, Y>…...

编程日记 2025/5/5 12:12:00

Jmeter的压测使用

Jmeter基础功能回顾一、创建Jmeter脚本 1、录制新建 （1）适用群体：初学者 2、手动创建 （1）需要了解Jmeter的常用组件元件：多个类似功能组件的容器（类似于类） 各元件作用组件…...

编程日记 2025/5/6 5:15:17

C语言--统计输入字符串中的单词个数

输入输入：大小写字母以及空格，单词以空格分隔输出：单词个数代码如果不是空格且inWord0说明是进入单词的第一个字母，则单词总数加一。如果是空格，证明离开单词，inWord 0。 #include <stdio.h&g…...

编程日记 2025/5/6 22:28:30

《雷神之锤 III 竞技场》快速求平方根倒数的计算探究

1. 《雷神之锤 III 竞技场》快速求平方根导数源代码此处先列出其源代码，这段代码的目标是计算一个浮点数平方根的导数，也就是如下形式： f ( x ) 1 x f(x) \frac{1}{\sqrt{x}} f(x)x 1这段代码可以说非常难以理解，尤其是 …...

编程日记 2025/4/29 9:00:00

深入解析 Java 8 Function 接口：函数式编程的核心工具

精心整理了最新的面试资料和简历模板，有需要的可以自行获取点击前往百度网盘获取点击前往夸克网盘获取 Java 8 引入的 java.util.function.Function 接口是函数式编程范式的核心组件之一，本文将全面解析其使用方法，并通过丰富的代码示例演…...

编程日记 2025/5/8 13:54:37

软件重构与项目进度的矛盾如何解决

软件重构与项目进度之间的矛盾可以通过明确重构目标与范围、采用渐进式重构策略、优化项目管理流程、提高团队沟通效率、建立重构意识文化等方式解决。其中，采用渐进式重构策略尤为关键。渐进式重构是指在日常开发过程中，以小步骤持续进行重构&#xff0…...

编程日记 2025/5/7 5:40:37

redis的geo结构实现[附近商铺]功能

先上结论 geo地理位置算出来是不准的实现思路 redis6.2支持了经纬度数据格式支持经纬度检索需要将redis升级否则会报错不支持命令 pom文件如果spring-data-redis是2.7.9的boot版本则要改一下支持geo: <dependency><groupId>org.springframework.boot</g…...

编程日记 2025/4/30 20:40:42

单调栈：Codeforces Round 622 (Div. 2) C2. Skyscrapers (hard version)

树状数组：Codeforces Round 1013 (Div. 3) F. Igor and Mountain

相关文章：