写在前面
作业还没有写完,简单写一下吧,做题过程中的感受就不会写那么详细了。
A
比较简单,就是个等差数列,数据范围很小,随便切。
B
简单的题目,但是我罚时了四次。把题目看错了,下次注意。
C
规律一开始没有推出来,写了个不带记忆化的 \(O(log n)\) 的深搜(没带记忆化所以这个复杂度应该是假的,但是确实是每次减少一半)。赛时知道记忆化可以做,但是值域太大了,没有想到去离散化,然后选择去推规律。有了暴力的程序帮我推规律,规律也挺好找的,再这里就不赘述了。
D
第一眼贪心,但是局部最优不能达到全局最优,然后想到 DP。有 \(2\) 个状态转移,自然想到状态机,但是写着写着发现假了,因为有后效性,挺烦的。再看了一眼,其实就是个最短路问题,建图跑了一遍 dij,成功 \(A\) 掉本题。
E
赛时没有调出来。说实话,这道题转化为数据结构的步骤挺巧妙的,单点查+区间修改,这是很基础的数据结构的操作,但是对于我这种蒟蒻来说不那么容易看出来。开始写线段树的时候只有 \(17\) 分钟了,我写写写,写完之后还有 \(9\) 分钟,样例一测,不对。但是我马上发现这道题下标是从 \(0\) 开始的,然后改了一下,发现答案比样例大一点,才发现自己是因为没有减去拿走的球。加上减去拿走的球这一步骤之后,发现答案居然有负数!猜到是哪里的数组越界了,此时还有 \(7\) 分钟,开始调调调,但是调不出来。赛后看题解的时候发现居然是修改的时候 \(x+1\) 可能比 \(n\) 大从而导致越界。可恶啊!
F~G
四次比赛了一次 \(F~G\) 都没有看过,对我来说在一个小时四十分钟内切掉比较难,这个阶段先不管他。
写在最后
这是我第四次参加 abc(前面有两次懒得写了),本来以为这次可以切掉五题的,可以在 \(B\) 题上面因看错题目浪费太多时间,在 \(E\) 题上面没有考虑周全导致越界,最终没有把第五道题给切掉,有点遗憾。