团体程序设计天梯赛-练习集的一些做题经历及思路

CodeingBoy 3月 10, 2018

团体程序设计天梯赛练习集的一些题解和经历。

这些题目是免费的,可以前往团体程序设计天梯赛-练习集访问并测试。

个人编写的代码放在了 Github 上,可以前往 https://github.com/CodeingBoy/Exercises-on-PAT-gplt 查看。

L1-001 Hello World

非常简单的一道题,但还是 WA 了一次。究其原因,是没有复制题目中给出的字符串”Hello World!”,直接写了一个自己的”Hello world”上去,自然就过不去了。

L1-002 打印沙漏

这道题也很简单,但是思维要理清一点才行。所以重写了一次+WA 了几次才过。

注意沙漏图形每行的末尾不要有空格(trailing space),否则会提示格式错误。

L1-003 个位数统计

比上一题还要简单一些,只花了 5 min 就做完了。(上一题第二次编写花了 25 min)

不需要存储数字,直接用“桶”进行统计即可。

L1-004 计算摄氏温度

也是简单题。现实生活里面不应该使用整数去存放结果的,因为做了除法可能会得到小数。

注意输入结束 EOF 的判断(scanf 无输入时返回 EOF -1 而不是 0)和小数部份的截断(需要使用向 int 的转换而不是 printf 的格式符,格式符会对小数进行四舍五入)。

L1-005 考试座位号

比较简单的题,使用 C++ 或 Java 中的 Map 类型会方便很多。答案格式在输入的时候就可以一步搞定,不需要查询出来后再做拼接。

L1-006 连续因子

L1 里面让我最头疼的一道题了,毫无思路。毕竟数学渣渣。

查看网络上的答案后发现需要使用逆向思维来思考。根据思路撰写代码后样例 4 通不过。

参考:https://www.liuchuo.net/archives/1590、https://www.jianshu.com/p/13ae65186396

L1-007 念数字

简单题,注意空格

L1-008 求整数段和

简单题

L1-009 N个数求和

题目虽然复杂但思路还是挺简单的,主要考实现。测试来测试去样例 5 过不了,最后发现整数和分数都为 0 的时候要输出 0……不早说啊!

使用 long 即可,不需要使用 long long。题目里面也没做对溢出的特殊处理。只是在计算最小公倍数时使用了《算法竞赛入门经典》里面介绍的技巧来避免可能的溢出:

参考:https://www.liuchuo.net/archives/2083

L1-010 比较大小

qsort大法好!

L1-011 A-B

跪了……题目的意思挺简单,但是读取输入的时候要谨慎。一个不小心可能会把最后的换行符也给读入到字符串了。另外也要注意输出是否带换行符。

注意只有一个样例,不需要接受多行输入。

个人的思路是使用 strstr 函数对 A 字符串中的每个字符查找是否存在于 B 字符串中,网络上的其他人使用了“桶”的做法,这一点确实要高明一点。

样例 2 尝试了很久都没有通过,换用“桶”也无效,只得猜测是其它的方面。最后发现是输入的问题,换用 gets 即可。奇怪的是,使用 fgets 手工去除换行符后却会通不过……结果竟然是 size 参数设置的太小了!?(设置的是 10000+1,换用 10000+5 后成功)

对于不想看答案(不过既然你都搜索来这里了……),但是又想自己解决的朋友,我试着给一个严格的数据格式定义:

输入格式:

输入只包含一个样例,在2行中先后给出字符串A和B。两字符串的长度都不超过10^4,并且保证每个字符串都是由可见的ASCII码和空白字符组成,最后以换行符结束。字符串部分不包含换行符。

输出格式:

在一行中打印出A-B的结果字符串。末尾有无换行符都没关系。

L1-012 计算指数

简单题

L1-013 计算阶乘和

计算的是阶乘的和,也就意味着会多次计算阶乘,会产生重复计算。数据规模不大,可以对阶乘打表也可以缓存。

L1-014 简单题

简单题

L1-015 跟奥巴马一起画方块

简单题

L1-016 查验身份证

简单题

L1-017 到底有多二

简单题

L1-018 大笨钟

简单题

L1-019 谁先倒

注意“甲、乙两人的酒量(最多能喝多少杯不倒)”,因此需要喝了酒量+1杯酒才倒。

L1-020 帅到没朋友

最初是用比较朴素的办法:查询的时候遍历去查,虽然通过了但是第 5 个样例超时。后面换用了只计算最多朋友圈朋友数的方式来判断,解决。

L1-021 重要的话说三遍

简单题

L1-022 奇偶分家

简单题

L1-023 输出GPLT

不需要真的排序:用“桶”的思想很好做。

L1-024 后天

简单题

L1-025 正整数A+B

不是很难,但就是死活过不了样例 3……测试多次无果,最后只有上网搜索,最后发现”123 123 123″这种也是不能过的……真是够阴的。

参考:http://blog.csdn.net/qq_34594236/article/details/51946150

L1-026 I Love GPLT

简单题

L1-027 出租

题目比较简单,就是麻烦了点。

L1-028 判断素数

题目虽然简单,但是用朴素算法第 2 个样例会运行超时。

L1-029 是不是太胖了

简单题

L1-030 一帮一

简单题

L1-031 到底是不是太胖了

注意范围是一个 (min, max) 区间,区间以外的即不合格。

样例 2 过不了的话注意浮点误差。个人是对计算出来的 min, max 乘以 100 然后转为 int 来规避的。

L1-032 Left-pad

简单题

L1-033 出生年

y 的范围只是说明输入范围,不代表年份范围喔~

L1-034 点赞

使用 STL 的容器不难处理。

L1-035 情人节

简单题

L1-036 A乘以B

简单题

L1-037 A除以B

简单题

L1-038 新世界

简单题

L1-039 古风排版

只要能观察出映射关系就不难。

L1-040 最佳情侣身高差

简单题

L1-041 寻找250

简单题

L1-042 日期格式化

简单题

L1-043 阅览室

用 STL 的 map 比较好处理,注意没人借书时候的情况。

L1-044 稳赢

简单题

L1-045 宇宙无敌大招呼

简单题

L1-046 整除光棍

没有想出“聪明”的办法,于是直接使用了 BigInteger 解决。

L1-047 装睡

简单题

L1-048 矩阵A乘以B

注意要按输入的格式输出,要仔细观察输出的范例。

L2-001 紧急救援

使用 DFS 的思想比较容易做出来。提交后只通过了样例 0。样例 1 和 2 都是答案错误,样例 3 运行超时,尝试将 C++ IO 替换为 C IO、进行剪枝、优化数据结构都无效。

仔细阅读题目,才发现自己把无向图当有向图处理了。解决后通过了样例1、2,样例 3 仍旧超时。

尝试换用邻接表,无效。

L2-002 链表去重

拿到题目的第一个想法当然是用两个数组分别存入没有重复的节点和重复的节点了。但是做出来后和样例比对发现地址计算很复杂,才知道是顺序要按输入的地址来计算的。如果按之前的做法,当两个重复或不重复的节点之间(设它们为A、B)混杂着不重复或重复的节点,就需要跳过这些中间节点,得到 B 的地址才行。

转换做法,在节点加入是否重复的标志。然后在输出时检测节点本身是否是重复的。输出时忽略节点本身的下一地址,只有当找到相同类型的下一个节点时,才将这个节点的地址作为上一行输出的最后一个字段输出。

提交后通不过样例 1、2,尝试进行排查。设置空节点特殊标记和处理后通过样例 2。

L2-003 月饼

背包问题的变种。使用贪心法可以很容易做出来。

提交后样例 2 没有通过。

L2-007 家庭房产

拿到题目后考虑过使用并查集和 DFS 两种办法,不过由于并查集办法比较复杂,因此使用了 DFS 的办法。

提交后就 0 分了。查看了其他人的答案,才发现原来用并查集就可以……

L2-008 最长对称子串

使用枚举法,从长度为 len 开始,逐步递减长度,枚举并检测可能的字串。

提交后样例 6 运行超时。

L2-009 抢红包

L2 中相对比较容易的一题,只要把握好数据结构即可。

L2-010 排座位

世界上没有什么是一个并查集解决不了的,如果有,那就两个!

只需要使用一个并查集。对于敌对关系,由于只有直接敌对关系需要判断,因此一个二维数组即可搞定。

L2-014 列车调度

通过样例观察到,在一条平行轨道中,只需要后面列车的序号小于前面列车的序号即可。然后编程实现放入符合条件的队列即可。

我实现的时候使用了 vector 和 queue 容器,如果使用数组实现样例 1、2、3 会产生内存超限错误。

提交后样例 1、3 提示运行超时。

L2-015 互评成绩

比较简单的一题,把握好数据结构即可。

L2-016 愿天下有情人都是失散多年的兄妹

使用 DFS 对涉及到的记录进行标记即可,后续访问到发现已被标记过的记录就返回 No。

提交后样例 1、3、4 没有通过。

L2-019 悄悄关注

比较简单的一题。使用容器存储统计数据即可。

L2-021 点赞狂魔

比较简单的一题,使用合适的数据结构配合容器统计即可。

“标签出现次数平均值”指的是赞的次数/出现标签的种类数。

L2-022 重排链表

比 L2-002 好做,地址都保证是有效的。因此仿效 L2-002 的做法,使用 map 保存节点。再使用两个指针或下标依次输出即可。

提交后样例 3 答案错误。

L2-024 部落

并查集!并查集!

L3-007 天梯地图

没什么好说的,DFS 求最短路即可。

提交后样例 4 运行超时。

本文采用 CC BY-NC-SA 3.0 协议进行许可,在您遵循此协议的情况下,可以自由共享与演绎本文章。
本文链接:https://blog.codeingboy.me/thoughts-of-gplt-exercises/

发表评论

电子邮件地址不会被公开。 必填项已用*标注