ARC177 记录

__vector__ · 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}。

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

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

现在，给定一个全 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。

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

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

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

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

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

我赛时的丑陋代码

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

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

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

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

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

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

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