模板网站的建设,wordpress 招聘 插件,专业管道疏通网站建设图片,宁波百度做网站的公司哪家好11.1总结 文章目录 11.1总结A. 集合题目大意考场思路 B. 差后队列题目大意考场思路正解 C. 蛋糕题目大意考场思路正解 D. 字符替换题目大意考场思路正解 总结 A. 集合
题目大意
给定一个长度为 n n n 的整数序列 a a a #xff0c;问该序列有多少个子区间满足这个区间内数…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≤ri1所以可以用一个双指针来处理。
用线段树来维护最大字段和然后每次加入一个 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}) ∑ilr(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 的练习。
