b523 - 先別管這個了，你聽過安麗嗎？

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一系列字串，對於每個字串，判斷它是否為第一次出現。如果是第一次出現，輸出 "NO"，否則輸出 "YES"。輸入以 EOF 結束。

解題思路

這題的核心是判斷字串是否重複出現。可以使用一個 Hash Table (例如 C++ 的 map) 來儲存每個字串及其出現次數。每次讀取一個字串時，檢查它是否已經存在於 Hash Table 中。如果不存在，則輸出 "NO" 並將其加入 Hash Table，如果存在，則輸出 "YES"。

複雜度分析

• 時間複雜度: O(N * K)，其中 N 是輸入字串的數量，K 是字串的平均長度。因為每次讀取字串都需要在 map 中查找，map 的查找操作平均時間複雜度為 O(log M)，其中 M 是 map 中元素的數量。在最壞情況下，M 等於 N，所以查找操作的時間複雜度為 O(log N)。此外，插入操作也需要 O(log N) 的時間。因此，總時間複雜度為 O(N * (log N + K))。如果假設 K 遠大於 log N，則可以簡化為 O(N * K)。
• 空間複雜度: O(N * K)，其中 N 是輸入字串的數量，K 是字串的平均長度。因為 Hash Table 需要儲存所有不同的字串，在最壞情況下，所有字串都不同，因此需要 O(N * K) 的空間。

程式碼

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	map <string,int> ans;
	string a;
	while(getline(cin,a)){
		ans[a]++;
		(ans[a]==1)?cout << "NO\n":cout << "YES\n";
	}
}