天津二十四格制作公司/青岛seo关键词排名
11.1总结
文章目录
- 11.1总结
- A. 集合
- 题目大意
- 考场思路
- B. 差后队列
- 题目大意
- 考场思路
- 正解
- C. 蛋糕
- 题目大意
- 考场思路
- 正解
- D. 字符替换
- 题目大意
- 考场思路
- 正解
- 总结
A. 集合
题目大意
给定一个长度为 n n n 的整数序列 a a a ,问该序列有多少个子区间满足这个区间内数值的最大字段和小于 k k k
1 ≤ n ≤ 2 ∗ 1 0 5 , k ≤ n 1\le n \le 2 *10^5 , k \le n 1≤n≤2∗105,k≤n
考场思路
设 r i r_i ri 为以 i i i 为左端点的最右边可以取到哪里。
显然 r i ≤ r i + 1 r_i \le r_{i + 1} ri≤ri+1,所以可以用一个双指针来处理。
用线段树来维护最大字段和,然后每次加入一个 j j j ,如果当前的最大字段和大于 k k k ,那么答案就加上 $ i - j$ ,每次再把 i i i 从线段树中删除就好了
B. 差后队列
题目大意
差后队列为一种数据结构,支持两种操作:
- push 插入一个数
- pop 随机删除一个 不是 最大值的数。如果只有一个数则删除该数
给定操作序列,求每次删的数的期望,以及每个数期望被删的时间,答案 m o d 998244353 \mod 998244353 mod998244353
1 ≤ n ≤ 1 0 6 1\le n \le 10^6 1≤n≤106
考场思路
对于 1 ≤ n ≤ 5000 1\le n \le 5000 1≤n≤5000 的数据
对于每个push,直接向后找到比它大的数,然后记录上到它被删除的期望。
就是前面都没有被删除的期望乘上这一次被删除的期望。
对于每个pop
求从上一次队列清空开始,到这次删除的数的期望
每次的数的期望就相当于对于每个在队列内的非最大值的数 n u m num num 乘上之前没被删掉的期望,再乘上这一次被删掉的期望。
暴力维护即可。
考场上打挂了,因为pop的情况不会处理
正解
跟上面的差不多
对于每次要删的数的期望。
每次从队列没有数开始单独处理。
-
如果当前只有一个数
那么直接删除就好了
-
否则
维护一个当前的最大值和当前数的数量,每次的数的期望就相当于对于每个在队列内的非最大值的数 n u m num num 乘上之前没被删掉的期望,再乘上这一次被删掉的期望。
对于每次数被删除的数的期望时间
维护一个类似于后缀和的东西。
从后往前开始,一个数的期望删除的时间就是这次被删除的期望加上这次没有被删除的期望乘上以后被删除的期望。
C. 蛋糕
题目大意
你现在得到了一个二维蛋糕,它从左到右可以分成 n n n 列,每列高为 a i a_i ai 。对于每一列,又可以从下到上分为 a i a_i ai 块,并且最上面一块权值为 1 1 1 ,从上到下权值依次加 。每一列的最上面的权值为 的块的上表面有“奶油”。
你现在要把这一个蛋糕分成若干个矩形,要求每一个矩形上都要有“奶油”,也即每个矩形要包含至少一个权值为 1 1 1 的块。显然蛋糕中的每一格都必须被划分到恰好一个矩形内,且矩形不能包含没有蛋糕的格子。
定义每一块矩形的代价为其每一行的最大值之和,即 ∑ i = l r ( max j − = d u v i , j ) \sum_{i = l}^r(\max_{j -= d}^u v_{i , j}) ∑i=lr(maxj−=duvi,j) 。特别地,对于宽(列数)为 1 1 1 的矩形,代价为矩形内权值的最大值。请你最小化划分整个蛋糕的代价。
n ≤ 3000 n\le 3000 n≤3000
考场思路
想到了可能要用到区间 d p dp dp ,但是不会做
正解
考虑维护区间最大值和最小值的位置。
然后搞一个 d p l , r , k dp_{l , r , k} dpl,r,k 表示区间 [ l , r ] [l , r] [l,r] 内从下往上前 k k k 层的最小代价。
通过一通推理发现,对于一个区间 [ l , r ] [l , r] [l,r] 的最优策略就是删除最高的那一列或者把区间的所有蛋糕删到最矮的那一列那么高。
搞一个记忆化就好了
D. 字符替换
题目大意
给定一个仅包含 0
、1
、2
、a
、b
、c
和 ?
的字符串,你需要将字符串中的每个 ?
分别替换成 0
或 1
或 2
之一,将字符串中的每个 a
分别替换成 0
或 1
之一,将字符串中的每个 b
分别替换成 0
或 2
之一,将字符串中的每个 c
分别替换成 1
或 2
之一。也就是说替换成一个 字符串。特别地,如果字符串中不包含 ?
,应将其自身视为唯一的替换方案。
求有多少种替换方案,使得替换后的字符串满足:恰好拥有奇数个“好的”非空子串。“好的”的定义为其本质不同的子序列(包含空集)个数为奇数。
每个数据点会给定一个字符串 ,然后每次对 的一个子串进行询问,答案对 998244353 998244353 998244353 取模。
n , ≤ 50000 n , \le 50000 n,≤50000
考场思路
题目有点绕,考试时把子序列看成了子串。
导致 1 ≤ n , m ≤ 10 1\le n , m \le 10 1≤n,m≤10 的部分分打挂了
正解
还不会
总结
前三题没有不会的知识点,但是没有想到思路
对于自己把握不大的题目或者打错了的题目,应该先自己操作一下小样例,看看是否理解好了题意。
对于 T 3 T3 T3 来说,可以手摸一下看能不能找到最优策略
平时可以多做一下 d p dp dp 的练习。
相关文章:

11.1总结
11.1总结 文章目录 11.1总结A. 集合题目大意考场思路 B. 差后队列题目大意考场思路正解 C. 蛋糕题目大意考场思路正解 D. 字符替换题目大意考场思路正解 总结 A. 集合 题目大意 给定一个长度为 n n n 的整数序列 a a a ,问该序列有多少个子区间满足这个区间内数…...

Proteus仿真--1602LCD显示电话拨号键盘按键实验(仿真文件+程序)
本文主要介绍基于51单片机的LCD1602显示电话拨号键盘按键实验(完整仿真源文件及代码见文末链接) 仿真图如下 其中右下方12个按键模拟仿真手机键盘,使用方法同手机键一样,拨打手机号码则在液晶显示屏上显示对应的号码 仿真运行…...

如何防范AI诈骗
如何防范AI诈骗 😇博主简介:我是一名正在攻读研究生学位的人工智能专业学生,我可以为计算机、人工智能相关本科生和研究生提供排忧解惑的服务。如果您有任何问题或困惑,欢迎随时来交流哦!😄 ✨座右铭&#…...

ICCV2023 Tracking paper汇总(一)(多目标跟随、单目标跟随等)
一、PVT: A Simple End-to-End Latency-Aware Visual Tracking Framework paper: https://openaccess.thecvf.com/content/ICCV2023/papers/Li_PVT_A_Simple_End-to-End_Latency-Aware_Visual_Tracking_Framework_ICCV_2023_paper.pdf github: https://…...

【PG】PostgreSQL查看与修改参数
文章目录 一 查看参数1. 使用 SHOW 命令:2. 查询 pg_settings 视图:3. 查看 postgresql.conf 文件:4. 使用 pg_settings 函数: 二 修改参数通过修改 postgresql.conf 文件:使用 ALTER SYSTEM 命令修改参数(…...

openGauss学习笔记-115 openGauss 数据库管理-设置安全策略-设置密码安全策略
文章目录 openGauss学习笔记-115 openGauss 数据库管理-设置安全策略-设置密码安全策略115.1 操作步骤 openGauss学习笔记-115 openGauss 数据库管理-设置安全策略-设置密码安全策略 115.1 操作步骤 用户密码存储在系统表pg_authid中,为防止用户密码泄露ÿ…...

如何更好地理解甜葡萄酒和干葡萄酒的区别?
如果你是葡萄酒界的新手,试图理解葡萄酒爱好者使用的所有术语和行话可能会非常困难。当你试图赶上时,你可能倾向于尝试货架上的每一种葡萄酒,以找出你喜欢的,但是那可能不会得到你想要的结果。所以如果你不确定你是喜欢甜葡萄酒还…...

基于单片机的车载太阳能板自动跟踪系统研究
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 技术交流认准下方 CSDN 官方提供的联系方式 文章目录 概要 一、总体设计开发流程二、机械结构设计与研究3.1 机械系统总体设计3.1.1 太阳能板折叠传动 三、太阳能自动跟踪系统硬…...

前端传字符串的开始时间和 结束时间,数据库时间字段是 timestamp,Java 代码如何写
目录 1 需求2 实现 1 需求 数据库时间字段类型是timestamp,前端传的开始时间和结束时间是字符串,那么代码如何写,可以实现 时间段查询 2 实现 实体类里面的字段是String xml 里面是 </if><if test"startTime !null and sta…...

Mac电脑录屏软件 Screen Recorder by Omi 中文最新
Screen Recorder by Omi是一款屏幕录制软件,它可以帮助用户轻松地录制屏幕活动,并将其保存为高质量的视频文件。 该软件提供了多种录制选项,包括全屏录制、选择区域录制和单窗口录制等,同时提供了丰富的设置选项,如视…...

Android 接入ttf字体文件
一、业务实现 一些炫酷的App总会加一些App自己的字体。这时候需要找UI提供ttf字体文件。 然后实现 TTF(TrueType Font)字体文件并将其应用到 TextView。 二、大致流程 将 TTF 字体文件添加到你的 Android 项目中: 将 TTF 文件复制到 res/f…...

Java中各种数据格式-json/latex/obo/rdf/ turtle/owl/xml介绍对比示例加使用介绍
一、数据格式类型 这些文件名称似乎包含了不同的数据格式扩展名,如.json, .latex, .obo, .owl, .rdf, .turtle, 和 .xml。以下是对这些数据格式的简要解释和讲解: JSON (.json): JSON(JavaScript Object Notation)是一种轻量级数…...

计网note
目录 其他 未分类文档 应用层补充 分组交换和报文交换 TCP和OSI参考模型...

Mac版eclipse如何安装,运行bpmn文件
一、下载程序包 网址:https://www.eclipse.org/downloads M2芯片安装包名称:eclipse-jee-2022-12-R-macosx-cocoa-aarch64.dmg 具体安装包版本根据自己电脑型号选择 二、eclipse安装步骤 1)双击下载的文件 2)将eclipse拖入到…...

3D高斯泼溅(Splatting)简明教程
在线工具推荐: Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 3D场景编辑器 3D 高斯泼溅(Splatting)是用于实时辐射场渲染的 3D 高斯分布描述的一种光栅化技术,它允许实时渲染从小图像样…...

为什么要停止在 SpringBoot 中使用字段注,改用构造器注入
停止在 SpringBoot 中使用字段注入! 本文为翻译文,同时加入了一些自己的理解,翻译来源:https://medium.com 在 Spring Boot 依赖项注入的上下文中,存在关于注入依赖项最佳实践的争论:字段注入、Setter注入和构造函数…...

数据可视化:地图
1.基础地图的使用 如何添加颜色表示层级 代码实现 """基础地图的使用 """ from pyecharts.charts import Map from pyecharts.options import VisualMapOpts# 准备地图对象 map Map() # 准备数据 data [("北京市", 9),("上海市…...

java 数据结构 ArrayList源码底层 LinkedList 底层源码 迭代器底层
文章目录 数据结构总结ArrayList源码底层LinkedList底层源码 迭代器底层 数据结构 对于数据结构我这边只告诉你右边框框里的 栈的特点:后进先出,先进后出,入栈也成为压栈,出栈也成为弹栈 栈就像一个弹夹 队列先进先出后进后出 队列像排队 链表查询满 但是增删快(相对于数组而…...

如何在Python编程中应用Linux环境下的框架,以实现高效算法?
python是一种广泛使用的编程语言,能够帮助开发人员快速开发高效的算法。与此同时,linux环境下提供了许多优秀的框架,可以进一步提高Python编程的效率。本文将介绍如何在Python编程中应用Linux环境下的框架,以实现高效算法。 一、Python和Linux环境的优势 Python是一种易学…...

多机位直播案例
目录 1、案例简述 2、设备准备: (1)笔记本电脑 (2)手机 (3)触控一体机 (4)教室前端监控摄像机 (5)教室后端监控摄像机 (6&…...

前沿重器[37] | 大模型对任务型对话的作用研究
前沿重器 栏目主要给大家分享各种大厂、顶会的论文和分享,从中抽取关键精华的部分和大家分享,和大家一起把握前沿技术。具体介绍:仓颉专项:飞机大炮我都会,利器心法我还有。(算起来,专项启动已经…...

第三章:boundary-value analysis
文章目录 Boundary-value Analysiscomputational faults 计算错误boundary shift 边界偏移boundary value analysis 的优势Path condition, domain, and domain boundary (路径条件、域和域边界)Open and closed boundaries (闭合边界 / 开放边界)on / off pointGuidelinestr…...

Python模块psutil:系统进程管理与Selenium效率提升的完美结合
前言 在前面编写一个Selenium的自动化程序时候,发现一个问题。 因笔记本配置较为差,所以每次初始化Selenium的WebDriver都会非常慢,整个等待过程是不友好的。 所以我就想到: 在程序中初始化一个全局的WebDriver对象,…...

glibc 里的线程 id
这里讲的是通过 pthread_create() 函数返回的线程 id,其实就是 glibc 库里维护的线程id,它跟内核维护的线程 id 不一样,pthread_create() 返回的线程 id 并不一定是唯一的。我们看 pthread_create 函数的源码,它最后返回的线程 id…...

nacos的部署与配置中心
文章目录 一、nacos部署安装的方式单机模式:集群模式:多集群模式: 二、安装的步骤1、预备环境准备2、载安装包以及安装2.1、Nacos有以下两种安装方式:2.2、更换数据源数据源切换为MySQL 2.3、开启控制台授权登录(可选) 3、配置中心的使用3.1、创建配置信…...

undefined 与 undeclared 的区别?
在 JavaScript 中,undefined 和 undeclared 是两个不同的概念,表示不同的情况: 1:undefined: undefined 是一个特殊的值,表示一个变量已经被声明,但尚未被赋予一个值。当一个变量被声明但未进…...

Leetcode周赛370补题(3 / 3)
目录 1、找到冠军 Ⅰ- 暴力 2、找到冠军 Ⅱ - 寻找入度为0的点 3、在树上执行操作以后得到的最大分数 - dfs树 逆向思考 1、找到冠军 Ⅰ- 暴力 100115. 找到冠军 I class Solution {public int findChampion(int[][] g) {int ng.length;for(int i0;i<n;i){int cnt0;for…...

PyTorch深度学习实战——图像着色
PyTorch深度学习实战——图像着色 0. 前言1. 模型与数据集分析1.1 数据集介绍1.2 模型策略 2. 实现图像着色相关链接 0. 前言 图像着色指的是将黑白或灰度图像转换为彩色图像的过程,传统的图像处理技术通常基于直方图匹配和颜色传递的方法或基于用户交互的方法等完…...

InfiniBand 的前世今生
今年,以 ChatGPT 为代表的 AI 大模型强势崛起,而 ChatGPT 所使用的网络,正是 InfiniBand,这也让 InfiniBand 大火了起来。那么,到底什么是 InfiniBand 呢?下面,我们就来带你深入了解 InfiniBand…...

分享一下微信小程序里怎么添加社区团购功能
随着互联网的快速发展,线上购物已经成为我们日常生活的一部分。而在这个数字化时代,微信小程序作为一种便捷的电商渠道,正逐渐成为新的趋势。其中,社区团购功能更是受到广大用户的热烈欢迎。本文将探讨如何在微信小程序中添加社区…...