[C++知识库]pat乙级 1059 c语言竞赛

做法

#include<iostream>
#include<vector>
using namespace std;
bool isprime(int k){
	for(int i=2;i*i<=k;i++){
		if(k%i==0) return false;
	}
	return true;
}
bool judge(int rank){
	if(rank==1) cout<<":Mystery Award"<<endl;
	else if(isprime(rank)) cout<<":Minion"<<endl;
	else cout<<":Chocolate"<<endl;
}
int main(){
	int n;
	cin>>n;
	string s;bool a[1005]={false};
	vector<string> v(n+1);
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	int k;
	cin>>k;
	int flag=0;
	for(int i=0;i<k;i++){
		cin>>s;
		flag=0;
		cout<<"第"<<i+1<<"输入"<<endl;
		for(int j=1;j<=n;j++){
					//找过但不是查询的不用输出 
			if(v[j]==s){//判断奖励类型 
			flag=1; 
			if(a[j]==true) {cout<<s<<":Checked"<<endl; break;}
			cout<<v[j];
			judge(j);
			a[j]=true;
			
			}
			
		}
		if(flag==0) cout<<s<<":Are you kidding?"<<endl;
	}
	
}

输出
6
1111
6666
8888
1234
5555
0001
6
8888
第1输入
8888:Minion
0001
第2输入
0001:Chocolate
1111
第3输入
1111:Mystery Award
2222
第4输入
2222:Are you kidding?
8888
第5输入
8888:Checked
2222

问题最后一个2222 没有回车空行输入不成功；这个问题在测试用例里会有回车符不用担心，只是你的赋值粘贴后没有；关键是你的代码超时
解决办法：用哈希索引去掉内层循环，另外bool数组也可以用set代替

优化 柳婼.

#include <iostream>
#include <set>
#include <cmath>
using namespace std;
int ran[10000];
bool isprime(int a) {
    if(a <= 1) return false;
    int Sqrt = sqrt((double)a);
    for(int i = 2; i <= Sqrt; i++) {
        if(a % i == 0)
            return false;
    }
    return true;
}
int main() {
    int n, k;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int id;
        scanf("%d", &id);
        ran[id] = i + 1;
    }
    scanf("%d", &k);
    set<int> ss;
    for(int i = 0; i < k; i++) {
        int id;
        scanf("%d", &id);
        printf("%04d: ", id);
        if(ran[id] == 0) {
            printf("Are you kidding?\n");
            continue;
        }
        if(ss.find(id) == ss.end()) {
            ss.insert(id);
        } else {
            printf("Checked\n");
            continue;
        }
        if(ran[id] == 1) {
            printf("Mystery Award\n");
        }else if(isprime(ran[id])) {
            printf("Minion\n");
        }else {
            printf("Chocolate\n");
        }
    }
    return 0;
}