b753 - P31以身分證投票之檢查
題目描述
題目要求統計有效身分證字號的數量、重複的有效身分證字號數量以及無效身分證字號的數量。輸入包含多組測試資料，每組資料包含若干個身分證字號。
解題思路
程式首先定義了一個 jg 函數，用於驗證身分證字號的有效性。驗證過程包括檢查字號長度、第二個字元是否為 1 或 2，以及計算檢查碼是否能被 10 整除。
主程式讀取每組測試資料，使用一個 map (dc) 來記錄已經出現過的有效身分證字號。對於每個輸入的身分證字號，首先使用 jg 函數驗證其有效性。如果有效，則檢查該字號是否已經在 map 中出現過。如果沒有出現過，則將其添加到 map 中，並將有效字號的計數器 (ans[0]) 加 1。如果已經出現過，則將重複字號的計數器 (ans[1]) 加 1。如果身分證字號無效，則將無效字號的計數器 (ans[2]) 加 1。最後，程式輸出每組測試資料的有效字號數量、重複字號數量和無效字號數量，以逗號分隔。
複雜度分析
- 時間複雜度: O(N * K)，其中 N 是每組測試資料中身分證字號的數量，K 是身分證字號的長度 (固定為 10)。
jg函數的時間複雜度為 O(K)，而主迴圈迭代 N 次。map的查找和插入操作平均時間複雜度為 O(log N)，但由於 N 的範圍較小，可以近似認為是 O(1)。 - 空間複雜度: O(N)，其中 N 是每組測試資料中不同有效身分證字號的數量。
map用於儲存有效身分證字號，最壞情況下需要儲存所有不同的有效字號。
程式碼
#include <iostream>
#include <map>
using namespace std;
bool jg(string k){
int kl=k.length();
if(kl!=10||(k[1]!='1'&&k[1]!='2'))return 0;
int num=0;
if(k[0]>='A'&&k[0]<='H')
num+=k[0]-'A'+10;
else if(k[0]=='I')
num+=34;
else if(k[0]>='J'&&k[0]<='N')
num+=k[0]-'A'+9;
else if(k[0]=='O')
num+=35;
else if(k[0]>='P'&&k[0]<='V')
num+=k[0]-'A'+8;
else if(k[0]=='W')
num+=32;
else if(k[0]=='Z')
num+=33;
else
num+=k[0]-'A'+7;
num=num/10+num%10*9;
for(int i=1;i<kl;++i)
num+=(k[i]-'0')*(9-i);
num+=k[9]-'0';
if(num%10)
return 0;
return 1;
}
int main(){
int n;
while(cin >> n){
int ans[3]={0};
map <string,int> dc;
string k;
while(n--){
cin >> k;
if(jg(k)){
if(dc[k])
++ans[1];
else{
dc[k]=1;
++ans[0];
}
}
else
++ans[2];
}
cout << ans[0] << "," << ans[1] << "," << ans[2] << "\n";
}
}