ACM.大一寒假2.15考试

傷城~ 2023-07-06 04:49 82阅读 0赞

**机器人**  
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 <bits/stdc++.h>
    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<sa,vector<sa> >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("\n");
        }
        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 <bits/stdc++.h>
    using namespace std;
    queue<int>q1;
    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\n",tmp2);
                    break;
                }
            }
            printf("%d\n",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<bits/stdc++.h>
    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 <bits/stdc++.h>
    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;//在每轮中的位置
    };
    queue<sa>vis;
    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<<ans<<endl;
        }
        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 <bits/stdc++.h>
    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;//在每轮中的位置
    };
    queue<sa>vis;
    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<<ans<<endl;
        }
        return 0;
    }

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

#include <bits/stdc++.h>
    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<<b[n]<<endl;
        }
        return 0;
    }