PAT甲级1116题（欢乐竞赛）

1.题目介绍

prime number：质数
query：疑问

2.考察点，难度

散列类，Map容器插入方法，Set容器的运用，难度易

3.解题代码

#include<unordered_map>
#include<iostream>
#include<set>
using namespace std;
bool isPrime(int n){
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
int main()
{
    int n, k, id;
    scanf("%d", &n);
    unordered_map<int,int> rank;
    for (int i = 0; i < n; i++){
        scanf("%d", &id);
        rank.insert({id,i+1});
    }
    set<int> checked;
    scanf("%d", &k);
    for (int i = 0; i < k; i++){
        scanf("%d", &id);
        if (rank.find(id) == rank.end()) printf("%04d: Are you kidding?\n", id);
        else {
            if (checked.find(id) != checked.end()) printf("%04d: Checked\n", id);
            else {
                checked.insert(id);
                if (rank[id] == 1) printf("%04d: Mystery Award\n", id);
                else if (isPrime(rank[id])) printf("%04d: Minion\n", id);
                else printf("%04d: Chocolate\n", id);
            }
        }
    }
    return 0;
}

// ************* 超时版 *************
//#include <iostream>
//#include <string>
//#include <cstring>
//#include <map>
//using namespace std;
//
//int find_first(string n, string *b, int k){
//    for(int i=0;i<k;i++){
//        if(b[i]==n){
//            return i;
//        }
//    }
//    return -1;
//}
//
//int main(){
//
//    int N,K;
//    map<string,int> m;
//    string s;
//    scanf("%d",&N);
//    getchar();
//    for(int i=0;i<N;i++){
//        getline(cin,s);
//        m.insert(pair<string,int>(s,i+1));
//    }
//
//    scanf("%d",&K);
//    getchar();
//    string *b=new string[K];
//    for(int j=0;j<K;j++){
//        getline(cin,b[j]);
//
//        if(m[b[j]]==0){
//            cout<<b[j]<<": Are you kidding?"<<endl;
//            continue;
//        }
//
//        if(find_first(b[j],b,j+1)<j){
//            cout<<b[j]<<": Checked"<<endl;
//        }
//        else{
//            if(m[b[j]]==1){
//                cout<<b[j]<<": Mystery Award"<<endl;
//            }
//            else if(m[b[j]]==2||m[b[j]]==3){
//                cout<<b[j]<<": Minion"<<endl;
//            }
//            else{
//                cout<<b[j]<<": Chocolate"<<endl;
//            }
//        }
//    }
//
//    return 0;
//}

4.原题地址

https://pintia.cn/problem-sets/994805342720868352/problems/994805355358306304