牛客小白月赛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;
}
/*
.....
.**..
.**..
.**..
.*...
*/