原文作者:陈越姥姥
链接:原文链接
CCCC 团体程序设计天梯赛题解
目录序言正文基础题进阶题登顶题结语目录
序言
今年的题真的“难”了咩……?其实知识点覆盖是不变的。所谓“难”了,可能是大家还没习惯搞学长的命题风格 —— 以前天梯赛严重缺钱,姥姥没钱请人命题,所以包办了绝大部分题目,因为姥姥自己命题是免费的。现在天梯赛参加的娃多起来了,就有钱组个命题团队了。以后,会有越来越多的题目请搞学长这个风格的命题王出手,大家要慢慢习惯…
正文
看到微信群里教练们问有题解没 —— 天梯赛好像没有给题解的习惯,一般是姥姥顺手在知乎上列一下各题知识点就算了。那么这里也就列一下。
基础题
L1-1 输出一句话 —— 因为担心大家提交太快冲爆服务器,所以今年掺了一点盐,让你输出今天的日期…… 出完了转念一想,搞不好真有娃一紧张不知道今天是哪天了,于是加了一句告诉你昨天是哪天,这个不能就算难了吧……
L1-2 本来是计算一个整数除以一个浮点数,最后向下取整,然后搞学长说这也太难了!于是改成了两个整数做个除法就算了……
L1-3 就是 if-else,两个条件组合了一下,这个很难咩?
L1-4 搞学长的评价是题目挺好玩的,但是程序也太简单了!但这就是简单题呀~ 我觉得第3题考察了组合的条件,可能略难了一点,循环就别再掺盐了,于是就这样了。
L1-5 我省脑力,写个循环模拟每次的情况,其实你稍微推导一下,写个算式也能搞定的。聪明一点写个十几行代码就行了吧…… 这题好像也不用花时间?
L1-6 字符串处理题,每年都怕字符串惹祸,今年直接把伪代码都给出来了,再不会做简直不知道该出啥好了…… 这题送分的吧?
到此为止,6道不能说毫无难度,只能说难度为零的题送出去了,再不加点盐就太没味道了呗?即使如此,姥姥还是枪毙了搞学长的一道20分题,因为我想了10分钟,没想好怎么写,那就不是简单题。
于是他又重新出了一道,就是L1-7 姥姥第一眼看到题,想这个简单,我开个二维数组…… 然后一看10^5,噗……不行…… 再看一眼?发现不用二维,开两个一维的去重就好了。然后看错了条件还以为两个维度都是10^5,说你这简单题怎么能用到longlong呀!被搞学长嘲笑了,说你看清楚条件啊!唉,老年人不应该在23点以后考虑写程序的事情…… 于是去睡了,第二天醒来花了5分钟搞定,觉得这题可以的 —— 为啥通过率都不到20%???难在哪里了……
L1-8 问“最多”能推多少人,显然会把比赛和PAT成绩双达标的人全推过去先,剩下PAT分数不够的才按比赛成绩排队。175~290这个闭区间里一共116个不同的分数,每个分数设个计数器,看看最后统计出来的人数有没有超过K,没超过K个人的,肯定全推出去了,对吧…… 很多娃纠结“与前一个人相同”这个人是哪个人……重要吗?问的是人数,又没问推哪个人?这题考察的是“映射”这个小套路,把175~290的每个分数映射到数组下标,然后用数组存每个分数的计数器就好啦……
进阶题
L2-1 一个队列推送松针,一个堆栈临时存放松针,仅此而已。搞学长说太无趣了,但我觉得……线性表就是这么简单呀,掺点盐就太耗时间了。
L2-2 总有一题考排序的,虽然搞学长没用排序做,但我觉得排序然后扫描一遍多么简单明了!他说这题简单到不像话了。至此没有一道题用到大脑,基本上都在用小脑…… 这时搞学长加了一道用大脑的题,我觉得是时候应该加一道这样的题了,不然委实无趣了。
L2-3 其实这种用父指针/双亲指针建树的题目以前也有出过,好像是用在模拟赛里了,比如以前有道武林高手的题…… 所以不能算是完全的新思路,只是他掺了点盐…… 但是就样例这个规模的数据,完全可以纯粹暴力乱搞一下呀,搞过了至少13~15分能有的。
L2-4 往年图论题只出到建图和简单遍历这种类型,鉴于今年前面的题难度其实比往年低,今年就出了一道Floyd最短路 —— 三重循环的套路题。有娃不理解两个人直接没给关系该怎么办,那就是完全无感呀~ 求最短路的时候,完全没连接的顶点,肯定距离无穷大呀 —— 难道还能定义成0?之后就是扫描Floyd距离矩阵的行和列找最值了,跟姥姥在MOOC上讲过的那道哈利波特的题是一个类型的吧…… 这里有个坑,是你必须跳过同性,只扫描异性。搞学长验题的时候这里错了一次,看贴好像很多娃也是错在这里了 —— 但是姥姥给的样例多么友好!这里错了就过不了样例,你就知道错了呀~~~~今年的难度是在L3这里了,想想大概是没有出一道简单的DP题…… 因为吉老师的最难题把DP这个点给占了,则另外两题只能选另外的知识点……
登顶题
L3-1 比较裸的拓扑排序,本来是L3里面的送分题。姥姥的锅,竟然有一组数据有环了…… 手工造的数据能出环,真是不能相信老年人了 =_=# 之所以没验证就是觉得这是我手工造出来的不至于错吧…… 那谁知道手错了捏…… 以后记住了,所有数据一概要验证合法性,不管怎么做出来的!这题建图有点繁,姥姥手写哈希函数存图的顶点,另外度为零的顶点存进一个手写的最小堆,标程最慢跑了不到40毫秒。用map的来比一比呀~
L3-2 标程解法是计算每个节点的祖先有多少比它大(小),用树状数组维护。暴力可以至少骗15~16分。
L3-3 吉老师的状态压缩动态规划。回头我把他的解题报告跟题目一起放出来吧……
结语
花絮是,吉老师本来是有权限在讨论版答疑的,但是他进入了卷子的编辑状态,然后就盯着讨论版的权限设置页发了一下午的呆,还在郁闷怎么没有提问的窗口弹出来问他问题…… 摸摸九条可怜……个人觉得志在国奖的娃,在前两个级别里,在搞学长那里丢10分是可以原谅的,然后L3前2题应该一共可以骗到30分左右,所以220分是可以达到的。到250分是略难了一些。再次强调,以后命题大权会逐渐过渡到命题组年轻人的手上,大家要慢慢习惯他们的命题风格。还有我们负责命题的其他比赛(比如工信部的RoboCom、拼题A的520和跨年赛、乃至PAT考试等等),都会逐渐以年轻的命题团队为主,大家也会有更多机会适应他们的风格。一回生二回熟,加加油还是可以哒!_