zerojudge d518 C++詳解文字抄寫 II

Jan 24, 2025

d518

題目

https://zerojudge.tw/ShowProblem?problemid=d518

Content

從機器中，不斷地出現 “?” 個英文字母的單字，現在要你抄寫下來，倘若這個單字已經出現過，則會使用編號上的號碼直接書寫倘若這個單字沒有出現過，則會賦予單字一個新的號碼

每組新的測資，代表不同事件，請勿將其納入新的號碼

Input

每組輸入的第一行 , 有一個數字 N ( 1 ≦ N ≦ 104 )

接下來會有瘋狂科學家講出的 N 行單字

每行由小寫字母 a 到 z 所構成的 ? 字單字. ( 1 ≦ ? ≦ 20 )

Output

若這個字串之前已經出現過,則輸出號碼,若沒有則輸出它將被編寫的號碼.

破題

看到這個問題，可以轉換成鍵值對問題，以字串為鍵，值隨便，因為本題利用鍵值對只是要看他有沒有存在而已，所以具體的值不重要。

那自然而然地要先宣告鍵值對物件，而C++中的鍵值對是 map，又我們不關心 map 中的順序，因此可以以用 unordered_map 加速。並且順便宣告用來讀取輸入的字串 s ，題目的 n 還有序號(從1開始)

unordered_map<string,int> m;
string s;
int n,no;

然後在處理的時候，先把讀入的字串當作鍵，在 C++ 的 map 中透過 map.find() 查詢，然後如果沒有查詢到就把他加入 map ，反之如果有查詢到就輸出號碼。

程式碼如下

	cin>>s;
			if(m.find(s)!=m.end()){
				cout<<"Old! "<<m[s]<<endl;
			}
			else{
				cout<<"New! "<<no<<endl;
				m[s]=no;
				no++;
			}

據題目”每組新的測資，代表不同事件，請勿將其納入新的號碼”，因此每次回合是為獨立的查詢，因此要做初始化

	m.clear();
		no=1;

完整程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,no;
	string s;
	ios::sync_with_stdio(0); // 加速輸入輸出
	cin.tie(0);
	unordered_map<string,int> m;
	while(cin>>n){
		m.clear();
		no=1;
		for(int i=0;i<n;i++){
			cin>>s;
			if(m.find(s)!=m.end()){
				cout<<"Old! "<<m[s]<<endl;
			}
			else{
				cout<<"New! "<<no<<endl;
				m[s]=no;
				no++;
			}
		}
	}
}