day 9：自闭的一天

小咪咪 2024-04-17 05:47 59阅读 0赞

# day 9：自闭的一天 #

又是心态爆炸的一天，不像前几天，今天ccpc网络赛，自闭了…

上午组队训练赛感觉还可以，但是怎么可能都会是这种水题呢，但是水题都有一道没做出来…

**上午训练赛：**

A题：[hdu 2562：奇偶位互换][hdu 2562]

大水题

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    {
        
        char s1[110];
        char ch;
        int t;
        scanf("%d",&t);
        while(t--)
        {
        
            scanf("%s",s1);
            int len1=strlen(s1);
            s1[len1]='\0';
            for(int i=0;i<len1;i+=2)
            {
        
                ch=s1[i];
                s1[i]=s1[i+1];
                s1[i+1]=ch;
            }
            printf("%s\n",s1);
        }
    }

B题：[hdu 2710：Max Factor][hdu 2710_Max Factor]

一道简单的素数题  
我是直接先素数筛预处理，然后找最大值，时间复杂度感觉比别人的要好点

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int  vis[20010];
    int main()
    {
        
        memset(vis,0,sizeof(vis));
        for(int i=2;i<=20000;i++)
        {
        
            if(vis[i]==0)
            {
        
                for(int j=i;j<=20000;j+=i)
                {
        
                    vis[j]=i;
                }
            }
        }
        vis[1]=1;
        int n;
        int num,ans;
        while(~scanf("%d",&n))
        {
        
            int maxPrime=-1;
            for(int i=1;i<=n;i++)
            {
        
                scanf("%d",&num);
                if(vis[num]>maxPrime)
                {
        
                    maxPrime=vis[num];
                    ans=num;
                }
            }
            printf("%d\n",ans);
        }
    }

C题：[hdu 2188：悼念512汶川大地震遇难同胞——选拔志愿者][hdu 2188_512]

又是一道类似于博弈的题  
说到底就是找规律，直接扔给了队友，关键我太菜了

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    {
        
        int t;
        int n,m;
        scanf("%d",&t);
        while(t--)
        {
        
            scanf("%d%d",&n,&m);
            if(n<=m)
            {
        
                printf("Grass\n");
                continue;
            }
            if(n%(m+1)==0)
                printf("Rabbit\n");
            else
                printf("Grass\n");
        }
        return 0;
    }

D题：[hdu 1253：胜利大逃亡][hdu 1253]

一道三维的迷宫题，当时没有做出来…

刚补完题，感觉好像也就那回事，就是因为是个三维的被吓到了  
其实和二维处理差不多

看网上代码DFS似乎会TLE，大多数都是用的BFS

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<cmath>
    using namespace std;
    const int maxn=55;
    int mp[maxn][maxn][maxn];    //三维迷宫
    int vis[maxn][maxn][maxn];
    int tx[]={
        1,-1,0,0,0,0};
    int ty[]={
        0,0,1,-1,0,0};
    int tz[]={
        0,0,0,0,1,-1};
    int a,b,c,t;          //题目中的a,b,c,t
    int ans;
    struct node
    {
        
        int x,y,z;
        int step;
    };
    /**判断是否越界*/
    int check(int i,int j,int k)
    {
        
        if(i<0||j<0||k<0||i>=a||j>=b||k>=c||mp[i][j][k])
            return 0;
        return 1;
    }
    int bfs(int x,int y,int z)
    {
        
        queue<node>Q;
        node p,q;
        p.x=x;
        p.y=y;
        p.z=z;
        p.step=0;
        vis[x][y][z]=1;
        Q.push(p);
        while(!Q.empty())
        {
        
            p=Q.front();
            Q.pop();
            if(p.x==a-1&&p.y==b-1&&p.z==c-1&&p.step<=t)
            {
        
                return p.step;
            }
            for(int i=0;i<6;i++)
            {
        
                q=p;
                q.x+=tx[i];
                q.y+=ty[i];
                q.z+=tz[i];
                if(vis[q.x][q.y][q.z]==0&&check(q.x,q.y,q.z))
                {
        
                    q.step++;
                    vis[q.x][q.y][q.z]=1;
                    /**由于行走只能朝6个固定方向，这里是对剩下时间里能否走到出口进行预判，如果走最短路径依然不能再规定时间内到达出口，明显是不行的,当然不加这个判断也能AC，只是比较消耗时间*/
                    /*if(fabs(q.x-a+1)+fabs(q.y-b+1)+fabs(q.z-c+1)+q.step>t)
                    {
                        continue;
                    }*/
                    Q.push(q);
                }
            }
        }
        return -1;
    }
    int main()
    {
        
        int Case;        //测试数据数量
        scanf("%d",&Case);
        while(Case--)
        {
        
            scanf("%d%d%d%d",&a,&b,&c,&t);
            memset(mp,0,sizeof(mp));
            memset(vis,0,sizeof(vis));
            for(int  i=0;i<a;i++)
            {
        
                for(int j=0;j<b;j++)
                {
        
                    for(int k=0;k<c;k++)
                    {
        
                        scanf("%d",&mp[i][j][k]);
                    }
                }
            }
            ans=bfs(0,0,0);
            printf("%d\n",ans);
        }
        return 0;
    }

E题：[hdu 2570：迷瘴][hdu 2570]

一道可以说是个贪心吧，其实还挺简单的，但是就是有点精度需要考虑，导致我WA了好几次…

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
    {
        
        int t;
        int n,V,W;
        int maxnum;           //表示当前的药水浓度综合
        int num;            //表示用多少种药水被使用
        int P[110];
        scanf("%d",&t);
        while(t--)
        {
        
            memset(P,0,sizeof(P));
            scanf("%d%d%d",&n,&V,&W);
            for(int i=0;i<n;i++)
                scanf("%d",&P[i]);
            sort(P,P+n);
            if(P[0]>W)
                printf("0 0.00\n");
            else
            {
        
                num=1;
                maxnum=P[0];
                for(int i=1;i<n;i++)
                {
        
                    if((maxnum+P[i])<=(num+1)*W)        //用乘号减少精度丢失
                    {
        
                        maxnum+=P[i];
                        num++;
                    }
                    else
                        break;
                }
                printf("%d %.2f\n",num*V,(maxnum)/(num*100.0));       //注意一定要乘V，开始还乘的100，佛了
            }
        }
        return 0;
    }

下午的ccpc网络赛不想说话，完全自闭…

[hdu 2562]: http://acm.hdu.edu.cn/showproblem.php?pid=2562
[hdu 2710_Max Factor]: http://acm.hdu.edu.cn/showproblem.php?pid=2710
[hdu 2188_512]: http://acm.hdu.edu.cn/showproblem.php?pid=2188
[hdu 1253]: http://acm.hdu.edu.cn/showproblem.php?pid=1253
[hdu 2570]: http://acm.hdu.edu.cn/showproblem.php?pid=2570