第九屆編程大賽預選賽#題解
教育場了屬於是，深感自己變菜了
YYDS
題意：
按照字典序排序輸入的字元串，後面加上 YYDS! 後輸出
題解：
- 使用sort排序字元串，sort默認為字典序
- 使用set容器，默認對容器內元素採用字典序排序
打卡題，這裡就不放程式碼了
TCL和TQL
題意：
如果有一個60以下則輸出「TCL」，如果所有課程的成績都大於等於85，且平均分大於等於90，則輸出”TQL”
題解：
可以使用printf格式化輸出，其他的直接看程式碼吧
程式碼：
for(int i=1;i<=n;i++){ int m,sum=0,flag=1,a; cin>>m; for(int j=0;j<m;j++){ cin>>a;//輸入成績 if(flag==-1)continue;//若已經存在60以下科目則不繼續判斷 if(a<60)flag=-1;//存在60以下科目，TCL else if(a<85)flag=0;//存在85以下科目，無法成為優秀學生 else sum+=a;//計算當前總分 } if(sum<90*m&&flag==1)flag=0;//平均分小於90，無法成為優秀學生 if(flag==-1)printf("No.%d TCL\n",i); else if(flag==1)printf("No.%d TQL\n",i); }
市質檢的分數 [前綴和]
題意：
求區間[a,b]內的平均分
題解：
這道題是經典的前綴和題目，所以首先介紹一下前綴和思想：
- 經典oj題目：《校門外的樹-困難》
- 在數組arr[]中用arr[i]記錄arr[0]~arr[i]的和，這一思想使得我們需要區間[a,b]的和時，只需要調用arr[a-1]和arr[b]，通過arr[b]-arr[a-1]就可以得到
剩下的直接看程式碼吧
for (int i = 1; i <= n; i++) { int sum=0,num; for(int j=1;j<=9;j++) { scanf("%d", &num);//分數讀入 if (i>1)arr[i][j] =arr[i-1][j]+num;//記錄前綴和 else arr[i][j] = num; sum+=num; } arr[i][0]=sum+arr[i-1][0];//在arr[i][0]記錄綜合前綴和，本題因為數值不大，所以可以使用int }
迴文姓名
題意：
一個人的姓名中第一個字和最後一個字的拼音相同，則認為該名字為迴文姓名
題解：
一道字元串比對題目，本題可以簡單分為三類：（1）姓氏的拼音長度大於名（2）姓氏的拼音長度等於名（3）姓氏的拼音長度小於名
- 第一類，直接輸出「no」
- 第二類，直接判斷是否相等
- 第三題，從第二個字元串末位開始，取出和姓氏相等長度的字元串進行比對；同時需要判斷剩餘的字母是否符合拼音標準
- 關於檢查標準：按照題意，只需要檢查是否包含韻母即可（要檢查合理性的話這題考察的內容就偏了）
int len1=s1.length(),len2=s2.length(); if(len1>len2) cout<<"No\n"; else if(len1==len2){ if(s1==s2)cout<<"Yes\n"; else cout<<"No\n"; } else{ string s3=s2.substr(len2-len1); s3[0]= toupper(s3[0]);//令第三個字的首字母大寫，方便同姓氏拼音比對 s2[0]= tolower(s2[0]);//令第二個字的首字母小寫，方便韻母比對 bool flag=(s1==s3); int flag2=0; for(int j=0;j<len2-len1&&flag==1;j++){ if(s2[j]=='a'||s2[j]=='e'||s2[j]=='i'||s2[j]=='o'||s2[j]=='u'||s2[j]=='v') flag2++; } if(flag&&flag2)cout<<"Yes\n";//flag大於0則說明第二個字中包含韻母，符合題意中的檢查要求 else cout<<"No\n"; }
牧夫座空洞 [BFS/DFS]
題意：
三維搜索連續的0的個數，返回最大值
題解：
使用BFS/DFS演算法，主要為演算法的變式，與常規的BFS題目不同的是，本題是求面積範圍而不是給定起點與重點求最短路，所以本題需要自己擬定起點，我給出的程式碼只能說中規中矩，有很多可以優化的地方，感興趣的可以自己進行優化。
- 關於起點的擬定，我這裡採用了O（n^3）的複雜度，遍歷整個三維數組，應該會有更好的方法
- 當剩餘的「空洞」數量少於當前的max值時，其實不需要繼續搜索
- （常規bfs優化）：在記錄是否可以經過的「地圖」外側加上一圈的「障礙物」，這樣就不需要進行越界判斷
以上為我認為可以優化的兩個地方。
程式碼：
（1）程式碼一：BFS，使用隊列
關於隊列知識，可以查看我的部落格《[C++STL] 隊列 queue 的入門》
#include<bits/stdc++.h> using namespace std; struct point { int x, y, z; }; int L, R, C;//記錄三個方向的長度 int g[11][11][11];//記錄是否為空洞 bool dist[11][11][11];//記錄該位置是否被檢索過 int dx[] = {1, -1, 0, 0, 0, 0};//方向數組 int dy[] = {0, 0, 1, -1, 0, 0};//方向數組 int dz[] = {0, 0, 0, 0, 1, -1};//方向數組 queue<point> q;//聲明一個隊列，隊列沒有學過的可以去看我的往期部落格 int bfs(int i, int j, int k) { q.push({i,j,k});//起點進入隊列 int v = 0;//記錄共有多少個連續的元素 dist[i][j][k] = true;//標記該點已經走過 while (!q.empty()) { point t = q.front();//獲取隊頭數據 q.pop();//出隊（丟棄） v++; for (int i = 0; i < 6; i++) { int di = t.x + dx[i], dj = t.y + dy[i], dk = t.z + dz[i]; if (di >= 0 && di < L && dj >= 0 && dj < R && dk >= 0 && dk < C && g[di][dj][dk]==0 && !dist[di][dj][dk]) { //這一行首先判斷了是否越界，然後判斷該點是否可以通過，然後判斷是否已經過 dist[di][dj][dk] = true;//標記該點已經走過 q.push({di, dj, dk});//符合的點，入隊 } } } return v; } int main() { int t; cin >> t; while (t--) { cin>>L>>R>>C; memset(dist, 0, sizeof dist); for (int i = 0; i < L; i++) for (int j = 0; j < R; j++) for (int k = 0; k < C; k++) cin>>g[i][j][k];//輸入三維數組 int ma = 0; for (int i = 0; i < L; i++) for (int j = 0; j < R; j++) for (int k = 0; k < C; k++) if (!dist[i][j][k]&&g[i][j][k]==0)//如果當前的位置未被檢索過，且為「空洞」 ma = max(ma, bfs(i,j,k));//將改點作為起點進行bfs搜索 cout << ma << endl; } return 0; }
View Code
（2）程式碼二：BFS，使用遞歸
int bfs(int i, int j, int k) { if (i < 0 || i >= L || j < 0 || j >= R || k < 0 || k >= C)return 0;//判斷越界 if (dist[i][j][k] || g[i][j][k] == 1)return 0;//已經走過或者不為「空洞」 dist[i][j][k] = true;//標記已經走過 return 1 + bfs(i, j, k + 1) + bfs(i, j, k - 1),bfs(i, j + 1, k), bfs(i, j - 1, k) +bfs(i + 1, j, k), bfs(i - 1, j, k);//向六個方向試探 }
孤獨的島嶼 [並查集]
題意：
島嶼和島嶼之間通過橋樑進行連接，有的島嶼之間有橋樑，有的島嶼之間沒有橋樑，但可以經由通往別的島嶼的橋樑繞行到目的島嶼。如果完全無法通行，只能租用水上飛機才能到達該島嶼。以第1座島嶼為起點，想要遊歷一遍所有的島嶼，並且最終回到第1座島嶼，問他至少需要租用多少次水上飛機？
題解：
- 建立並查集，關於並查集，可以查看我的部落格《[並查集] 問題列表#1192：朋友》
- 判斷find(i)的值的個數
- 這裡給出兩種思路吧
- （1）存入set容器，輸出set.size()
set<int>ans; for(int j=1;j<=m;j++) ans.insert(k[find(j)]); if(ans.size()==1)cout<<0<<endl;//由於最終需要回到起始島嶼，若全部聯通則不需要 else cout<<ans.size()<<endl;
- （2）建立一個bool數組 b[]，將b[find(i)]=1，再遍歷一次bool數組
for(int j=1;j<=m;j++) k[find(j)]=1; int ans=0; for(int j=1;j<=m;j++) if(k[j])ans++; if(ans==1)ans=0; cout<<ans<<endl;
- （1）存入set容器，輸出set.size()
- 這裡給出兩種思路吧
第五題使用矩陣快速冪，只能說再等等，可能等不到了（課設太多了啊喂！）
製作：BDT20040
