牛客小白月赛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 文章被收录于专栏
信息学竞赛
华为工作强度 840人发布
