廈門大學(xué)嘉庚學(xué)院：第九屆編程大賽預(yù)選賽試題及其解析！
廈門大學(xué)嘉庚學(xué)院第九屆編程大賽預(yù)選賽試題及其解析，快來試試吧！
例題一：YYDS?
題意：
按照字典序排序輸入的字符串，后面加上 YYDS! 后輸出
題解：
使用sort排序?字符串，sort默認(rèn)為字典序
使用set容器?，默認(rèn)對(duì)容器內(nèi)元素采用字典序排序
打卡題，這里就不放代碼了
例題二：TCL和TQL
題意：
如果有一個(gè)60以下則輸出“TCL”，如果所有課程的成績(jī)都大于等于85，且平均分大于等于90，則輸出"TQL"
題解：
可以使用printf格式化輸出?，其他的直接看代碼吧
代碼：
例題三：市質(zhì)檢的分?jǐn)?shù)?[前綴和]
題意：
求區(qū)間[a,b]內(nèi)的平均分
題解：
這道題是經(jīng)典的前綴和題目，所以首先介紹一下前綴和思想：
經(jīng)典oj題目：《校門外的樹-困難?》
在數(shù)組arr[]中用arr[i]記錄arr[0]~arr[i]的和，這一思想使得我們需要區(qū)間[a,b]的和時(shí)，只需要調(diào)用arr[a-1]和arr[b]，通過arr[b]-arr[a-1]就可以得到
剩下的直接看代碼吧！
例題四：回文姓名
題意：
一個(gè)人的姓名中第一個(gè)字和最后一個(gè)字的拼音相同，則認(rèn)為該名字為回文姓名
題解：
一道字符串比對(duì)題目，本題可以簡(jiǎn)單分為三類：（1）姓氏的拼音長(zhǎng)度大于名（2）姓氏的拼音長(zhǎng)度等于名（3）姓氏的拼音長(zhǎng)度小于名
第一類，直接輸出“no”
第二類，直接判斷是否相等
第三題，從第二個(gè)字符串末位開始，取出和姓氏相等長(zhǎng)度的字符串進(jìn)行比對(duì)；同時(shí)需要判斷剩余的字母是否符合拼音標(biāo)準(zhǔn)
關(guān)于檢查標(biāo)準(zhǔn)?：按照題意，只需要檢查是否包含韻母即可（要檢查合理性的話這題考察的內(nèi)容就偏了）
例題五：牧夫座空洞?[BFS/DFS]
題意：
三維搜索連續(xù)的0的個(gè)數(shù)，返回最大值
題解：
使用BFS/DFS算法，主要為算法的變式，與常規(guī)的BFS題目不同的是，本題是求面積范圍而不是給定起點(diǎn)與重點(diǎn)求最短路，所以本題需要自己擬定起點(diǎn)，我給出的代碼只能說中規(guī)中矩，有很多可以優(yōu)化的地方，感興趣的可以自己進(jìn)行優(yōu)化。
關(guān)于起點(diǎn)的擬定，我這里采用了O（n^3）的復(fù)雜度，遍歷整個(gè)三維數(shù)組，應(yīng)該會(huì)有更好的方法
當(dāng)剩余的“空洞”數(shù)量少于當(dāng)前的max值時(shí)，其實(shí)不需要繼續(xù)搜索
（常規(guī)bfs優(yōu)化）：在記錄是否可以經(jīng)過的“地圖”外側(cè)加上一圈的“障礙物”，這樣就不需要進(jìn)行越界判斷
以上為我認(rèn)為可以優(yōu)化的兩個(gè)地方。
代碼：
（1）代碼一：BFS，使用隊(duì)列
（2）代碼二：BFS，使用遞歸
例題六：孤獨(dú)的島嶼?[并查集]
題意：
島嶼和島嶼之間通過橋梁進(jìn)行連接，有的島嶼之間有橋梁，有的島嶼之間沒有橋梁，但可以經(jīng)由通往別的島嶼的橋梁繞行到目的島嶼。如果完全無法通行，只能租用水上飛機(jī)才能到達(dá)該島嶼。以第1座島嶼為起點(diǎn)，想要游歷一遍所有的島嶼，并且最終回到第1座島嶼?，問他至少需要租用多少次水上飛機(jī)？
題解：
建立并查集
判斷find(i)的值的個(gè)數(shù)
這里給出兩種思路吧
（1）存入set容器，輸出set.size()
（2）建立一個(gè)bool數(shù)組 b[]，將b[find(i)]=1，再遍歷一次bool數(shù)組
第五題使用矩陣快速冪，只能說再等等，可能等不到了（課設(shè)太多了啊喂！）
制作：BDT20040
希望對(duì)大家有幫助！
對(duì)于很多初學(xué)者來說，有一群一起學(xué)習(xí)一起解答的小伙伴很重要！如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！
微信公眾號(hào)：C語言編程學(xué)習(xí)基地
整理分享（多年學(xué)習(xí)的源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門教程）
歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長(zhǎng)比自己琢磨更快哦！
編程學(xué)習(xí)書籍分享：
