9.4模拟赛

part1:比赛过程&结果回顾

一、比赛过程:

先读题,觉得第一题基本可做,也许能切,先放着不管。第二题不是很难,估计有一些奇怪的性质,至少能写个暴力,先过。第三题,在k维上求最大点权独立集,emmm估计是树形dp或者贪心,仔细一看,题面过于复杂,好多隐藏条件根本看不出来,没想出来怎么在多个图之间建边,第一步就卡住了,连暴力都写不出来,直接放弃。第四题,是数学推倒,只会(!n * n)的做法,估计第一个点都过不了。后来看到题解发现这题确实不可做,包括且不限于莫反的一大堆公式,这要是考场现推估计直接爆炸。

最后选定先做第二题在做第一题,第三第四题直接把样例以及几个手算能算出来的数据打了个表。
第二题暴力写过了,然后发现D、U、R、L这四个操作可以互相抵消而且进行的顺序并不影响结果,直接滚动数组+特判+暴力修改+优化修改水掉30分。
开始做第一题,觉得就是一个小递推,顶多有一个矩阵快速幂。先写出一个按照题意剪枝的全排列dfs,暴力打表,直接找规律。然后就没找出来。先打表把n=20以内全部打出来,水掉20分。现在总分20+30=50。
递推推不出来我就以为这个并不是递推,再加上复杂度算错了,然后就以为这个东西需要o(1)查询,是需要推导一个公式,这方向都错了自然就不可能有结果。
最后还剩1h30min,会过头来做第二题,我就猜规律然后在结合纯暴力代码验证规律的正确性,最后推出来了一个可过80+的做法。结果代码难度特别大写出一堆bug。以往的经验告诉我这个时候debug是不会有结果的,于是乎就直接放弃,继续做第一题。结果最后也没推出来。

二、end:tot=第一题20+第二题10=30

第一题合情合理,估分和结果一样。
第二题代码太长,滚动数组有一个地方写错了常见bug的博客又有素材了,但是我自己构造的数据和断点调试都没能发现这个问题。。。挂掉40分,下次注意吧。
第三题第四题手算的打表没得分也在意料之中。

三、总结:

整体心态非常平稳,但是还是debug能力+代码实现能力确实不够。再加上我平时练得多的部分这次真的是一点都没考,数论很多内容也只是会个定义+公式+特别裸的模版题。

part2一些比较重要的经验:

(1)递推最重要的性质是1~n的连续性,也就是找到f[i]对前面所有f的依赖性,而性质的推导重在从题意中找出如何从i找到n的过程
(2)虽然是个错误思路,但是递推式有可能出现减法
(3)如果估计代码会很长的时候,就尽量慢点写不出错,要不然在数据不容易构造的情况下真的很难debug
(4)多练数论

part3:题解+一些题解所需的前置知识

施工中
先搞完前置知识的灵活应用吧,毕竟很多我会的树上算法都快忘的差不多了,顺便搞一个树上算法+部分图论算法的集合。

9.4模拟赛

上一篇:文件管理基础命令之二


下一篇:k8s-集群安全机制