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)$ 的删除。

---

不会做，使用 $\mathcal{O}(n\times ABC)$ 的暴力，枚举三元组 $(u,v,w)$，遍历 $n$ 个条件限制，如果有任意一个条件删除了该三元组则累加计数器。成功获得 $35$。

我是 B 题

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

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

---

枚举可能的结果，设 $d{p}_{i,j}$ 表示为到前 $i$ 个机器，目标排名位于 $j$ 的概率（初始化 $d{p}_{1,k}=1$，其中 $k$ 为枚举的目标）。考虑转移，此时有两种可能，就是机器把 $j$ 前面或是后面的删掉了。如果删除前面的，那么 $d{p}_{i+1,j-1}\leftarrow d{p}_{i+1,j-1}+d{p}_{i,j}\times (1-(1-p_i{)}^{j-1})$；如果删除后面的，那么 $d{p}_{i+1,j}\leftarrow d{p}_{i+1,j}+d{p}_{i,j}\times (1-p_i{)}^j$。

求出的 $d{p}_{n,1}$ 即为答案为枚举的目标的概率，乘上目标质量累计即可。时间复杂度 $\mathcal{O}(n^3)$。

我是 C 题

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

---

本题非常不要脸的地方在于，题面没有直接说出 $b$ 非严格单调递减，而是在数据范围里面用极小的字体给出了，这是解题的关键。

若是 $b_i\ge b_{i+1}$，那么对于任意区间 $[l,r]$，如果 $[l,v]$ 不满足条件，满足其子区间 $[u,v]$ 也必定不满足条件，因为删除了数而 $b_i$ 会增大。

因此我们可以使用分治。对于要分治的区间 $[l,r]$，我们将所有出现次数小于需要数量 $(b_{r-l+1})$ 的数删掉，也就是找到第一个数量没达到限制的 $p$，然后删除它并往两边递归。如果没有找到 $p$，则代表着该区间 $[l,r]$ 已经是满足条件的答案了，与答案取最大值即可。时间复杂度 $\mathcal{O}(n{\log }_{2}n)$。

我是 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$ 取模后的结果。

---

没看懂题，文件都没有创建，$0$ 分。江南 LPL 司马了，快跟我们一起说：Watch Out！

总结

• 排名：$1$；
• 比赛分数：$235/400$；
• 情况：相比 2024.10.6 模拟赛，好；
• 问题：语文理解能力不够。