原文作者：陈越姥姥

链接：原文链接

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考试等等），都会逐渐以年轻的命题团队为主，大家也会有更多机会适应他们的风格。一回生二回熟，加加油还是可以哒！_