2024.10.7 题目

题解：2024.10.7 模拟赛

我是 A 题

容斥 三维偏序 排序

给定 $A,B,C$，有一些不重复三元组 $(a,b,c)$ 满足 $a\in [1,A],b\in [1,B],c\in [1,C]$。定义三元组 $(a,b,c)$ 不大于 $(u,v,w)$ 当且仅当 $a\le u,b\le v,c\le w$。有 $n$ 次操作，每次给出三元组 $(u,v,w)$，将现存三元组当中不大于 $(u,v,w)$ 的删除。输入方式如下：

$$\begin{array}{rl}& \text{function }Rand(\text{arg: }k1(\text{reference}),k2(\text{reference})):\\ & \text{var }k3\leftarrow k1,k4\leftarrow k2\\ & k1\leftarrow k4\\ & k3\leftarrow k3\oplus (k3\mathrm{shl}23)\\ & k2\leftarrow k3\oplus k4\oplus (k3\mathrm{shr}17)\oplus (k4\mathrm{shr}26)\\ & \text{return }k2+k4\\ & \\ & \text{procedure }GetData(\text{none}):\\ & \text{var }x,y\\ & \text{read }n,A,B,C,x,y\\ & \text{for }\text{var }i\in [1,n]:\\ & u_i\leftarrow Rand(x,y)\mathrm{mod}A+1\\ & v_i\leftarrow Rand(x,y)\mathrm{mod}B+1\\ & w_i\leftarrow Rand(x,y)\mathrm{mod}C+1\\ & u_i\leftarrow A\text{ if }Rand(x,y)\equiv 0(\mathrm{mod}3)\\ & v_i\leftarrow B\text{ if }Rand(x,y)\equiv 0(\mathrm{mod}3)\\ & w_i\leftarrow C\text{ if }{u}_i\ne A\text{ and }{v}_i\ne B\end{array}$$

我是 B 题

概率dp 概率与期望

有 $n$ 个质量分别为 $1\sim n$ 的物品需要经过 $n$ 道质检工序。 每一轮工序会收到上一轮传过来的所有物品并开始质检，第 $i$ 道工序流程如下：

• 如果此时该道工序处只剩下一个物品，那么机器会将其粉碎。
• 如果此时该道工序处剩下了不止一个物品，那么机器会将质量最小的物品挑出来，以 $p_i$ 的概率将其粉碎，$1-p_i$ 的概率放过它并将其传给下一道工序。如果 机器放过了本次选择的物品，那么重新执行该流程直到粉碎某一个物品。 求最后剩下的物品质量的期望，答案对 $10^9+7$ 取模。

我是 C 题

递归 分治

有长度为 $n$ 的整数数列 $a,b$，需要求出最大的 $k$，满足序列 $a$ 当中存在区间 $[i,i+k-1]$，使得区间内出现过的所有数出现次数都不小于 $b_k$。

我是 D 题

线段树

若有一个长度为 $n$ 的数列 $a$ 满足 $\forall a_i\in [1,m]$，定义 $f(a)$ 为数列中所有极长相等子段长度的平方和。 现在给出长度为 $n$ 的数列 $b$，满足 $\forall b_i\in [0,m]$，$b_i=0$ 表示 $b_i$ 的取值在 $[1,m]$ 中均匀随机。 有 $q$ 次操作，每次修改数列 $b$ 中的一个值，或者询问 $f(b_l\sim b_r)$ 的期望对 $998244353$ 取模后的结果。