d517 - 文字抄寫 I

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一系列由小寫字母組成的四字單詞，並判斷每個單詞是否已經出現過。如果單詞是第一次出現，則賦予它一個新的編號並輸出 "New! 編號"，否則輸出 "Old! 編號"，其中編號是該單詞第一次出現時的編號。

解題思路

使用一個 map (類似於 Python 的 dictionary 或 Java 的 HashMap) 來儲存單詞及其對應的編號。對於每個輸入的單詞，首先檢查它是否已經存在於 map 中。如果不存在，則將其添加到 map 中，並賦予一個新的編號（從 1 開始遞增），然後輸出 "New! 編號"。如果存在，則直接輸出 "Old! 編號"，其中編號是 map 中儲存的該單詞的編號。

複雜度分析

• 時間複雜度: O(n * k)，其中 n 是輸入的單詞數量，k 是單詞的平均長度（在本例中 k=4）。map 的查找、插入操作平均時間複雜度為 O(log m)，其中 m 是 map 中元素的數量。但由於題目限制 n <= 10^5，且單詞長度固定為 4，因此可以近似認為查找和插入操作的時間複雜度為 O(1)。
• 空間複雜度: O(m)，其中 m 是不同單詞的數量。map 儲存了所有出現過的單詞及其編號。

程式碼

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n;
	string a;
	while(cin >> n){
		int b=1;
		map <string,int> ans;
		while(n--){
			cin >> a;
			if(ans.find(a)==ans.end()){
				ans[a]=b;
				cout << "New! " << b << "\n";
				b++;
			}
			else{
				cout << "Old! " << ans[a] << "\n"; 
			}
		}
	}
}