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

11.1总结

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 1n2105,kn

考场思路

r i r_i ri 为以 i i i 为左端点的最右边可以取到哪里。

显然 r i ≤ r i + 1 r_i \le r_{i + 1} riri+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 1n106

考场思路

对于 1 ≤ n ≤ 5000 1\le n \le 5000 1n5000 的数据

对于每个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 n3000

考场思路

想到了可能要用到区间 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. 字符替换

题目大意

给定一个仅包含 012abc? 的字符串,你需要将字符串中的每个 ? 分别替换成 012 之一,将字符串中的每个 a 分别替换成 01 之一,将字符串中的每个 b 分别替换成 02 之一,将字符串中的每个 c 分别替换成 12 之一。也就是说替换成一个 字符串。特别地,如果字符串中不包含 ?,应将其自身视为唯一的替换方案。

求有多少种替换方案,使得替换后的字符串满足:恰好拥有奇数个“好的”非空子串。“好的”的定义为其本质不同的子序列(包含空集)个数为奇数。

每个数据点会给定一个字符串 ,然后每次对 的一个子串进行询问,答案对 998244353 998244353 998244353 取模。

n , ≤ 50000 n , \le 50000 n,50000

考场思路

题目有点绕,考试时把子序列看成了子串。

导致 1 ≤ n , m ≤ 10 1\le n , m \le 10 1n,m10 的部分分打挂了

正解

还不会

总结

前三题没有不会的知识点,但是没有想到思路

对于自己把握不大的题目或者打错了的题目,应该先自己操作一下小样例,看看是否理解好了题意。

对于 T 3 T3 T3 来说,可以手摸一下看能不能找到最优策略

平时可以多做一下 d p dp dp 的练习。

http://www.lryc.cn/news/219932.html

相关文章:

  • Proteus仿真--1602LCD显示电话拨号键盘按键实验(仿真文件+程序)
  • 如何防范AI诈骗
  • ICCV2023 Tracking paper汇总(一)(多目标跟随、单目标跟随等)
  • 【PG】PostgreSQL查看与修改参数
  • openGauss学习笔记-115 openGauss 数据库管理-设置安全策略-设置密码安全策略
  • 如何更好地理解甜葡萄酒和干葡萄酒的区别?
  • 基于单片机的车载太阳能板自动跟踪系统研究
  • 前端传字符串的开始时间和 结束时间,数据库时间字段是 timestamp,Java 代码如何写
  • Mac电脑录屏软件 Screen Recorder by Omi 中文最新
  • Android 接入ttf字体文件
  • Java中各种数据格式-json/latex/obo/rdf/ turtle/owl/xml介绍对比示例加使用介绍
  • 计网note
  • Mac版eclipse如何安装,运行bpmn文件
  • 3D高斯泼溅(Splatting)简明教程
  • 为什么要停止在 SpringBoot 中使用字段注,改用构造器注入
  • 数据可视化:地图
  • java 数据结构 ArrayList源码底层 LinkedList 底层源码 迭代器底层
  • 如何在Python编程中应用Linux环境下的框架,以实现高效算法?
  • 多机位直播案例
  • 前沿重器[37] | 大模型对任务型对话的作用研究
  • 第三章:boundary-value analysis
  • Python模块psutil:系统进程管理与Selenium效率提升的完美结合
  • glibc 里的线程 id
  • nacos的部署与配置中心
  • undefined 与 undeclared 的区别?
  • Leetcode周赛370补题(3 / 3)
  • PyTorch深度学习实战——图像着色
  • InfiniBand 的前世今生
  • 分享一下微信小程序里怎么添加社区团购功能
  • 软考高项-IT部分