ACM.大一寒假2.15考试

发布于:2021-06-24 15:46:40

机器人
Problem:A
Time Limit:1000ms
Memory Limit:65535K
Description
机器人Bo很聪明,会做许多事情。惟独对自然数的理解与人类不一样,它是从右往左读数。比如,它看到123时,会理解成321.让它比较23与15哪一个大,它说15大。原因是它的大脑会以为是32与51在进行比较.再比如让它比较29与30,它说29大。 当然对于像90,它会把它当成9处理。给定Bo N个自然数x,让它将这N个数按从小到大排序出来。你会认为它如何排序?
Input
第一行: N表示有多少个数. (2<=N<=25 )
接下来有N个数字x.( 0<=x<1e9 )
Output
对于每一行测试数据,输出一行,为所有排好序的元素,元素之间有一个空格.
Sample Input
3
45 69 87
4
66 98 34 32
Sample Output
45 87 69
32 34 66 98


签到题,写一个函数来按要求转换数字,根据转换后的数字比较,创建一个结构体比较即可,我用优先队列来做纯粹是熟练一下,
实际没必要,竟然因为多一个空格PE了两次,我真的撒币。


#include
using namespace std;
struct sa
{
int real;//原来的值
int now;//转化后的值
};
int fun(int x)
{
int temp=x,temp1,cnt=0;
int zhi=0;
while(temp)
{
temp/=10;
cnt++;
}
int g=(int)pow(10,cnt-1);
while(x)
{
temp1=x%10;
zhi+=temp1*g;
g/=10;
x/=10;
}
return zhi;
}
bool operator < (const sa &s1,const sa &s2)//根据转换后的值从小到大排列
{
return s1.now>s2.now;
}
priority_queue >q1;
int main()
{
int N;
while(scanf("%d",&N)!=-1)
{struct sa a[N+1];
for(int i=1;i<=N;i++)
{
scanf("%d",&a[i].real);
a[i].now=fun(a[i].real);
q1.push(a[i]);
}
while(q1.size()>0)
{
int tmp1=q1.top().real;
if(q1.size()>1)
{printf("%d ",tmp1);
q1.pop();}
else
{
printf("%d",tmp1);
q1.pop();
}
}
printf("
");
}
return 0;
}

纸牌游戏
Problem:B
Time Limit:1000ms
Memory Limit:65535K
Description
小明闲来无事,看到了一堆纸牌(编号从1到N)放在了他的面前,他想到了一个好办法打发时间。他把第一张牌扔掉然后把新的第一张牌放入整叠纸牌的最后面。不断的重复操作,直到只剩一张牌,他想知道在这个过程中他扔了哪些纸牌,最后留下的是哪张纸牌。
Input
第1行输入T代表数据组数。(T<=50)
第2行到第1+T行输入纸牌的数量N(1<=N<=50)。
Output
第一行按顺序输出扔掉的纸牌。
第二行输出最后剩下的纸牌。
若没有扔掉的纸牌,则只输出剩下的纸牌
Sample Input
1
7
Sample Output
1,3,5,7,4,2
6
队列模板题,没话说吧。


#include
using namespace std;
queueq1;
int main()
{
int T,N;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
q1.push(i);
}
while(q1.size()>1)
{
if(q1.size()!=2)
{int tmp=q1.front();
q1.pop();
printf("%d,",tmp);
int tmp1=q1.front();
q1.pop();
q1.push(tmp1);}
else
{
int tmp2=q1.front();
q1.pop();
printf("%d
",tmp2);
break;
}
}
printf("%d
",q1.front());
q1.pop();
}
return 0;
}

咸鱼连突刺
Problem:C
Time Limit:1000ms
Memory Limit:65535K
Description
宇宙洪荒之时便现于世间,威名显赫的咸鱼家族有着代代相传的高超武技,其中最为咸鱼的,就是“咸鱼连突刺”,其技巧在于精准的控制伤害。咸鱼组长的变态训练方法是,每次攻击时给出两个数字 L 和 R ,新来的咸鱼蛋子们要精准的刺出L 和 R之间最大的素数与最小的素数之和的伤害值(如果之间没有素数,则相当于本回合造成的伤害值为0),两个素数可以是L或者R。而你要帮咸鱼组长计算这天所有的攻击一共打出了多少伤害。
Input
给出攻击次数T,1<=T<=1e4,接下来T行,每行给出两个数字L R 0<=L<=R<1e6。
Output
输出今天的伤害总值
Sample Input
1
1 10
Sample Output
9


先线性筛打表素数,再根据要求输出即可,第一次暴力枚举忘记加breakTL,第二次WA是因为题目要求输出T天的伤害之和,
我分着输出了每一天的伤害值,菜,委婉点说,有点绿色。


#include
const int N=1e6+1;
int prime[N];
int b[N];
int cnt=0,max1=1e6;
int init()
{
memset(b,1,sizeof(b));
b[0]=b[1]=0;
for(int i=2;i<=max1;i++)
{
if(b[i])
{
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&prime[j]*i<=max1;j++)
{
b[prime[j]*i]=0;
if(i%prime[j]==0) break;
}
}
return 0;
}
int judge(int n){
int flag=0;
for(int i=1;prime[i]<=sqrt(n*1.0);i++)
if(n%prime[i]==0) {flag=1;break;}
if(n==1||n==0) flag=1;
return flag;
}
int main()
{
init();
int T;
scanf("%d",&T);
long long sum=0;
while(T--)
{
int L,R,small=0,big=0;
scanf("%d %d",&L,&R);
for(int i=L;i<=R;i++)
{
if(!judge(i))
{
small=i;
break;//正着找到以后一定要break,否则超时
}
}
for(int i=R;i>=L;i--)
{
if(!judge(i))
{
big=i;
break;
}
}
sum+=small;
sum+=big;
}
printf("%lld",sum);//输入的t天的伤害总和。
return 0;
}

库特的素数队列(1)
Problem:E
Time Limit:4000ms
Memory Limit:200000K
Description
由于一个和库特很熟的幼儿园阿姨在某一天突然有急事,所以她拜托库特帮她讲一天的课,正好这天课程的内容是素数。由于大家还小,库特希望能够能以游戏的方式来给他们讲解。幼儿园共有n个孩子(n<=1e7),他们的序号分别是从1到n。库特让这n个孩子按照序号从小到大的顺序从左到右站成一排,然后从左向右依次报数,从第一个人开始,第一个人开始报1,之后每个人报的数字比他左边的人大1。最后报的数为素数的人能进入下一轮。然后进入下一轮的人再按序号从小到大的顺序从左到右站成一排,然后从左向右依次报数,从第一个人开始,第一个人开始报1,之后每个人报的数字比他左边的人大1,最后报的数为素数的人能进入下一轮…重复这个操作直至只剩下一个孩子。库特会给这个孩子奖励,请问你能知道序号为几的孩子能得到库特的奖励吗?
Input
第一行一个正整数T表示数据组数(T<=3)
接下来T行每行一个正整数n表示孩子的数量(n<=1e7)
Output
对于每组数据,输出一行,输出最后得到奖励的孩子的序号
Sample Input
2
2
6
Sample Output
2
5
Hint
解释一下n=6的情况
首先站成一排 1 2 3 4 5 6
第一轮过后还剩下 2 3 5
然后序号为2的人报1,序号为3的人报2,序号为5的人报3
所以第二轮过后还剩下 3 5
序号为3的人报1,序号为5的人报2
所以第三轮过后还剩下 5一个人
游戏结束


刚开始以为是约瑟夫环问题,不记得公式,后来发现,可以用队列做,结构体成员中要有记录id,当前序号,和第几轮的轮数(用来判断什么时候是下一轮了,序号从初始值给出)。


#include
using namespace std;
const int N=1e7+10;
int prime[2000000];
bool b[N],c[N];
int cnt=0,max1=N;
int init(){
memset(b,1,sizeof(b));
b[0]=b[1]=0;
for(int i=2;i<=max1;i++)
{
if (b[i])
{prime[++cnt]=i;
}
for(int j=1;j<=cnt&&prime[j]*i<=max1;j++)
{
b[prime[j]*i]=0;
if (i%prime[j]==0) break;
}
}
return 0;
}
struct sa
{
int id;//编号
int lun;//第几轮
int dis;//在每轮中的位置
};
queuevis;
int main()
{
int t,n,ans;
struct sa tmp;
init();
scanf("%d",&t);
while(t--)
{scanf("%d",&n);
while(!vis.empty())vis.pop();
for(int i=1;i<=n;i++)
vis.push({i,1,i});
int num=0;
while(!vis.empty())
{
tmp=vis.front();
if (vis.size()==1) {ans=tmp.id;break;}
vis.pop();
if (b[tmp.dis])
{
num++;
vis.push({tmp.id,tmp.lun+1,num});//符合条件的轮数加1,扔到队列后面。
}
if (tmp.lun+1==vis.front().lun)//进入下一轮,序号归为0.
num=0;
}
cout< }
return 0;
}

库特的素数队列(2)
Problem:F
Time Limit:4000ms
Memory Limit:200000K
Description
由于一个和库特很熟的幼儿园阿姨在某一天突然有急事,所以她拜托库特帮她讲一天的课,正好这天课程的内容是素数。由于大家还小,库特希望能够能以游戏的方式来给他们讲解。幼儿园共有n个孩子(n<=1e7),他们的序号分别是从1到n。库特让这n个孩子按照序号从小到大的顺序从左到右站成一排,然后从左向右依次报数,从第一个人开始,第一个人开始报1,之后每个人报的数字比他左边的人大1。最后报的数为素数的人能进入下一轮。然后进入下一轮的人再按序号从小到大的顺序从左到右站成一排,然后从左向右依次报数,从第一个人开始,第一个人开始报1,之后每个人报的数字比他左边的人大1,最后报的数为素数的人能进入下一轮…重复这个操作直至只剩下一个孩子。库特会给这个孩子奖励,请问你能知道序号为几的孩子能得到库特的奖励吗?
Input
第一行一个正整数T表示数据组数(T<=30000)
接下来T行每行一个正整数n表示孩子的数量(n<=1e7)
Output
对于每组数据,输出一行,输出最后得到奖励的孩子的序号
Sample Input
2
2
6
Sample Output
2
5
组数这么多,按上面的算法肯定不行了,所以可以将e题稍作修改,找出范围内所有可能的结果,发现是由规律的,打表后写出。
先写一个函数打表找规律。


#include
using namespace std;
const int N=1e7+10;
int prime[2000000];
bool b[N],c[N];
int cnt=0,max1=N;
int init(){
memset(b,1,sizeof(b));
b[0]=b[1]=0;
for(int i=2;i<=max1;i++)
{
if (b[i])
{prime[++cnt]=i;
}
for(int j=1;j<=cnt&&prime[j]*i<=max1;j++)
{
b[prime[j]*i]=0;
if (i%prime[j]==0) break;
}
}
return 0;
}
struct sa
{
int id;//编号
int lun;//第几轮
int dis;//在每轮中的位置
};
queuevis;
int main()
{
int t,n,ans;
struct sa tmp;
init();
//cin>>t;
for(n=/1;n<=1e6;n++)
{
while(!vis.empty()) vis.pop();
//cin>>n;
for(int i=1;i<=n;i++)
vis.push({i,1,i});
int num=0;
while(!vis.empty())
{
tmp=vis.front();
if (vis.size()==1) {ans=tmp.id;break;}//输出最后剩下的一个
vis.pop();
if (b[tmp.dis])
{
num++;
vis.push({tmp.id,tmp.lun+1,num});
}
if (tmp.lun+1==vis.front().lun)//一次筛选已经完成,序号归为0,重新递增。
num=0;
}
cout< }
return 0;
}

再根据规律写出符合题意的程序


#include
using namespace std;
const int N=1e7+1;
int b[N];
int init()
{
b[1]=1;
b[2]=2;
for(int i=3;i<=10000000;i++)
{
if(i>=3&&i<=4) b[i]=3;
if(i>=5&&i<=10) b[i]=5;
if(i>=11&&i<=30) b[i]=11;
if(i>=31&&i<=126) b[i]=31;
if(i>=127&&i<=708) b[i]=127;
if(i>=709&&i<=5380) b[i]=709;
if(i>=5381&&i<=52710) b[i]=5381;
if(i>=52711&&i<=648390) b[i]=52711;
if(i>=648391&&i<=9737332) b[i]=648391;
if (i>=9737333&&i<=10000000) b[i]=9737333;
}
return 0;
}
int main()
{
init();
int t,n;
cin>>t;
while(t--)
{
cin>>n;
cout< }
return 0;
}

相关推荐

最新更新

猜你喜欢