厦门大学嘉庚学院：第九届编程大赛预选赛试题及其解析！
厦门大学嘉庚学院第九届编程大赛预选赛试题及其解析，快来试试吧！
例题一：YYDS
题意：
按照字典序排序输入的字符串，后面加上 YYDS! 后输出
题解：
使用sort排序 字符串，sort默认为字典序
使用set容器 ，默认对容器内元素采用字典序排序
打卡题，这里就不放代码了
例题二：TCL和TQL
题意：
如果有一个60以下则输出“TCL”，如果所有课程的成绩都大于等于85，且平均分大于等于90，则输出"TQL"
题解：
可以使用printf格式化输出 ，其他的直接看代码吧
代码：
例题三：市质检的分数 [前缀和]
题意：
求区间[a,b]内的平均分
题解：
这道题是经典的前缀和题目，所以首先介绍一下前缀和思想：
经典oj题目：《校门外的树-困难 》
在数组arr[]中用arr[i]记录arr[0]~arr[i]的和，这一思想使得我们需要区间[a,b]的和时，只需要调用arr[a-1]和arr[b]，通过arr[b]-arr[a-1]就可以得到
剩下的直接看代码吧！
例题四：回文姓名
题意：
一个人的姓名中第一个字和最后一个字的拼音相同，则认为该名字为回文姓名
题解：
一道字符串比对题目，本题可以简单分为三类：（1）姓氏的拼音长度大于名（2）姓氏的拼音长度等于名（3）姓氏的拼音长度小于名
第一类，直接输出“no”
第二类，直接判断是否相等
第三题，从第二个字符串末位开始，取出和姓氏相等长度的字符串进行比对；同时需要判断剩余的字母是否符合拼音标准
关于检查标准 ：按照题意，只需要检查是否包含韵母即可（要检查合理性的话这题考察的内容就偏了）
例题五：牧夫座空洞 [BFS/DFS]
题意：
三维搜索连续的0的个数，返回最大值
题解：
使用BFS/DFS算法，主要为算法的变式，与常规的BFS题目不同的是，本题是求面积范围而不是给定起点与重点求最短路，所以本题需要自己拟定起点，我给出的代码只能说中规中矩，有很多可以优化的地方，感兴趣的可以自己进行优化。
关于起点的拟定，我这里采用了O（n^3）的复杂度，遍历整个三维数组，应该会有更好的方法
当剩余的“空洞”数量少于当前的max值时，其实不需要继续搜索
（常规bfs优化）：在记录是否可以经过的“地图”外侧加上一圈的“障碍物”，这样就不需要进行越界判断
以上为我认为可以优化的两个地方。
代码：
（1）代码一：BFS，使用队列
（2）代码二：BFS，使用递归
例题六：孤独的岛屿 [并查集]
题意：
岛屿和岛屿之间通过桥梁进行连接，有的岛屿之间有桥梁，有的岛屿之间没有桥梁，但可以经由通往别的岛屿的桥梁绕行到目的岛屿。如果完全无法通行，只能租用水上飞机才能到达该岛屿。以第1座岛屿为起点，想要游历一遍所有的岛屿，并且最终回到第1座岛屿 ，问他至少需要租用多少次水上飞机？
题解：
建立并查集
判断find(i)的值的个数
这里给出两种思路吧
（1）存入set容器，输出set.size()
（2）建立一个bool数组 b[]，将b[find(i)]=1，再遍历一次bool数组
第五题使用矩阵快速幂，只能说再等等，可能等不到了（课设太多了啊喂！）
制作：BDT20040
希望对大家有帮助！
对于很多初学者来说，有一群一起学习一起解答的小伙伴很重要！如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！
微信公众号：C语言编程学习基地
整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）
欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！
编程学习书籍分享：
