题目：[[2024.10.7 题目]] ![[UKE 一语惊人.png]] ![[HKE 经典语录.png]] ## 我是 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$ 取模。 --- 枚举可能的结果，设 $dp_{i,j}$ 表示为到前 $i$ 个机器，目标排名位于 $j$ 的概率（初始化 $dp_{1,k}=1$，其中 $k$ 为枚举的目标）。考虑转移，此时有两种可能，就是机器把 $j$ 前面或是后面的删掉了。如果删除前面的，那么 $dp_{i+1,j-1}\gets dp_{i+1,j-1}+dp_{i,j}\times (1-(1-p_i)^{j-1})$；如果删除后面的，那么 $dp_{i+1,j}\gets dp_{i+1,j}+dp_{i,j}\times (1-p_i)^j$。 求出的 $dp_{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 模拟赛]]，好； - **问题**：语文理解能力不够。