f259 - 皓宇的青蛙
題目描述
題目要求讀取多行大寫英文字串，對於每個輸入的字串，判斷該字串是否曾經出現過。如果出現過，輸出 1；否則輸出 0。輸入以 EOF 結束。
解題思路
此題的核心是判斷字串是否重複出現過。可以使用 Hash Table (例如 C++ 的 map) 來儲存已經出現過的字串。對於每個輸入的字串，首先檢查它是否在 Hash Table 中存在。如果存在，則輸出 1；否則，將該字串加入 Hash Table，然後輸出 0。
程式碼使用了 getchar_unlocked() 函數來加速輸入，並使用 putchar_unlocked() 函數來加速輸出。cin.tie(0); ios::sync_with_stdio(false); 也能加速 I/O。
複雜度分析
- 時間複雜度: O(nm)，其中 n 是輸入字串的數量，m 是字串的平均長度。因為每次查詢和插入
map的平均時間複雜度都是 O(log m)，而有 n 個字串，所以總時間複雜度是 O(nlog m)。在最壞情況下，如果所有字串都不同，則時間複雜度接近 O(n*m)。 - 空間複雜度: O(n*m)，其中 n 是輸入字串的數量，m 是字串的平均長度。因為
map儲存了所有不同的字串，所以空間複雜度取決於不同字串的數量和長度。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <map>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
map <string,bool> ans;
char in;
string input;
while(in=getchar_unlocked()){
if(in==-1)break;
else if(in>='A'){
input+=in;
}
else{
if(ans[input]){
putchar_unlocked('1');
putchar_unlocked('\n');
}
else{
ans[input]=1;
putchar_unlocked('0');
putchar_unlocked('\n');
}
input.clear();
}
}
}