2023 年上海市大学生程序设计竞赛 - 四月赛 题解

sunzhihong edited 1 年前

A

宝石划分：
题意为如果 $N$ 不是 $M$ 的倍数就一直让M减1，直到 $N$ 是 $M$ 的倍数。

根N的复杂度找出 $N$ 的所有因子，找到比 $M$ 小的最大的那个因子就是最终的人数，再输出 $N/M$ 即可。
另一种做法：设最终每人分配到的宝石个数为 $X$ ，则有关系 $M*X=N$ ，因此如果在输入之后如果 $M$ 大于 $10^6$ ，则让初始的 $X$ 不断加 $1$ ；否则就按照题意让 $M$ 不断减 $1$ 即可

B

$f[i][0/1]$表示考虑到第 $i$ 位是不是以 $o$ 为结尾的个数，考虑到每个字母长度不一样，从前往后转移比较方便。

注意划分后的每个摩斯电码都必须是26个字母中的一个。

C

首先，我们询问20个元素的完全图，每个元素的值是所有和他有关的询问的结果的“或“

这是因为，假设一个询问的结果在某一位上是1，那么询问的两个值在这个位置上面一定是1

这个值猜测错误的可能性是，当前值在某一位上是1，但是另外19个元素的值是0，这个可能性很小

于是我们得出20个元素的值，其中大概率有两个值的“或”的结果是全1

考虑两个随机值或的结果，每一位是1的可能性是3/4，总的可能性是 (3/4)^10

20个元素相当于190次随机，成功一次即可。这个概率也是非常大的

于是，我们有两个或的结果全1的数字，2n询问剩下的数字即可。

数据是随机数据，不再下发

D

回文串构造时可看做左右两半部分；一开始将每个字符串放进优先队列（在左 (l, empty, cost) 和在右 (empty, r, cost)）。然后每次 1~n 加入新的字符串在当前节点字符串短的一侧，看能否抵消（回文）。如果能有一边全部抵消，则将剩下部分加入优先队列。直到一边回文或者两边都空。

E

• 题目要求的操作为区间修改以及查询，考虑使用线段树。观察到颜色种类数较大，难以直接维护答案，考虑离线操作，计算每种颜色对哪些时间区间的答案有贡献。算出区间后进行差分以及前缀和即可得出所有时间点的答案，顺序输出即可。
• 关于如何计算每种颜色的贡献，我们只需要计算每次操作的影响会持续多久，得到每次操作的“影响区间”，再按照操作颜色进行分类存储并分别进行区间合并即可。一共有 $N$ 次操作，每次操作只会产生一个区间，因此区间合并这一过程显然可以 $O(N)$ 进行。
• 问题转化为如何计算每次操作的影响会持续多久。经过分析可知，每次操作的影响结束时间为该区间内所有点都被后续操作区间覆盖的时间，考虑正向维护较为困难，我们可以倒序操作，并使用线段树维护每个点前一次被更新的时间。每次操作相当于是线段树的区间赋值，而每次查询即为查询区间最值。每次操作流程如下：
• 查询该操作区间中的最大值，得到该区间何时被完全覆盖，设该值为 $R$
• 令该操作的时刻为$L$，得到该操作的影响区间 $[L,R]$
• 进行区间修改，将操作区间中各点的值修改为当前时刻 $L$
• 将得到的影响区间存入相应颜色的区间集合里
• 每次操作会进行一次查询与一次修改，共有 $N$次操作，计算影响区间这一过程的时间复杂度为 $O(Nlog_2S)$ ，由于倒序操作，区间左端点保证有序，因此区间合并时不需要额外排序，时间复杂度为 $O(N)$ ，差分与前缀和这一过程的时间复杂度显然为 $O(N)$
• 因此，总体时间复杂度为 $O(Nlog_2S)$

Comments