ZeroJudge A541: 字典

 7000單字

所有高中生的夢魘

但對聰明的有駿可就不一樣了

號稱擁有70000字的他 

對於已經背過的單字嗤之以鼻

因為這讓他感到很無聊

但這世界上總會有他沒見過的單字吧

沒關係

一眼就記住了 

還好

老天是公平的

有駿不會寫程式

他總是對於判斷自己有沒有背過這些單字感到麻煩…… 

聰明的我們

寫個程式幫幫有駿吧 

範例測資

範例輸入範例輸出
每個測資點只有一個測資
第一行有一個整數 N (1 < N < 70000)
代表有駿所知的單字數
接下來的 2 到 N+1 行每行有一個長度不到 20 的不重複英文單字
所有單字僅包含英文小寫字元
第 N+2 行有一個正整數 Q ( 1 < Q < 70000)
接下來的 Q 行每行有一個要查詢的單字
所有單字僅包含英文小寫字元並且長度不到20
對於每一個查詢的單字輸出查詢結果分行輸出
如果有駿已經背過請輸出「yes」
如果有駿尚未背過請輸出「no」同時把此單字放到有駿的腦海中
4
henry
john
mary
cindy
5
andy
cindy
vicky
leo
leo
no
yes
no
no
yes

解題思路

使用 Map 判斷每一個字串是否有出現過,需要注意的是,在判斷 Q 個字串時,有可能會有重複出現相同字串的情況,這種情況下因為已經有出現過一次,就算這個字串沒有出現在N個字串中第二次詢問時也要輸出yes因為已經出現過了

範例程式碼-ZeroJudge A541: 字典

#include <iostream>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    map<string, int>MAP;
    for (int i = 0; i<N; i++)
    {
        string str;
        cin >> str;
        MAP[str]++;
    }
    int Q;
    cin >> Q;
    for (int i = 0; i<Q; i++)
    {
        string str;
        cin >> str;
        if (MAP[str] == 0) cout << "no\n";
        else cout << "yes\n";
        MAP[str]++;
    }
}

//ZeroJudge A541
//Dr. SeanXD

發佈留言