牛客小白月赛21全解

2020/01/19 19:16
阅读数 21

题目链接:https://ac.nowcoder.com/acm/contest/3947#question

emmm,小白赛,G题手贱,送了4发,出了8题,B,D没有出来(rank 59)

题目说明:

A.三角形外心求解 B.大模拟 C.前缀和思想
D.记忆化搜索或拓扑排序 E.水题 F.斐波那契数列性质
G.数论+思维 H.水题 I.子序列DP

J.三维BFS

 

 

 

 

 

 

 

 

A-Audio:

题目大意:给你3个点的坐标,让你找到一个点使得该点的到3点的距离一样。给个样例:

Input:

0 0
1 3
4 2

Output:

2.000 1.000

 

 

 

 

 

 

 

emmm,三点不在一条直线上,则可构成三角形,那么三角形的外心到三点的距离是一样的,然后套个三角形外心的公式就OK了,

具体求解过程:https://blog.csdn.net/u010141928/article/details/88942989

以下是AC代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double x1,y1,x2,y2,x3,y3;
    double a,b,c,p;
    double  aa,bb,zz,aa1,bb1,zz1;
    scanf("%lf%lf",&x1,&y1);
    scanf("%lf%lf",&x2,&y2);
    scanf("%lf%lf",&x3,&y3);
    aa=2*(x1-x2);
    bb=2*(y1-y2);
    zz=x1*x1-x2*x2+y1*y1-y2*y2;
    aa1=2*(x3-x2);
    bb1=2*(y3-y2);
    zz1=x3*x3-x2*x2+y3*y3-y2*y2;
    printf("%.3lf %.3lf\n",((zz*bb1)-(zz1*bb))/((aa*bb1)-(aa1*bb)),
           ((aa*zz1)-(aa1*zz))/((aa*bb1)-(aa1*bb)));
    return 0;
}
View Code

 

B-Bits:

题目大意:给你圆盘的个数n,求汉诺塔的移动过程,并将其绘制出来,如果n是奇数则移动到中间的柱子,否则就移动到最右边的柱子上。给个样例:

Input:

2

Output:

...................
...|.....|.....|...
..***....|.....|...
.*****...|.....|...
-------------------
...................
...|.....|.....|...
...|.....|.....|...
.*****..***....|...
-------------------
...................
...|.....|.....|...
...|.....|.....|...
...|....***..*****.
-------------------
...................
...|.....|.....|...
...|.....|....***..
...|.....|...*****.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

emmm,外观上有点问题,只不过在屏幕上每个字符大小是一样的就很整齐了。

我们先移动盘子,不考虑画图,那么程序很好写,当n为奇数的时候,我们将第二个柱子当做第三柱子进去就好了:

void move(int n,int a,int b,int c)
{
    if (n==1) {solve(a,c);return;}
    move(n-1,a,c,b);
    solve(a,c);//将a移动到c
    move(n-1,b,a,c);
}

int main()
{
    int n;
    scanf ("%d",&n);
    sum=n;
    int a=1,b=2,c=3;
    move(n,a,b,c);
    return 0;
}
View Code

接下来就是画图了。。。这就是个纯粹的大模拟,不过为了简化它,我们可以将每层分为三个部分,然后找到柱子的位置和盘子的范围。

以下是AC代码:

#include <bits/stdc++.h>
using namespace std;

vector<int>g[10];
int sum,tot;
char pan='*',zhu='|',kong='.',ge='-';

void print()
{
    tot--;
    int n=sum;
    int len=3*(2*sum+1)+4;
    for (int i=1; i<=len; i++) printf ("%c",kong);printf ("\n");
    for (int i=1; i<=3; i++){
        printf("%c",kong);
        int round=(2*sum+1)/2+1;
        for (int j=1; j<=sum*2+1; j++)
            if (j==round) printf("%c",zhu);
            else printf("%c",kong);
    }
    printf("%c\n",kong);
    for (int i=n; i>=1; i--){//第几层
        for (int j=1; j<=3; j++){//第几个柱子
            printf("%c",kong);
            int h=g[j].size();
            int round=(2*sum+1)/2+1;//柱子的位置
            for (int k=1; k<=2*sum+1; k++){//每个柱子管辖的范围
                if (h<i){
                    if (k==round) printf("%c",zhu);
                    else printf("%c",kong);
                }
                else {
                    int length=g[j][i-1];
                    int l=round-length,r=round+length;//盘子的范围
                    if (k>=l && k<=r) printf("%c",pan);
                    else printf("%c",kong);
                }
            }
        }
        printf("%c\n",kong);
    }
    if (tot==0) return;
    for (int i=1; i<=len; i++) printf ("%c",ge);printf("\n");
}

void solve(int a,int b)
{
    int p=g[a].size()-1;
    g[b].push_back(g[a][p]);
    g[a].erase(g[a].begin()+p);
    print();
}

void move1(int n,int a,int b,int c)
{
    if (n==1) {solve(a,c);return;}
    move1(n-1,a,c,b);
    solve(a,c);
    move1(n-1,b,a,c);
}

int main()
{
    int n;
    scanf ("%d",&n);
    sum=n;
    tot=1;
    for (int i=1; i<=n; i++) tot*=2;
    for (int i=n; i>=1; i--) g[1].push_back(i);
    int a=1,b=2,c=3;
    print();
    if ((n%2)==0) move1(n,a,b,c);
    else move1(n,a,c,b);
    return 0;
}
View Code

 

C-Channels:

题目大意:给你一个区间让你求有多少时间是在看剧。其中电视在时刻1开始到无穷,每50分钟后有10分钟的广告。给个样例:

Input:

1 61

Output:

51

 

 

 

 

 

emmm,就是利用一下前缀和的思想,我们用sum[r]-sum[l-1]就完事了。我们直接除60,然后再减一下,剩下的就是个不完整的时间,如果这个时间>50,那么就增加广告时间。

以下是AC代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define ll long long

int main(){
    ll t1,t2;
    while (~scanf ("%lld%lld",&t1,&t2)){
        t1--;
        ll sum1=t1/60;
        ll p1=t1-sum1*60;
        if (p1>50) sum1=sum1*10+p1-50;
        else sum1*=10;
        ll ans1=t1-sum1;
        ll sum2=t2/60;
        ll p2=t2-sum2*60;
        if (p2>50) sum2=sum2*10+p2-50;
        else sum2*=10;
        ll ans2=t2-sum2;
        printf ("%lld\n",ans2-ans1);
    }
    return 0;
}
View Code

 

D-DDOoS:

题目大意:给你一张有向图,让你求从1到n有多少条不同的路径。给个样例:

Input:

4 4
1 2 3
1 3 1
2 4 1
3 4 3

Output:

2

 

 

 

 

 

 

 

 

emmm,记忆化搜索,当时题目读错了,以为是最短路径数。。。

以下是AC代码:

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;
const int M=2e5+10;
const int mod=20010905;

int head[N],ans[N],vis[N],num=0;
struct node
{
    int to,next,w;
}eg[M<<1];

void add(int u,int v,int w)
{
    eg[++num]=node{v,head[u],w};
    head[u]=num;
}

int dfs(int x,int ed)
{
    if (x==ed) return 1;
    if (ans[x]) return ans[x];
    for (int i=head[x]; i!=-1; i=eg[i].next){
        int v=eg[i].to;
        ans[x]=(ans[x]+dfs(v,ed))%mod;
    }
    return ans[x]%mod;
}

int main()
{
    int n,m;
    scanf ("%d%d",&n,&m);
    memset(head,-1,sizeof head);
    for (int i=1; i<=m; i++){
        int u,v,w;
        scanf ("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    printf ("%d\n",dfs(1,n));
    return 0;
}
View Code

 

E-Exams:

题目大意:emmm,就是个纯粹的计算题。样例:

Input:

5
0 1 97 1 0 0 0 0
0 2.5 98 0.3 0 0 92 0.7
0 4 100 0.3 0 0 100 0.7
0 1 0 0 0 0 74 1
0 2 94 1 0 0 0 0

Output:

94.67

 

 

 

 

 

 

 

 

 

 

以下是AC代码:

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    double ans=0,sum=0;
    for (int i=1; i<=n; i++){
        int id;
        double pt,c1,p1,qz,p2,qm,p3;
        cin>>id>>pt>>c1>>p1>>qz>>p2>>qm>>p3;
        if (id==2) continue;
        double grd=c1*p1+qz*p2+qm*p3;
        grd*=10;
        int s=(int)grd;
        if (s%10>=5) s+=10;
        s/=10;
        ans+=s*pt;
        sum+=pt;
    }
    ans/=sum;
    printf ("%.2f\n",ans);
    return 0;
}
View Code

 

F-Fool Problem:

题目大意:给你n,让你求$f_{n+1}f_{n-1}-f_{n}^{2}$其中$f$是斐波那契数列。样例:

Input:

2

Output:

1          

 

 

 

 

 

就是利用斐波那契数列的性质,具体的性质:https://www.cnblogs.com/Milkor/p/4734763.html

以下是AC代码:

#include <cstdio>
#include <cstring>
using namespace std;

const int mac=3e3+10;

char s[mac];

int main()
{
    scanf ("%s",s);
    int len=strlen(s);
    int p=s[len-1]-'0';
    if (!(p%2)) printf ("1\n");
    else printf ("-1\n");
    return 0;
}
View Code

 

G-Game:

题目大意:给你一个数n,Nancy和Johnson先后将其拆解为两个任意两个非1因子的积,问谁最后无法操作。样例:

Input:

4

Output:

Johnson

 

 

 

 

 

实际上这题就是问n的质因子的个数,如果个数为奇数,那么就是就是Nancy输掉,但我们要特判一下n是否为质数或者1。

至于为什么,除最后一次拆解外,每次拆解得到一个质数和一个合数,我们看看它可以拆解多少次就好了

以下是AC代码:

#include <bits/stdc++.h>
using namespace std;
 
const int mac=1e5+10;
 
int vis[mac],prim[mac];
int nb;
 
int main()
{
    int n,cnt=0;
    scanf ("%d",&n);
    int m=sqrt(n);
    for (int i=2; i<=m; i++)
        if (!vis[i])
            for (int j=i*i; j<=n; j+=i) vis[j]=1;
    for (int i=2; i<=n; i++)
        if (!vis[i]) prim[++cnt]=i;
    m=n;
    for (int i=1; i<=cnt; i++){
        while (n%prim[i]==0 && m!=prim[i]) nb++,n/=prim[i];
    }
    n=m;
    if (!vis[n]) printf ("Nancy\n");
    else if (nb%2) printf ("Nancy\n");
    else if (!(nb%2)) printf ("Johnson\n");
    return 0;
}
View Code

 

H-"Happy New Yeay!":

题目大意:输出题目

注意连引号也要输出,用一下转义字符就好了,同时不能直接复制,它是中文的引号当时。

以下是AC代码:

#include <cstdio>
int main()
{
    printf ("\"Happy New Year!\"\n");
    return 0;
}
View Code

 

I-I Iove you:

题目大意:给你一个字符串,让你求iloveyou作为子序列出现了多少次,大小写不区分。对20010905取模。样例:

Input:

IloveyouNotonlyforwhatyouareButforwhatIamWhenIamwithyouIloveyouNotonlyforwhatYouhavemadeofyourselfButforwhatYouaremakingofme

Output:

2864

 

 

 

 

emmm,是个dp。令 $f[i][j],(j = 1...8)$ 表示前 i 个字符中,匹配了字符串”iloveyou” 的前多少位,那么有转移方程:

$f[i][j] = (f[i−1][j] + (s[i] ==ss[j])∗f[i−1][j]) % mod$

当然,$f[i][1]$比较特殊:$f[i][1] = (f[i−1][1] + (s[i] ==′ i′)) % mod$

以下是AC代码:

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mac=1e6+10;
const int mod=20010905;

ll dp[10];

int main(){
    string s;
    cin>>s;
    string m="iloveyou";
    for(int i=0;i<s.length();i++){
        s[i]=tolower(s[i]);  
        for (int j=8; j>=1; j--){
            if (j==1) dp[j]=(dp[j]+(s[i]==m[j-1]))%mod;
            else dp[j]=(dp[j]+(s[i]==m[j-1])*dp[j-1])%mod;
        }
    }
    cout<<dp[8]<<endl;
    return 0;
}
View Code

 

J-Jelly:

题目大意:从(1,1,1)到(n,n,n)至少需要多少时间,n层,每层n行n列。样例:

Input:

2
.*
..
*.
..

Output:

4

 

 

 

 

 

 

 

 

实际上就是个三维的BFS,和POJ2251一样。这里注意特判一下n等于1的情况就好了,然后注意起点入队的时候放入的时间是1。

#include <cstdio>
#include <cstring>
#include <queue>
#define BYJ(cx,cy,cl,cen,n,m) (cx>=1)&&(cx<=n)&&(cy>=1)&&(cy<=m)&&(cl>=1)&&(cl<=cen)
using namespace std;
const int mac=110;
int dre[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};  //{x,y,z的走向}
int a[mac][mac][mac],v[mac][mac][mac];
int main() {
    int cen,n,m;
    while (~scanf ("%d",&n)) {
        cen=m=n;
        memset(a,0,sizeof(a));
        memset(v,0,sizeof(v));
        queue<int>qx,qy,ql,stp;     
        int sx,sy,sc,fx,fy,fc,mark=0;
        for (int k=1; k<=cen; k++)
            for (int i=1; i<=n; i++)
                for (int j=1; j<=m; j++) {
                    char ch=getchar();
                    while (ch!='.' && ch!='*') ch=getchar();
                    if (ch=='*') a[k][i][j]=1;
                }
        if (n==1) {printf ("1\n");return 0;}
        sx=sy=sc=1;
        fx=fy=fc=n;
        qx.push(sx),qy.push(sy),ql.push(sc),stp.push(1);//注意刚开始是1
        v[sc][sx][sy]=1;
        while (!qx.empty()) {
            if (mark) break;   
            for (int i=0; i<6; i++) {    //六种方向入队
                    int cx,cy,cl;
                    cx=qx.front()+dre[i][0];   
                    cy=qy.front()+dre[i][1];
                    cl=ql.front()+dre[i][2];    //层数
                if (BYJ(cx,cy,cl,cen,n,m) && !a[cl][cx][cy] && !v[cl][cx][cy]) {
                    if (cx==fx && cy==fy && cl==fc) {
                        printf ("%d\n",stp.front()+1);
                        mark=1;break;            
                    }
                    v[cl][cx][cy]=1;
                    qx.push(cx),qy.push(cy),ql.push(cl),stp.push(stp.front()+1);
                }
            }
            if (mark) break;
            qx.pop(),qy.pop(),ql.pop(),stp.pop();
        }
        if (!mark) printf ("-1\n");
    }
    return 0;
}
View Code
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部