e925 - pD. 學號檢查
題目描述
題目要求驗證 10 個大學學號的有效性。學號的格式為九位字元，第一位必須是 'B'，第二、三位是數字，第四到七位是院系組代號，第八、九位是數字。程式需要檢查學號是否符合這些格式要求，並檢查第四到七位是否在給定的院系組代號列表中。最後，計算並輸出驗證失敗的比例。
解題思路
程式首先讀取院系組代號列表，並儲存在字串陣列中。然後，程式迴圈讀取 10 個學號，並對每個學號進行驗證。驗證包括檢查第一位是否為 'B'，第二和第三位是否為數字，第八和第九位是否為數字，以及第四到七位是否在院系組代號列表中。如果學號不符合任何一個驗證條件，則輸出 'N' 並增加錯誤計數器。如果所有驗證都通過，則輸出 'Y'。最後，程式計算並輸出錯誤比例。
複雜度分析
- 時間複雜度: O(N + 10 * M)，其中 N 是院系組代號的數量，M 是學號的長度。讀取院系組代號列表需要 O(N) 時間。驗證每個學號需要 O(M) 時間，由於有 10 個學號，因此驗證所有學號需要 O(10 * M) 時間。
- 空間複雜度: O(N + M)，其中 N 是院系組代號的數量，M 是學號的長度。程式需要儲存院系組代號列表，需要 O(N) 空間。儲存學號需要 O(M) 空間。
程式碼
#include <iostream>
using namespace std;
int main(){
int n,t,wa=0,ac=10;
string tt;
cin >> n;
string a[n];
for(int i=0;i<n;++i)
cin >> a[i];
while(ac--){
cin >> tt;
if(tt[0]!='B'||tt[1]>'9'||tt[1]<'0'||tt[2]>'9'||tt[2]<'0'||tt[7]>'9'||tt[7]<'0'||tt[8]>'9'||tt[8]<'0'){
cout << "N\n";
++wa;
}
else{
string k;
for(int i=3;i<=6;++i)
k+=tt[i];
bool chat=0;
for(int i=0;i<n;++i){
if(a[i]==k){
chat=1;
break;
}
}
if(chat==0){
cout << "N\n";
++wa;
}
else
cout << "Y\n";
}
}
if(wa==0)
cout << "0";
else
cout << "0." << wa << "\n";
}