牛客小白月赛21题解
A
一句话题意：求出平面上一个三角形的外心坐标
题解：列出三角形两条边的垂直平分线方程，联立解方程组即可
代码：
#include<stdio.h>
double A,B,C,D,E,F,ax,bx,cx,ay,by,cy,xc1,yc1,xc2,yc2,dy1,dx1,dy2,dx2;
int main(){
scanf("%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy);
xc1=(ax+bx)*0.5;
yc1=(ay+by)*0.5;
xc2=(ax+cx)*0.5;
yc2=(ay+cy)*0.5;
dx1=by-ay;
dy1=ax-bx;
dx2=cy-ay;
dy2=ax-cx;
A=-dy1;
B=dx1;
D=-dy2;
E=dx2;
C=-dy1*xc1+dx1*yc1;
F=-dy2*xc2+dx2*yc2;
// printf("%.3f %.3f %.3f\n%.3f %.3f %.3f\n",A,B,C,D,E,F);
printf("%.3f %.3f\n",(C*E-B*F)/(A*E-B*D),(A*F-C*D)/(A*E-B*D));
}
B
一句话题意：打印图形化的汉诺塔移动过程
题解：类似汉诺塔移动步骤的递归解法，只不过需要把每一步移动步骤进行图形化显示。算清楚图形长宽，以及如何显示柱子、盘子，在对应位置显示正确的字符即可
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,s[3][20],t[3],tot;
void printhanoi(){
fo(i,1,3*(n+n+1)+4) putchar('.');
putchar('\n');
fd(i,n+1,1){
putchar('.');
fo(j,0,2){
if (t[j]<i){
fo(k,1,n) putchar('.');
putchar('|');
fo(k,1,n) putchar('.');
}else{
fo(k,1,n-s[j][i]) putchar('.');
fo(k,1,s[j][i]) putchar('*');
putchar('*');
fo(k,1,s[j][i]) putchar('*');
fo(k,1,n-s[j][i]) putchar('.');
}
putchar('.');
}
putchar('\n');
}
tot++;
if (tot>>n) return;
fo(i,1,3*(n+n+1)+4) putchar('-');
putchar('\n');
}
void hanoi(int n,int a,int b){
if (n==0) return;
hanoi(n-1,a,3-a-b);
s[b][++t[b]]=s[a][t[a]--];
printhanoi();
hanoi(n-1,3-a-b,b);
}
int main(){
scanf("%d",&n);
fd(i,n,1) s[0][++t[0]]=i;
printhanoi();
if (n&1) hanoi(n,0,1);else hanoi(n,0,2);
return 0;
}C
一句话题意：电视循环播放50个时刻节目和10时刻广告，求t1t2时刻有多少个时刻是节目n时刻有多少个时刻是节目的问题。这个问题装修要将60个时刻作为一个周期就很好计算出来。
题解：转化为1
#include<stdio.h>
long long l,r;
long long ask(long long n){
long long ans=0;
ans=n/60*50;
n%=60;
if (n>50) n=50;
return ans+n;
}
int main(){
while (scanf("%lld%lld",&l,&r)==2){
printf("%lld\n",ask(r)-ask(l-1));
}
return 0;
}D
一句话题意：不难看出路径长度不影响答案。需要求出从DAG起点到终点的路径条数
题解：拓扑排序+动态规划即可。f[i]表示从起点到i的不同路径方案数
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,m,xx,yy,zz,q[110000],f[110000],he,ta,rd[110000],et,be[110000];
long long d[110000],oo,te;
const int p=20010905;
struct edg{
int y,ne;
long long z;
}e[220000];
inline void add_edge(int x,int y,int z){
e[++et].y=y;
e[et].ne=be[x];
e[et].z=z;
be[x]=et;
rd[y]++;
}
int main(){
scanf("%d%d",&n,&m);
fo(i,1,m){
scanf("%d%d%d",&xx,&yy,&zz);
add_edge(xx,yy,zz);
}
q[he=ta=1]=1;
oo=0x3fffffff;oo*=oo;
fo(i,2,n) d[i]=oo;
while (he<=ta){
int &x=q[he];
for(int i=be[x];i;i=e[i].ne){
rd[e[i].y]--;
te=d[x]+e[i].z;
if (te<d[e[i].y]) d[e[i].y]=te;
if (!rd[e[i].y]){
q[++ta]=e[i].y;
}
}
he++;
}
f[1]=1;
fo(t,1,ta){
int &x=q[t];
for(int i=be[x];i;i=e[i].ne){
f[e[i].y]+=f[x];
if (f[e[i].y]>=p) f[e[i].y]-=p;
}
}
printf("%lld\n",f[n]);
return 0;
}E
一句话题意：根据多门课程的平时、期中、期末成绩和比例算出G总GPA
题解：按题意模拟即可
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,ty;
double num,s1,p1,s2,p2,s3,p3;
long double fz,fm;
int main(){
scanf("%d",&n);
fo(i,1,n){
scanf("%d%lf%lf%lf%lf%lf%lf%lf",&ty,&num,&s1,&p1,&s2,&p2,&s3,&p3);
if (ty>1) continue;
fm+=num;
fz+=num*(int(s1*p1+s2*p2+s3*p3+0.5));
}
printf("%.2f\n",double(fz/fm));
return 0;
}F
题目本身就是一句话题意~
题解：利用斐波那契数列的性质，可以推出n为偶数，答案为1，否则答案为-1。可以利用斐波那契数列递推性质证明
#include<stdio.h>
#include<string.h>
char s[11000];
int n;
int main(){
scanf("%s",s+1);
n=strlen(s+1);
if ((s[n]-'0')&1) putchar('-');
printf("1\n");
return 0;
}G
一句话题意：给定一个初始只包含一个数的多重集合n，两人轮流操作，每次操作可以从集合中取出一个数，将其分解为它的两个非1因数，并加入集合中。问先手还是后手先无法操作。
题解：可以发现，胜负只和n可以因数分解为多少个质因子有关。奇数个则先手无法操作，否则后手无法操作
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int cnt,n;
int main(){
scanf("%d",&n);
for(int i=2;i*i<=n;i++) if (n%i==0){
while (n%i==0) n/=i,cnt++;
}
if (n>1) cnt++;
// printf("%d\n",cnt);
if (cnt&1) printf("Nancy\n");else printf("Johnson\n");
return 0;
}H
Hello World问题
#include<stdio.h>
int main(){
printf("\"Happy New Year!\"\n");
}I
一句话题意：求解iloveyou在输入字符串中作为子序列出现多少次(大小写不敏感)
题解：先将字符串统一大小写。然后可以用简单的动态规划求解。枚举输入字符串的每个字符s[i]，f[j]表示到当前字符匹配到iloveyou的第j个字符的s[1..i]中的子序列数目，根据当前字符s[i]简单转移即可
#include<stdio.h>
#include<string.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
char s[1100000];
const int p=20010905;
int n,f[9];
int main(){
scanf("%s",s+1);
n=strlen(s+1);
fo(i,1,n) if (s[i]>='A'&&s[i]<='Z') s[i]+='a'-'A';
f[0]=1;
fo(i,1,n)
switch(s[i]){
case 'u':f[8]+=f[7];if (f[8]>=p) f[8]-=p;break;
case 'o':f[7]+=f[6];if (f[7]>=p) f[7]-=p;f[3]+=f[2];if (f[3]>=p) f[3]-=p;break;
case 'y':f[6]+=f[5];if (f[6]>=p) f[6]-=p;break;
case 'e':f[5]+=f[4];if (f[5]>=p) f[5]-=p;break;
case 'v':f[4]+=f[3];if (f[4]>=p) f[4]-=p;break;
case 'l':f[2]+=f[1];if (f[2]>=p) f[2]-=p;break;
case 'i':f[1]+=f[0];if (f[1]>=p) f[1]-=p;break;
}
printf("%lld\n",f[8]);
return 0;
}J
一句话题意：三维地图走迷宫最短路问题
题解：简单用8个方向的bfs求解即可
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
char s[110][110][110];
int nx,ny,nz,n,qx[1100000],qy[1100000],qz[1100000],qs[1100000],he,ta;
const int dx[6]={1,-1,0,0,0,0};
const int dy[6]={0,0,1,-1,0,0};
const int dz[6]={0,0,0,0,1,-1};
bool vis[110][110][110];
int main(){
scanf("%d",&n);
fo(i,1,n) fo(j,1,n) scanf("%s",s[i][j]+1);
he=ta=1;
qx[1]=qy[1]=qz[1]=qs[1]=1;vis[1][1][1]=1;
while (he<=ta){
fo(i,0,5){
nx=qx[he]+dx[i];
ny=qy[he]+dy[i];
nz=qz[he]+dz[i];
if (nx>0&&ny>0&&nz>0&&nx<=n&&ny<=n&&nz<=n&&s[nx][ny][nz]=='.'&&!vis[nx][ny][nz]){
qs[++ta]=qs[he]+1;
qx[ta]=nx;
qy[ta]=ny;
qz[ta]=nz;
// printf("%d %d %d:%d\n",nx,ny,nz,qs[he]+1);
vis[nx][ny][nz]=1;
if (nx==n&&ny==n&&nz==n){
printf("%d\n",qs[ta]);
return 0;
}
}
}
he++;
}
printf("-1\n");
return 0;
}
恒生电子公司氛围 52人发布
