牛客小白月赛21题解

牛客小白月赛21题解

A

题目：给你三个点，求到三个点距离相等的点。

题解：三角形两条中垂线的交点，垂直直线k1*k2=-1

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
#define x1 x[1]
#define x2 x[2]
#define x3 x[3]
#define y1 y[1]
#define y2 y[2]
#define y3 y[3]
const int N=1e6+5;
int n,m,a[N];
char s[N];
double x[N],y[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    for(int i=1;i<=3;i++)x[i]=read(),y[i]=read();
    double k1=(y1-y2)/(x1-x2);
    k1=-1/k1;
    double b1=(y1+y2)/2-(x1+x2)/2*k1;

    double k2=(y1-y3)/(x1-x3);
    k2=-1/k2;
    double b2=(y1+y3)/2-(x1+x3)/2*k2;
    double xx=(b2-b1)/(k1-k2);
    double yy=k1*xx+b1;
    printf("%.3lf %.3lf\n",xx,yy);
    return 0;
}

C

题目：在[1+k * 60,50+k * 60]看电视，其余时间看广告。问在[L,R]中有多少时间看电视。

题解：边界上先处理好，然后中间就数有几个60即可

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
#define x1 x[1]
#define x2 x[2]
#define x3 x[3]
#define y1 y[1]
#define y2 y[2]
#define y3 y[3]
const int N=1e6+5;
int n,m,x,y,a[N],f[N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    while(scanf("%lld%lld",&x,&y)!=EOF)
    {
        int ans=0;
        if(y-x<=300)
        {
            for(int i=x;i<=y;i++)
                if(i%60>0&&i%60<=50)ans++;
            printf("%lld\n",ans);
        }
        else{
            while(x)
            {
                if(x%60==0)break;
                if(x%60>0&&x%60<=50)ans++;
                x++;
            }
            while(y)
            {
                if(y%60==0)break;
                if(y%60>0&&y%60<=50)ans++;
                y--;
            }
            ans+=(y-x)/60*50;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

E

题目：

一名同学的学分是这样计算的：
1.仅计算必修和限选课程
2.根据平时成绩、期中成绩、期末成绩对应的不同比例求和，并四舍五入到整数
3.学分为各门课成绩乘以学分占总学分的比例
4.对计算结果进行四舍五入（保留两位小数）

题解：根据题意模拟即可，仔细读题。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
const int N=1e5+5;
int n,a[N],e[N];
double sum,ans,d[N],c[N],b[N];
//#define int long long
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        for(int j=1;j<=7;j++)scanf("%lf",&b[j]);
        if(a[i]==2)continue;
        sum+=b[1];
        d[i]=b[1];
        c[i]=b[2]*b[3]+b[4]*b[5]+b[6]*b[7];
        e[i]=round(c[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]==2)continue;
        ans+=d[i]/sum*e[i];
    }
    printf("%.2lf\n",ans);
    return 0;
}

F

题目：F为斐波那契数列，求F[n+1] * F[n-1] - F[n] * F[n]

题解：打表找规律得，偶数为1，奇数为-1

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
#define x1 x[1]
#define x2 x[2]
#define x3 x[3]
#define y1 y[1]
#define y2 y[2]
#define y3 y[3]
const int N=1e6+5;
int n,m,a[N],f[N];
char s[N];
double x[N],y[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    n=read();
    if(n%2==0)puts("1");
    else puts("-1");
    return 0;
}

G

题目：

两人博弈，两个人轮流进行操作。
一次操作可以将集合中一个数字分解为它的任意两个非1的因数，并加入集合中。
在Johnson和Nancy绝顶聪明的情况下，如果Nancy先手进行操作，最后谁没有办法继续操作了呢？

题解：发现每个数是独立的，即对每个数都有一个胜负。直接DP即可，比如X分成A和B，那么根据A和B的DPzhi

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=20010905;
#define x1 x[1]
#define x2 x[2]
#define x3 x[3]
#define y1 y[1]
#define y2 y[2]
#define y3 y[3]
const int N=1e6+5;
int n,m,x,y,a[N],P[N],vis[N],f[N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int dfs(int n)
{
    if(P[n])return 0;
    if(vis[n])return f[n];
    vis[n]=1;
    for(int i=2;i*i<=n;i++)
    if(n%i==0)
    {
        if(dfs(i)+dfs(n/i)==0||dfs(i)+dfs(n/i)==2)
        {
            f[n]=1;
            return 1;
        }
    }
    f[n]=0;
    return 0;
}
signed main()
{
    n=read();
    P[2]=1;
    for(int i=3;i<=n;i++)
    {
        P[i]=1;
        for(int j=2;j*j<=i;j++)
            if(i%j==0)
            {
                P[i]=0;
                break;
            }
    }
    if(dfs(n))puts("Johnson");
    else puts("Nancy");
    return 0;
}

H

题目：输出"Happy New Year!"

题解：输出"Happy New Year!"

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
#define x1 x[1]
#define x2 x[2]
#define x3 x[3]
#define y1 y[1]
#define y2 y[2]
#define y3 y[3]
const int N=1e6+5;
int n,m,a[N];
char s[N];
double x[N],y[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    puts("\"Happy New Year!\"");
    return 0;
}

I

题目：问一个串中，iloveyou作为子序列出现的次数。

题解：记录i,il,ilo,ilov,ilove,ilovey,iloveyo,iloveyou在前i个字符中出现了几次。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=20010905;
#define x1 x[1]
#define x2 x[2]
#define x3 x[3]
#define y1 y[1]
#define y2 y[2]
#define y3 y[3]
const int N=1e6+5;
int n,m,x,y,a[N],f[N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='i')a[1]++;
        if(s[i]=='l')a[2]+=a[1];
        if(s[i]=='o')a[3]+=a[2];
        if(s[i]=='v')a[4]+=a[3];
        if(s[i]=='e')a[5]+=a[4];
        if(s[i]=='y')a[6]+=a[5];
        if(s[i]=='o')a[7]+=a[6];
        if(s[i]=='u')a[8]+=a[7];

        if(s[i]=='I')a[1]++;
        if(s[i]=='L')a[2]+=a[1];
        if(s[i]=='O')a[3]+=a[2];
        if(s[i]=='V')a[4]+=a[3];
        if(s[i]=='E')a[5]+=a[4];
        if(s[i]=='Y')a[6]+=a[5];
        if(s[i]=='O')a[7]+=a[6];
        if(s[i]=='U')a[8]+=a[7];
        for(int j=1;j<=8;j++)a[j]%=mod;
    }
    cout<<a[8]<<endl;
    return 0;
}

J

题目：n * n * n的立方体，求从(1,1,1)走到(n,n,n)，只走"."的最短路径长度。

题解：宽搜即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=20010905;
#define x1 x[1]
#define x2 x[2]
#define x3 x[3]
#define y1 y[1]
#define y2 y[2]
#define y3 y[3]
const int N=1e6+5;
const int M=105;
int n,m,x,y,vis[M][M][M],dis[M][M][M];
char s[M],a[M][M][M];
struct node{
    int x,y,z;
};
queue<node>q;
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
bool pd(int x,int y,int z)
{
    if(x<1||x>n||y<1||y>n||z<1||z>n)return 0;
    if(a[x][y][z]=='*')return 0;
    if(vis[x][y][z])return 0;
    return 1;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%s",s+1);
            for(int k=1;k<=n;k++)a[i][j][k]=s[k];
        }
    q.push((node){1,1,1});
    vis[1][1][1]=1;
    dis[1][1][1]=1;
    while(!q.empty())
    {
        node u=q.front();q.pop();
        int x=u.x,y=u.y,z=u.z,k=dis[x][y][z]+1;
        if(pd(x-1,y,z))
        {
            node v=(node){x-1,y,z};
            vis[x-1][y][z]=1;
            dis[x-1][y][z]=k;
            q.push(v);
        }
        if(pd(x+1,y,z))
        {
            node v=(node){x+1,y,z};
            vis[x+1][y][z]=1;
            dis[x+1][y][z]=k;
            q.push(v);
        }
        if(pd(x,y-1,z))
        {
            node v=(node){x,y-1,z};
            vis[x][y-1][z]=1;
            dis[x][y-1][z]=k;
            q.push(v);
        }
        if(pd(x,y+1,z))
        {
            node v=(node){x,y+1,z};
            vis[x][y+1][z]=1;
            dis[x][y+1][z]=k;
            q.push(v);
        }
        if(pd(x,y,z-1))
        {
            node v=(node){x,y,z-1};
            vis[x][y][z-1]=1;
            dis[x][y][z-1]=k;
            q.push(v);
        }
        if(pd(x,y,z+1))
        {
            node v=(node){x,y,z+1};
            vis[x][y][z+1]=1;
            dis[x][y][z+1]=k;
            q.push(v);
        }
    }
    if(vis[n][n][n])cout<<dis[n][n][n];
    else cout<<-1;
    return 0;
}
/*
.....
.**..
.**..
.**..
.*...
*/
xuxuxuxuxu 文章被收录于专栏

信息学竞赛

全部评论

相关推荐

昨天 18:04
南开大学 电子工程师
租房踩坑，没人比我更惨
当时刚工作，第一个房子就在蛋壳租的。晚上九点左右刚下班到家，听到外面大门的敲门声，狂拍！最开始还以为是宿友叫的外卖和快递，没怎么搭理，结果敲门声越来越响，我一开门，房东直接往里面走，叫了所有租客直接宣告蛋壳跑路，然后告诉我们去维权申诉。大无语，就在前两天蛋壳才扣了我一个季度的房租，押金也没退！！！我交的钱蛋壳也都没给房东！房东说按照规定的话必须在15天内搬走，除非跟房东再重新签约，相当于我前几天交的房租打水漂了，又要重新给房东交租！当时我真的都快崩溃了，只能给爸妈打电话了。&nbsp;在此奉劝广大毕业生、实习生，有条件的话尽可能跟房东直租吧！
我的租房踩坑经历
点赞 评论 收藏
分享
06-03 15:52
已编辑
太原理工大学 Java
点赞 评论 收藏
分享
04-17 10:16
门头沟学院 Java
哎，不想说什么了这让刚毕业的学生怎么搞
小浪_coder：24届很难找了,马上25的都毕业了还有很多没找到的
点赞 评论 收藏
分享
04-11 00:51
已编辑
门头沟学院 Java
两个月的努力，抵不过一纸offer
先说一下楼主的情况：双非本大三，两段实习，javaer，想要找一个暑期大厂offer，努力了两个月，三月份每天的状态就是算法，八股，项目，四月份更是一个面试没有，最终还是没有结果，心碎了一地。期间面了一些中小厂，大厂只有腾讯约面，其他大厂都投了一遍，但是还是石沉大海。再看一下楼主的面试结果吧，就不说ttl了腾讯s3:三面挂csig：一面挂teg：三面挂wxg：一面挂没错，面了八次腾讯，两次三面挂，当时真的心都碎了。其他中小厂都有面，有的没过，有的oc，但是都没有去。其他大厂投了简历，但是不是简历挂，就是测评挂，都说今年行情好很多，各大厂都扩招，可是问题出在那里呢？学历背景吗？实习经历吗？还是简历不够好看？依稀记得，从年初七就离开了家里，回到学校，早早准备面试，当时自己认为凭借着自己的两段实习经历，以及大二就开始准备的八股算法，拿大厂offer不是问题，但是还是不敢放松，回校的状态每天就是算法，八股，还有查看各种招聘信息，想着尽早投机会多，但是事实证明，投的早，不如投的刚刚好。当时想着，先投一些中小厂开始面试，找找面试感觉，从2.10就开始有面试了，基本都是线下面试，面试的感觉都很不错，觉得自己的状态慢慢回来了，期间也有oc一些中小厂，但是自己的目标并不在此，只是想练一下手，遂拒。后面投了腾讯的暑期实习基地，不久就约面了，第一次面这么大的厂，多少有点紧张，好在运气还不错，遇到的面试官也比较好，一直干到了三面，期间看牛客有不少说一面就挂了的，感觉自己还是比较幸运的，但是没想到倒在了三面，一周后就挂了，伤心是有的，但是想到这才刚刚开始，还有很多机会，便继续准备下一次面试了，很快，被另外一个部门捞了，一进会议，面试官没开摄像头，看网上说没开摄像头很多都是kpi，但是自己给自己打气，认为面试官只是不方便开摄像头罢了，面完，感觉良好，没问什么很难得问题，基本都答出来了，算法两道也a了一道，感觉实习不会这么严格吧？还是过了一会挂了，因为这个？还是技术不太匹配？面试过程中说搞C++的，心想，搞c++的你面我干啥？唉，这时候有点气馁，然后就接下来半个月没有面试。这时已经是三月底了，看到牛客好多人都已经陆陆续续拿到了offer，看人家的面试准备也没那么早，有0实习的，有没刷算法的，有两个面的，，，唉，反正是一言难尽啊，感觉努力没有什么意义，面试多半是看面试官的感觉，主观性很大啊，只要你技术没有太大的问题。第三次面试腾讯，面试来的比较突然，期间已经有几天没看八股什么的了，临时看了一下之前自己做的面试笔记，但是面试却异常顺利，三天闯到了三面，自己也不敢相信，三面玩感觉也良好，脑子里不得不想着一些“offer结算画面”，但是过了一会查看流程显示“流程终止”，我？哎，当时真的有苦说不出啊，也是一晚没睡。后面就逐渐开始褪去大厂梦了，看着曾经跟自己交流的牛油，朋友，认识的人，觉得他们技术不太如你，算法刷的没你多，进了大厂，但是这又如何呢？能力强不强不是你了说了，面试官说了算。也逐渐知道，不是你能力好就可以了，还得有运气，运气，运气。这个过程太累了，和自己和解吧，不用非得大厂，找个合适一点的就好，放轻松一点。今天有点心事睡不着，闲着想写一些自己的面试过程，勿喷。附上一张面试的情况，公司就不方便透露了。
怒卷的斯科特：八分运气两分实力
点赞 评论 收藏
分享
06-03 07:37
清华大学 BSP工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我的实习收获 #
16826次浏览 318人参与
# 穿越回高考你还会选现在的专业吗 #
13043次浏览 179人参与
# 实习吐槽大会 #
19337次浏览 89人参与
# 我的租房踩坑经历 #
9752次浏览 137人参与
# 晒一晒你的工位 #
81607次浏览 287人参与
# 打工人锐评公司红黑榜 #
144669次浏览 892人参与
# 非技术er求职现状 #
58316次浏览 428人参与
# 提前批过来人的忠告 #
102444次浏览 1114人参与
# 毕业旅行去哪玩儿 #
588次浏览 18人参与
# 携程求职进展汇总 #
524955次浏览 3879人参与
# 高学历就一定能找到好工作吗？ #
47449次浏览 585人参与
# 运营/市场营销人的秋招现状 #
16689次浏览 186人参与
# 你想对下半年说点什么 #
22445次浏览 209人参与
# 你投递的公司有几家约面了？ #
104138次浏览 746人参与
# 招聘要求与实际实习内容不符怎么办 #
100473次浏览 726人参与
# 工作压力大怎么缓解 #
78837次浏览 934人参与
# 运营人求职交流聚集地 #
133456次浏览 978人参与
# 你最满意的offer薪资是哪家公司？ #
25648次浏览 134人参与
# 选完offer后，你后悔学机械吗？ #
29038次浏览 162人参与
# 实习中的菜狗时刻 #
364336次浏览 3289人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务