本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-14 16:25:21

废话区

赛时 40min 切了 ABC，赛时切了 AB 后以为稳上分，就摆了一会再去看 C，最后掉分了，搞得猝不及防。

翻榜发现就比 Register_int 多 2min 罚时，重温了去年省选以 0.01 分差败于 zd 大佬的感觉。

A

设第 $i$ 种硬币价值是 $a_i$。

注意到对于 $\forall i \in {[1,5]},a_i | a_{i+1}$。

一个比较显然的贪心，即每次尽可能选价值大的硬币。

因为，越小的硬币适用的价格范围越广。

B

现在，给定一个全 0 的数组，给定了一些 $1$ 的位置，要求将对应位置的数变成 $1$。

正着操作似乎不太好操作。

考虑倒着来，依次处理倒数第 $1$ 个 $1$，倒数第 $2$ 个 $1$，$\cdots$，倒数第 $1$ 个 $1$。

假设从前到后第 $i$ 个 $1$ 位置在 $p_i$。
考虑现在要处理第 $t$ 个 $1$，且第 $t+1$ 个及以后的 $1$ 已经处理完毕，第 $1$ 到 $t$ 个 $1$ 尚未处理。

显然，可以先使用 $p_t$ 次 $A$ 操作将前 $p_t$ 个位置赋值成 $1$，然后再使用 $p_t-1$ 次 B 操作将前 $p_t-1$ 个位置赋值成 $0$。

以上反复操作，可以得到一组正确答案。

C

两个人，第一个要从 $(1,1)$ 走到 $(n,n)$，第二个要从 $(1,n)$ 走到 $(n,1)$，第一个人只能走红色或紫色格子，第二个人只能走蓝色或紫色格子。

现在要求最多把多少个格子变成紫色，使得两个人都能走到目标点。

事实上，有效的操作一个格子，只能使其中一个人的可使用格子增加。

也就是说，两个人的操作是独立的，分别建图跑最短路求答案，然后加起来就可以了。

我赛时的丑陋代码

D

本题 @Iceturky 教会了我做法，@cxm1024 的代码给了我一个较为简洁易懂的参考，使得我的代码长度压缩了 3 倍，学会了一个较为简洁的 mint 实现。在此拜谢。

注意，如果一些横坐标升序排序后编号连续的点，满足相邻点距离小于等于 $H$，那么这些点就可以互相影响，可以把它们放进一个连通块。

现在，依次枚举 $1$ 到 $n$ 次地震，同时维护当且地震结束后，所有电线杆倒塌的概率。

现在，考虑什么情况下，刚好第 $i$ 次地震结束后，$i$ 所在的连通块被全部摧毁。接下来分类讨论：

• 答案不为 $0$ 前提
  $i$ 电线杆所在连通块中，横坐标和编号都比 $i$ 点对应值小的电线杆都不能向右倒塌；所有横坐标大于 $i$ 电线杆，且编号小于 $i$ 电线杆的电线杆都不能向左倒塌。
• 若第 $i$ 个电线杆向左倒塌
  第 $i$ 个电线杆所在连通块中，横坐标比 $i$ 电线杆小的电线杆直接全部清除。
  那么要么第 $i$ 个电线杆处于所在连通块的最右端，要么第 $i$ 个电线杆按横坐标排序的下一个电线杆的编号小于 $i$，才能保证右边的全部清除。
• 若第 $i$ 个电线杆向右倒塌
  和上一种情况同理。

我自认为 cxm 大佬的代码是比大多数题解清楚的，所以超级巨佬 cxm1024 的赛时提交

E

官方题解说只有一百多种有效的题目分数分布，暂时没理解。

F