e785 - 12592 - Slogan Learning of Princess

🔗 前往 ZeroJudge 原題

題目描述

題目描述了王子學習口號，公主尋找王子並跟隨他學習口號的情境。給定一組“呼喊口號”與“對應口號”的配對，以及一系列“呼喊口號”，要求輸出對應的“對應口號”。

解題思路

本題的核心是建立一個“呼喊口號”到“對應口號”的映射關係，然後根據輸入的“呼喊口號”查詢對應的“對應口號”。使用 map 資料結構可以有效地實現這個映射關係。程式首先讀取 N 個配對，將“呼喊口號”作為鍵，將“對應口號”作為值存儲到 map 中。然後讀取 Q 行“呼喊口號”，並在 map 中查找對應的“對應口號”並輸出。

複雜度分析

• 時間複雜度: O(N + Q)，其中 N 是配對的數量，Q 是查詢的數量。map 的插入和查找操作平均時間複雜度為 O(log N)，但在此題中，N 的最大值為 20，Q 的最大值為 100，因此可以近似認為是 O(1)。
• 空間複雜度: O(N)，用於存儲 map。

程式碼

#include <bits/stdc++.h>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n;
	string s,y;
	map <string,string> mp;
	cin >> n;
	getline(cin,s);
	while(n--){
		getline(cin,s);
		getline(cin,y);
		mp[s]=y;
	}
	cin >> n;
	getline(cin,s);
	while(n--){
		getline(cin,s);
		cout << mp[s] << "\n"; 
	}
}