2021.9.12周六PAT甲级考试复盘与总结

周六PAT甲级考试复盘与总结

先说结论:仍未步入“高手”行列;现在的学习节奏与方法是对的,有十万分的必要坚持下去。

题目 知识点 分数
T1 前缀和、二分 11 / 20
T2 排序 25 / 25
T3 图论 17 / 25
T4 二叉树(根据中序遍历建树) 30 / 30
总分 // 83 / 100

题目很简单,总体来讲极其可惜: T1 和 T3 考试时实在没有找到 bug 出在哪里,目前 T1 的 bug 已经找到,我们先且复盘考试。

复盘

浙江大学计算机程序设计能力考试(Programming Ability Test,简称PAT),据说浙江大学 CS 平均分 70 分,于是我也想试试。

考完试我觉得这个 70 分没有什么意义:

  • 首先,本次这四道题目极其简单
  • 其次, CS 的学生也并非有平日练习数据结构算法题的习惯,算法这个东西,大部分题目:「无他,唯手熟尔」

这次考 83 分十分可惜,可惜在题目太简单了,最后半小时,我就在死死盯着屏幕:逻辑上没问题啊?而且测试用例都通过了,怎么就有判分用例过不去呢?

昨天晚上睡前刷了刷知乎,果然大家都是甲级满分...恍然大悟 T1 在哪出了问题。

经验1:认真读题,不可臆测

第一题说:计算机保存一个数组,未必要在物理空间里申请一段连续的地址。

比如一个 int (32 bit) 数组长度为 20 ,其地址可能是:

// 首地址 元素个数
1024 10
0 5
2048 5

给我询问,问我第几个元素的地址是多少。

很简单的查询问题,怕超时,我还写了前缀和和二分(实际上知乎上说直接暴力枚举找都不会超时...)。

这题有两个坑点,我考试时全踩了:

  • 最后问我,开了多少个内存空间?
    • 我以为,比如一共查询了两个数 019 ,那就妥妥地用到 1024 这块还有 2048 这块返回 2 呗;于是写个 bool used[N]; 计数
    • 结果着实被教育了一把:你要开到 19019 之间的不开吗?因此你返回查询过的最大内存块编号就行了
  • 如果查询全部越界,你也得返回 1 个地址空间而不是 0
    • 我已经看不到题目了,但是据说题目中其实写了:至少开一块地址空间

这就很服气,原来一直以来,都是题目理解错了;而我一直以为是自己的逻辑问题,没有再读题。

PAT 甲级题目都是英文的,确实很考英文阅读理解。

经验2:继续刷题,打出自信

其实 T1 都错题也有自己不自信的锅:

  • 逻辑是对的,但我非得认为“一定是自己哪里写的有疏漏”
  • 如果我能咬定:“好,逻辑没问题了,我去再读一遍题目”,那将会是截然不同的结果

y 总就有这个自信,他讲过的每道题都会先说思路,然后亲手敲一遍,最后现场 debug 。自信来自于实力强大,如果我能强大到:『这个思路,这个实现,就没问题!如果出错了,一定是题目没理解对!』自然也不会有本次考试的可惜。

T3 我也没做成满分,我怀疑是 dfs 写得不好,周日上午打力扣也是,比完才意识到 dfs 有逻辑漏洞。我现在已经无法再看到当时的题目和代码了,也没必要纠结,再多做递归题目就是了。

经验3:复习没用,继续开眼

前 3 道题做的不好,于是跳到 T4 。

当时很慌,看到 T4 更慌了:靠,我要是考前复习下建树多好。

我除了 8 月份简单捋过两个序列遍历建树的代码就没再想过了。也确实没空。

但是记住了一条核心原则:有了中序遍历序列,则可以找到中心点,然后递归下去。

2021.9.12周六PAT甲级考试复盘与总结

于是硬着头皮,竟然写出来了, 30 分满分。递归真的很神奇,觉得算法可能有点麻烦,但是写的时候才发现递归帮我们把好多逻辑自动实现了。

因此现在更应该:

  • 把复习的时间更多地花在刷新题上
  • 好好记笔记,好好总结,争取学一遍就有学懂学透,少被模板,多理解核心思路,省着以后再回来看

总结

强烈给大家推荐 y 总的 PAT 课,虽然我算是他比较差的学生了(感觉很多人考了满分):AcWing.com PAT甲级辅导课

我 8 月 9 号买的, 9 月 6 号刷完,之后就没怎么碰过了。收获不小,关于算法细节的咱们以后慢慢唠。

算法这部分,上述三个经验总结起来,就一句话:现在的学习节奏与方法是对的,有十万分的必要坚持下去! 现在的学习节奏与方法是对的,有十万分的必要坚持下去! 现在的学习节奏与方法是对的,有十万分的必要坚持下去!

接下来准备干掉 y 总的算法提高课和算法竞赛进阶指南,这两节课内容太多了,先挑重点攻破吧!

2021.9.12周六PAT甲级考试复盘与总结

2021.9.12周六PAT甲级考试复盘与总结

上一篇:this的指向问题 --- 前端


下一篇:【题解】Ynoi 2007 rgxsxrs