Canary Workshop

ここから始めよう 世界を見にゆこう

2021春季PAT甲级满分经历+线上考试经验

也算有惊无险,第一次考成功满分收工,就写一贴记录下做题时的心理过程、线上考试的经验和准备PAT时的经验作为纪念吧。

考前

因为是线上考试,环境就直接使用自己平时用的 VSCode 了。考试当日突然发现没有手机架,只好用椅子+书+衣架+透明胶自己糊了一个支撑手机的玩意……接上充电宝,手机架(迫真)第二机位就成了。

考前一个小时登录系统,这一个小时恐怕是最煎熬的:只能干坐着,电脑上什么也不能开,只好盯着时间倒数……

话说中午这个时间段干坐一个小时真的很容易犯困啊

开考

终于熬完了倒计时,开干!

(因为现在还不能绑定考试,完整代码稍后再放出来吧,这里只写写考试是怎么想的)

第一题,一看就是暴力求解的味道,第二题看到那堆时间瞬间想到了被模拟题支配的恐惧……那就先过

第三题,好嘛,考前才做过2019年春季真题,除了把常规的树改成堆以外几乎没变,先拿这个开刀好了。建堆肯定不会老老实实去手写的,懒狗会选择直接用 std::make_heap 。下面命题的读入有一定技巧性,这里说说我的办法:

  • 首先用 std::getline 把整行读入字符串;
  • 有一些命题最后一个字符有特征,这里就用类似 cmd[cmd.length() - 1] == 's' 作匹配;
  • 对于那些没法这样定位的,我先用 std::istringstream 把整个字符串塞进去,然后不断 iss >> tmp 得到特征位置(就本题来说,是第四个位置);
  • 判断完类型后,数据用 sscanf 读入。

这个时候多么希望能有 Python 的字符串操作!实际上这题用 Python 写也是可以的,直接用 Python 库函数里的堆实现。

判断说白了就是利用完全二叉树的性质,用下标来比较就行了。只要知道堆就是个完全二叉树,这点基本就没有难度。

写完提交一发,WA 了一个点,读了遍题发现是“插入”堆,于是改用 std::push_heap,再交,AC。(我好像是全场第一个过第三题的233333333)

看完题目感觉很简单,就是个贪心嘛!没仔细读题就光速敲了个 Dijkstra 算法,结果发现跟答案对不上。仔细读了遍题又瞅了眼数据范围,决定直接写 Floyd 算法(PAT甲在这之前好像没考过 Floyd?),再加个递归来从起始点一直往后找,根据访问过的点数判断方案是否可行。写的时候脑抽了一下,把 visited[u] = true 放在了查询最近点后面,导致出现好多重复点……当时还大脑短路没反应过来咋回事,随便加了点策略绕了过去,提交,AC,考完才想起来是自己蠢了。

看看(以为是模拟的)第二题。仔细看完,这不就是个裸的区间贪心么,考前才看到过,不过一时半会想不到边界条件了……草稿纸上现场推了下,提交,AC。

因为紧张和第二题和第四题稍微耽误了点时间,速度比平时做模拟要慢得多,此时还有一个半小时。看了眼榜,已经有不少满分大佬了。还有一个小时,有希望。进入第一题,还是觉得按照 PAT 的尿性这题绝对是暴力就好了。先写了个筛子打质数表备用,然后我先枚举公差,再枚举所有质数,保留所有结果,最后根据要求排个序输出。非常非常暴力,一提交果然一片绿:答案错误,内存超限,时间超限……好在第一个主测试点过了,此时还有一小时多,已经拿到90分,心态稳住,思考怎么优化。

内存超限肯定不是因为质数表,只能是我保留了所有结果。当然是没必要的,留一个就行。然后稍微加入了一些简单的剪枝策略,再提交,可惜只多过了一个点。

打表王决定万事不决先打个表看看,结果发现数据稍大的时候公差都是整10。钦定公差为整十肯定是不合适的,但根据运行时间来看,应该没有最开始那些小数据,不妨就 for (int diff = 10; diff < N; diff += 10) 这样枚举试试,真不行最后加个特判,提交,96分了!

此时还剩不到一个小时,我觉得是枚举上限的问题。当时一时半会没有想清楚上限(也就是上面代码的 N)应该是多少,于是发挥暴力的传统艺能,随便想了个大数,人肉二分查找上限反复提交在 TLE 和 AC 之间寻找平衡。。。就在寻找的过程中又过了一个点,98分。

还有一个点没有 TLE 而是直接 WA 了,那看来不是枚举上限的锅。再一看代码才意识到自己多蠢:没有保存下来所有质数而是枚举自然数再判断质数(虽然查表判断质数是 O(1) 的)。光速改了下筛子,保存质数,枚举只枚举质数(真的最开始就该想到的,蠢哭),提交,AC!

考试时没保存代码,完整代码等到开放绑定时再更新吧。虽然真的很丑很丑

考后

此时时间还有50多分钟,比平时训练慢了一大截。看了一眼四个红对勾深吸了一口气,有点波折但还是成功搞掉了!看了眼榜子准备交卷闪人,结果手贱点了登出……

赶紧微信小程序联系监考老师,老师让我重新登录,这一试两边都直接退了。无奈,只好在电脑屏幕上打出求救字样,重新走最开始的登录流程,拍照处拍下电脑上的求救字样。还好监考老师很 nice,给我放了进去。最后确认了一眼,提前交卷,登出客户端,考试结束。(到最后也对监考老师是谁一无所知,但还是想说声谢谢您!)

结束后还是有点不放心的,私信了姥姥一下确认这种情况是否违规,得到“没问题”的答复时才真正地松了一口气。

关掉电脑,躺在床上回想考试题目,才意识到自己好多地方有多蠢……代码也是烂到不能看(平时训练时还是很注重代码质量的,至少会好好缩进,好好给变量起名),但至少从结果上来说成功拿满了。完结撒花!

经验

今年寒假比较长,也花了不少时间在 PAT 的准备上,零零散散断断续续大概两个月。期间过完了《算法笔记》,刷完了近年考过的大部分题目,应该还算准备充分。这里就整理一些训练及考试时的经验吧(针对 PAT 甲级)。

  • 算法题一般都是用 C++ 刷,但是熟悉 Python 的话经常会有奇效。20分题有不少都可以用 Python 几行甚至一行秒杀,考场上关键时候也许能救命
  • 熟悉库函数!比如 C++ 里堆的那几个函数(建堆,插入,删除,判断之类的),这次考试如果不会的话那就得现场写,要是不会写那25分就没了,但如果恰巧看到过库函数用法就要偷笑了。Python 的库函数也尽量多看点吧,不光考试有用,以后干别的也可以少查很多 Stack Overflow
  • 熟悉套路。PAT 圈钱考试的套路不少,比如考过很多次的链表,我总结的套路就是:开个结构体存地址、数值和下一个地址,保存为数组 mem[100001],读入时就像真的链表那样。读完就从头开始捋一遍存入 std::vector<Node>,在数组里毕竟好处理点。处理完对着数组从头打印到尾即可。熟悉套路后看到链表题基本都是几分钟就能秒掉,不存在任何难度。这次考试的第三题也是,和2019年春季的第四题极为相似,考前才做过那题,数据的处理方法直接套用就是
  • PAT 甲级不考动态规划,不考最小生成树,不考树状数组,现在也(几乎)不考大模拟。如果目标只是 PAT 甲级,这些东西完全可以不看
  • 常见数据结构和算法多写几遍,达到能够直接默写的地步。PAT 甲级不难,很多时候就是个熟练度的问题
  • PAT 甲级的数据结构最难应该只涉及 AVL 树和堆
  • PAT 很多时候不怎么卡复杂度,所以不要怀疑自己,先试试暴力,有蛮大可能性直接就过了
  • 接上条,PAT 的评测机性能似乎参差不齐的,有的时候一些卡在超时边缘的代码,多提交几次可能就过了(曾经某道题我一份代码从10分一直提交到满分。。。)。尤其是大量使用 STL 的场合,多提交几次真的有奇迹
  • 再接上条,之前看经验贴说考试最后服务器会卡死,实测这次服务器性能很足,甚至比平时刷题都要顺,几乎不用排队可能是这次送钱的比较多服务器租多了

暂时就以上这些吧

结尾

这次 PAT 甲级总体感觉题型比以前新了一些(区间贪心,Floyd 算法应该从来没考过),难度的话一般偏易吧。也算借着这次机会,寒假里陆陆续续复习了一遍数据结构,也算比较有收获吧。

接下来大概就是被某人怂恿报名的CSP了