NOIP2023模拟8联测29 总结

题目

T1 集合

大意

给出一个序列 \(S\)，找出有多少个区间 \([L,R]\)，使得 \([L,R]\) 值域的连续长度不超过 \(k\)。

\(n \leq 2*10^5,k\leq n\)

赛时思路

对于区间 \([L,R]\)，如果有 \([L',R']\) 符合答案（\(R'\leq R\) 且 \(L \leq L'\)），那么区间 \([L,R']\) 也符合答案，每个点自己可以覆盖的最右边。可以通过维护一条队列，里面的点都是可能的右端点，通过线段树判断，如果可以满足大于 \(k\) 就出队，直到不满足条件，此时的最后一个出队的点就是最右端点。

正解思路

同上。

T2 差后队列

大意

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

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

给定操作序列，求每次删的数的期望，以及每个数期望被删的时间（如果到最后也没被删则删除时间为 \(0\)）。

\(n\leq 10^6\)

赛时思路

分开讨论两个问题，第一个问题通过 dp 可以解决，第二个问题考虑每一个可能删除它的操作带来的贡献，为一个若干个概率相乘的式子，类似于正解，唯一的错误在于笔误 \(p_i\) 没有使用 \(1-p_i\)。于是考试时没调出来……

正解思路

博客链接：2023NOIP A层联测22 差后队列 - 彬彬冰激凌 - 博客园 (cnblogs.com)

除去最大值外的元素个数的倒数就是这一轮取到某个数的概率，而最大值是特殊的情况，在被替代之前或作为最后一个数被弹出之前，不参与计算。

对于操作 0 的输出和操作 1 的输出分开处理。

操作 1

设 \(f[i]\) 表示在执行第 \(i\) 个操作时可弹出数的期望大小。

1.加入操作

加入后不成为最大值，\(f[i]=f[i-1]+val[i]\)。

加入后成为最大值，\(f[i]=f[i-1]+mx\)，然后更新 \(mx=val[i]\)。（\(mx\) 为最大值）

2.删除操作

设此时队列中除去最大值外元素个数为 \(has\)。

除最大值外每个元素被取到的概率 \(p=\frac{1}{has}\)。

此时期望取到的值 \(ans=p*f[i]\)。

更新 \(f[i]=f[i-1]-ans\)。

\(ans\) 为这一次操作的答案。

操作 0

不难发现，每个元素都有一个开始会被弹出的操作 1，和一定被弹出队列的操作 1。

设第 \(i\) 个弹出操作弹出每个树的概率是 \(p[i]\)。（除最大值外每一个数被等概率弹出，所以 \(p[i]\) 容易得到）

设第 \(i\) 个弹出操作是总操作中第 \(a[i]\) 个操作。

设第 \(u\) 个插入队列的数，可以被弹出的第一个操作 1 是总弹出操作第 \(st_u\) 个，一定会被弹出的操作 1 是总弹出操作的第 \(ed_u\) 个。

那么对于第 \(u\) 个插入的数。如果不是最大值，那么它在第 \(k\ (st_u \leq k \leq ed_u)\) 次操作被弹出的概率是 \(p_k\prod_{j=st_u}^{k-1}(1-p_j)\)。

给期望删除时间的贡献为 \(a_kp_k\prod_{j=st_i}^{k-1}(1-p_j)\)。

第 \(u\) 个插入的数被删除时间的期望为 \(ans_u=\sum_{i=st_u}^{ed_u} a_ip_i \prod_{j=st_u}^{i-1} (1-p_j)\)。

接下来要考虑如何 \(O(1)\) 的求这个式子。

设 \(s_i=a_ip_i\prod_{j=1}^{i-1}(1-p_j)\)。

又有 \(g_1=\frac{1}{1-p_1}\)，\(g_i=g_{i-1}\frac{1}{1-p_i}\)。

所以 \(ans_u=\sum_{i=st_u}^{ed_u} s_ig_{st_u-1}=g_{st_u-1}\sum_{i=st_u}^{ed_u} s_i\)。

后面的 \(s_i\) 可以用前缀和 \(O(1)\) 求出。

而上面的数预处理都是 \(O(n)\) 或 \(O(n\log_2n)\)。

总时间复杂度 \(O(n\log_2n)\)。

可能会有点小常数。

T3 蛋糕

大意

有若干列数字排在一起，数字由 1 开始，从上到下递增，可以将他们划分为若干个矩形，要求每个矩形必须包含一个 1。

该矩形的花费为：1.如果只有一列，花费为最大值。2.如果有若干列，花费为每一列的最大值。

求最小划分花费。

\(n \leq 300,a_i \leq 10^9\)

赛时思路

完全没想法，自己的暴力花费方案不满足最低分数要求，初步形成了一个猜测，划分以最长列划分两个区间，或一最低处划分若干区间。

正解思路

考虑区间 dp，以上述最长列划分和最低处划分（证明过程较简单略），设 \(dp[l][r][k]\) 为区间 \([l,r]\) 高度为 \(k\)，转移通过上述划分转移。

这样状态数过多，但是可以证明有效状态数在 \(n^2\) 以内，于是 map 记忆化加递推求解即可。

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