11.1总结

11.1总结

A. 集合

题目大意

给定一个长度为 $n$ 的整数序列 $a$ ，问该序列有多少个子区间满足这个区间内数值的最大字段和小于 $k$

$1\le n\le 2\ast 10^5,k\le n$

考场思路

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

显然 $r_i\le r_{i+1}$，所以可以用一个双指针来处理。

用线段树来维护最大字段和，然后每次加入一个 $j$ ，如果当前的最大字段和大于 $k$ ，那么答案就加上 $ i - j$ ，每次再把 $i$ 从线段树中删除就好了

B. 差后队列

题目大意

差后队列为一种数据结构，支持两种操作：

• push 插入一个数
• pop 随机删除一个 不是 最大值的数。如果只有一个数则删除该数

给定操作序列，求每次删的数的期望，以及每个数期望被删的时间，答案 $\mathrm{mod}998244353$

$1\le n\le 10^6$

考场思路

对于 $1\le n\le 5000$ 的数据

对于每个push，直接向后找到比它大的数，然后记录上到它被删除的期望。

就是前面都没有被删除的期望乘上这一次被删除的期望。

对于每个pop

求从上一次队列清空开始，到这次删除的数的期望

每次的数的期望就相当于对于每个在队列内的非最大值的数 $num$ 乘上之前没被删掉的期望，再乘上这一次被删掉的期望。

暴力维护即可。

考场上打挂了，因为pop的情况不会处理

正解

跟上面的差不多

对于每次要删的数的期望。

每次从队列没有数开始单独处理。

• 如果当前只有一个数

  那么直接删除就好了

• 否则

  维护一个当前的最大值和当前数的数量，每次的数的期望就相当于对于每个在队列内的非最大值的数 $num$ 乘上之前没被删掉的期望，再乘上这一次被删掉的期望。

对于每次数被删除的数的期望时间

维护一个类似于后缀和的东西。

从后往前开始，一个数的期望删除的时间就是这次被删除的期望加上这次没有被删除的期望乘上以后被删除的期望。

C. 蛋糕

题目大意

你现在得到了一个二维蛋糕，它从左到右可以分成 $n$ 列，每列高为 $a_i$ 。对于每一列，又可以从下到上分为 $a_i$ 块，并且最上面一块权值为 $1$ ，从上到下权值依次加 。每一列的最上面的权值为 的块的上表面有“奶油”。

你现在要把这一个蛋糕分成若干个矩形，要求每一个矩形上都要有“奶油”，也即每个矩形要包含至少一个权值为 $1$ 的块。显然蛋糕中的每一格都必须被划分到恰好一个矩形内，且矩形不能包含没有蛋糕的格子。

定义每一块矩形的代价为其每一行的最大值之和，即 ${\sum }_{i=l}^r({\max }_{j-=d}^u{v}_{i,j})$ 。特别地，对于宽（列数）为 $1$ 的矩形，代价为矩形内权值的最大值。请你最小化划分整个蛋糕的代价。

$n\le 3000$

考场思路

想到了可能要用到区间 $dp$ ，但是不会做

正解

考虑维护区间最大值和最小值的位置。

然后搞一个 $d{p}_{l,r,k}$ 表示区间 $[l,r]$ 内从下往上前 $k$ 层的最小代价。

通过一通推理发现，对于一个区间 $[l,r]$ 的最优策略就是删除最高的那一列或者把区间的所有蛋糕删到最矮的那一列那么高。

搞一个记忆化就好了

D. 字符替换

题目大意

给定一个仅包含 0、1、2、a、b、c 和 ? 的字符串，你需要将字符串中的每个 ? 分别替换成 0 或 1 或 2 之一，将字符串中的每个 a 分别替换成 0 或 1 之一，将字符串中的每个 b 分别替换成 0 或 2 之一，将字符串中的每个 c 分别替换成 1 或 2 之一。也就是说替换成一个 字符串。特别地，如果字符串中不包含 ?，应将其自身视为唯一的替换方案。

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

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

$n,\le 50000$

考场思路

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

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

正解

还不会

总结

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

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

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

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