Logic
向着梦想进发
Logic's Blog

【警钟长鸣】div3坠机实录

失败不可避免,唯有继续努力。这本来是一场普通的 div3,本来应该是上分的好机会,至少也是信心场。虽然上不了打分,但是至少分数也不会变化太多。但是我显然高估了我自己的能力。

A

一道模拟题,非常简单。当我看到这道题目时,我只觉得这是一场非常普通的 div3 的模拟题。

B

二分查找数的范围,也很简单,只是需要加一点讨论。

C

这题开始不对劲了,至少我觉得这是一道大模拟,但是调试了 2 个小时才过的这道题,其中直接重构了四五次代码。

第一次的代码没有考虑到要按照给的顺序做,WA。

第二次,改了一下代码把操作序列构造出来,但是这个构造不是最优所以 WA 了。

然后调细节一直调到一点半才把正解调出来。简单说一下我的思路:从后向前做,如果可以把非法的部分变为合法的,那么直接操作;如果不行,在合法的部分中找到不影响的部分;如果找不到就在上一次操作的位置做,因为从后向前做的时候那个值已经固定了,所以可以这么操作。

这题整整卡了我 2h 导致我这场 div3 只做了 2 题,又掉回绿名。但是这道题只有 1200 分,所以我需要拉响警钟,唯有努力。

D

模拟题,但是细节不少。枚举分割点:如果分割点在边界,那么就直接在原数组上检查有序性;如果在中间,则从两端向中间找到最大的有序部分,如果两个有序部分距离太远,那么非法,反之枚举所有可能的分界点,就可以得到答案。

E

矩阵变换。用到一个线性代数中非常基本的结论。假设操作的过程为:

$$
P_nP_{n-1}\dots P_1AQ_1Q_2\dots Q_m=B
$$

其中 P、Q 都是初等行列交换。我们需要的做的就是找到一组 P、Q 满足上面的式子。实际上这等价于先做所有的行变换,在做所有的列变换,这由矩阵乘法的结合率可知。所以我们直接先把行按贪心做变换,再按照列贪心变换,如果合法,那么就可以构造出答案。

以上,继续加训。

赞赏
# #
首页      coding      【警钟长鸣】div3坠机实录

发表回复

textsms
account_circle
email

Logic's Blog

【警钟长鸣】div3坠机实录
失败不可避免,唯有继续努力。这本来是一场普通的 div3,本来应该是上分的好机会,至少也是信心场。虽然上不了打分,但是至少分数也不会变化太多。但是我显然高估了我自己的能力。 A …
扫描二维码继续阅读
2024-06-04