PAT 乙级 1059 C语言竞赛 （20分）_pat比赛c语言竞赛

---

题目

C 语言竞赛是浙江大学计算机学院主持的一个欢乐的竞赛。既然竞赛主旨是为了好玩，颁奖规则也就制定得很滑稽：

0、冠军将赢得一份“神秘大奖”（比如很巨大的一本学生研究论文集……）。
1、排名为素数的学生将赢得最好的奖品 —— 小黄人玩偶！
2、其他人将得到巧克力。
给定比赛的最终排名以及一系列参赛者的 ID，你要给出这些参赛者应该获得的奖品。

输入格式：
输入第一行给出一个正整数 N（≤10 4 ），是参赛者人数。随后 N 行给出最终排名，每行按排名顺序给出一位参赛者的 ID（4 位数字组成）。接下来给出一个正整数 K 以及 K 个需要查询的 ID。

输出格式：
对每个要查询的 ID，在一行中输出 ID: 奖品，其中奖品或者是 Mystery Award（神秘大奖）、或者是 Minion（小黄人）、或者是 Chocolate（巧克力）。如果所查 ID 根本不在排名里，打印 Are you kidding?（耍我呢？）。如果该 ID 已经查过了（即奖品已经领过了），打印 ID: Checked（不能多吃多占）。

输入样例：
6
1111
6666
8888
1234
5555
0001
6
8888
0001
1111
2222
8888
2222
输出样例：
8888: Minion
0001: Chocolate
1111: Mystery Award
2222: Are you kidding?
8888: Checked
2222: Are you kidding?

---

分析

一、创建数组ID[10001] 用于记录每个ID值对应的名次（默认值为0，表示不存在ID）

二、创建字典string dic[5],五种奖品分别对应五种状态（用flag表示状态）：
  ①flag=0，ID存在且第一名
  ②flag=1，ID存在且名次为素数
  ③flag=2，ID存在且名次不为素数
  ④flag=3，ID不存在
  ④flag=4，ID存在但已经查询过

三、接收参赛人数N，记录参赛ID，创建rank[N+1] 用于保存每个名次对应的奖品,其值为上述flag
对N进行循环，对于第i次循环进行以下操作：
1.将参赛ID存储到temp中,将ID[temp]++ 表示该ID参赛
2.由于参赛者的ID是根据排名给出的，因此第i次循环表示该选手的排名为i+1，判断排名是否为素数：
  ① 素数，rank[i+1]=1
  ②非素数，rank[i+1]=2
结束循环后令 rank[1]=0 ，因为第一名的状态独立于其他选手

四、接收查询人数K，输出查询结果
对K进行循环，对于第i次循环进行一下操作：
1.将需要查询的ID存储到temp中
2.在ID[temp] 中查询参赛名单中该ID是否不存在，即 ID[temp]==0
  ①true, 表示该ID不存此时flag=3,直接输出dic[3]并continue
  ②flase,表示该ID存在此时 ID[temp] 表示了该ID的参赛排名，在rank中查询该参赛排名对应的状态值rank[ID[temp]] 并输出dic[rank[ID[temp]]]，然后该ID已经查询过，更新其状态值 rank[ID[temp]]=4
  ！这里排名和ID是唯一对应，所以操作排名即可

---

代码

#include<iostream>
#include<cmath>
int isPrime(int k){
    int flag = 1;
    for(int i = 2;i<(int)sqrt((double)k)+1;i++){
        if(k % i == 0){
            flag = 2;
            break;
        }
    }
    return flag;
}
using namespace std;
int main(){
    string dic[5]={"Mystery Award","Minion","Chocolate","Are you kidding?","Checked"};
    int N,K,temp,ID[10001];
    scanf("%d",&N);
    int rank[N+1];
    for(int i=0;i<N;i++){
        scanf("%d",&temp);
        ID[temp]=i+1;
        rank[i+1]=isPrime(i+1);
    }
    rank[1]=0;
    scanf("%d",&K);
    for(int i=0;i<K;i++){
        scanf("%d",&temp);
        printf("%04d: ",temp);
        if(ID[temp]==0){
            cout<<dic[3]<<endl;
            continue;
        }
        cout<<dic[rank[ID[temp]]]<<endl;
        rank[ID[temp]]=4;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

总结

一、这道题跟之前有几道一样，运用了创建字典和用数组当做map的思路
二、其实ID[10001]最好手动初始化为0，如果PTA不把数组默认值设为0就会出错了！
三、用sqrt判断素数的时候要记得再+1，不然有测试点0、2会不通过 = =