AcWing 1606. C 语言竞赛
原题链接
简单
作者:
eveer
,
2021-08-26 16:38:35
,
所有人可见
,
阅读 202
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int award[N];//记录每一个人的状态,初始化为-1,表示还没有获奖;0表示冠军;1表示质数,获得小黄人;2表示巧克力奖
bool st[N];//用于遍历所有数的状态
vector<int>prime;//存储质数
bool is_check[N];//用来记录这个人是否已经被访问过
bool is_prime[N];//用来记录是否为质数
void linear_prime(int x)//线性筛法筛出质数
{
for(int i=2;i<=x;i++)
{
if(st[i]==false)//表示第i个数的状态,如果为false说明是质数
{
is_prime[i]=true;
prime.push_back(i);
}
for(int j=0;prime[j]<=x/i;j++)//这里需要注意的是primes[j]*i<x,因为大于x的部分不是因子
{
st[prime[j]*i]=true;
if(i%prime[j]==0)break;
}
}
}
bool whether_prime(int x)
{
if(x<=1)return false;//注意0和1都不是质数,需要特判
for(int i=2;i<=x/i;i++)//这里采用x/i的方式缩小区域实际上是i^2<=x,那么也相当于i<=x/i
if(x%i==0)
return false;
return true;
}
int main()
{
memset(award,-1,sizeof award);//将获奖设置为-1,表示暂时还不清楚获奖情况
int n;
scanf("%d",&n);
linear_prime(n);
for(int i=1;i<=n;i++)//遍历每一个排名
{
int m;
scanf("%d",&m);
if(i==1)award[m]=0;//如果这个人是第一名,则直接将x的获奖设置为0
else//如果这个人不是第一名
{
if(whether_prime(i))//如果这个人的排名是质数,将x的获奖设置为1 is_prime[i]==true
award[m]=1;
else
award[m]=2;
}
}
int k;
scanf("%d",&k);
while(k--)
{
int x;
scanf("%d",&x);
printf("%04d:",x);
if(is_check[x]==false)//表示x这个人还没有被访问过
{
is_check[x]=true;
if(award[x]==0)printf(" Mystery Award\n");
else if(award[x]==1)printf(" Minion\n");
else if(award[x]==2)printf(" Chocolate\n");
else
{
printf(" Are you kidding?\n");
is_check[x]=false;
}
}
else
printf(" Checked\n");
}
return 0;
}