牛客练习赛24

程序员文章站 2022-06-07 13:13:50

...

B-凤凰

链接：https://www.nowcoder.com/acm/contest/157/B
来源：牛客网

题目描述

凤凰于飞，翙翙其羽，亦集爰止。

——《诗经·卷阿》

传说，凤凰是百鸟之王。有一天，凤凰要召开百鸟大会，百鸟国是一个由n个节点组成的树，每个节点有一只鸟，开会的节点定在1号节点。每只鸟可以花费1s通过一条边，由于每根树枝(边)的载重有限，只允许一只鸟同时通过。作为会议的策划师，HtBest想知道百鸟国的所有鸟在1点集合最少需要多少秒。

输入描述:

第一行有一个正整数n，表示百鸟国节点个数。
接下来n-1行，第i行两个正整数ai,bi用空格隔开，表示树上节点ai,bi之间有一条边。

输出描述:

第一行一个整数，表示集合最少需要的时间。

示例1

输入

复制

3
1 2
2 3

输出

复制

示例2

输入

复制

3
1 2
1 3

输出

复制

示例3

输入

复制

输出

复制

备注:

对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

PS：由于每个节点都有一只鸟，并且每一秒子节点都在像根节点传送鸟，所以只要求根节点下面站的鸟数最多的节点就行了。

AC代码：

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e6+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int sum[maxn],root[maxn];
void inct(int n)
{
    for(int i=1;i<=n;i++)
        root[i]=i;
}
int find(int x)
{
    if(x==root[x])
        return x;
    return root[x]=find(root[x]);
}
void unite(int x,int y)
{
    int x1=find(x);
    int y1=find(y);
    if(x1!=y1)
        root[x1]=y1;
}
int main()
{
    int n;cin>>n;
    inct(n);
    for(int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        if(x!=1&&y!=1)
            unite(x,y);
    }
    int ans=0;me(sum,0);
    for(int i=1;i<=n;i++)
        sum[find(i)]++;
    for(int i=1;i<=n;i++)
        ans=max(ans,sum[i]);
    cout<<ans<<endl;
    return 0;
}

C-PH试纸

链接：https://www.nowcoder.com/acm/contest/157/C
来源：牛客网

题目描述

PH试纸，是一种检测酸碱度的试纸，试纸红色为酸性，蓝色为碱性。

HtBest有一个PH试纸，试纸被分成了n段，每一段都可以被染色成红色或者蓝色，WHZ在试纸的每一段上都染为一种颜色，HtBest有m个询问，对于每个询问，Ta想知道某种颜色第qi次在什么地方出现。

输入描述:

第一行有两个正整数n，m。
第二行有n个字母(‘R’或’B’)，每个第i个字母表示PH试纸第i段的颜色。
接下来m行，第i行有一个大写字母 ci(‘R’或’B’)和一个正整数qi ，用空格隔开，表示查询颜色ci 第qi 次出现的位置。

输出描述:

共m行，第i行一个整数，表示查询结果，若颜色ci出现次数少于qi次，则输出-1，否则输出颜色qi第ci次出现的位置。

示例1

输入

复制

2 2
RB
R 1
B 1

输出

复制

1
2

示例2

输入

复制

2 2
BB
R 1
B 2

输出

复制

-1
2

示例3

输入

复制

3 3
BRB
B 1
B 2
R 1

输出

复制

1
3
2

备注:

对于100%的测试数据：
1 ≤ n, m ≤ 1000000
所有输入数据不超过1000000。
数据量较大，注意使用更快的输入输出方式。

PS：水题，记录一下，然后二分就行了。

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e6+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
struct node
{
    int x=0,i;
}R[maxn],B[maxn];
int chaxun(node a[],int l,int r,int i)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(a[mid].x==i)
            break;
        if(a[mid].x>i)
            r=mid-1;
        else
        l=mid+1;
    }
    return mid;
}
int main()
{
    string s;
    int n,m;cin>>n>>m;
    cin>>s;
    int lr=1,lb=1;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='R')
        {
            R[lr].i=i+1;
            R[lr].x=R[lr-1].x+1;
            lr++;
        }
        else
        {
            B[lb].i=i+1;
            B[lb].x=B[lb-1].x+1;
            lb++;
        }
    }
    while(m--)
    {
        char s[5];
        int i;
        scanf("%s%d",s,&i);
        if(s[0]=='R')
        {
            if(i>lr-1)
                printf("-1\n");
            else
            {
                int x=chaxun(R,1,lr-1,i);
                printf("%d\n",R[x].i);
            }
        }
        else
        {
            if(i>lb-1)
                printf("-1\n");
            else
            {
                int x=chaxun(B,1,lb-1,i);
                printf("%d\n",B[x].i);
            }
        }
    }
    return 0;
}

D-插排树

链接：https://www.nowcoder.com/acm/contest/157/D
来源：牛客网

题目描述

一年一度的山东省oi夏令营又开始了，每到这个季节，山东的oier们都会欢聚这里，一起学（tuí）习（feì）。当然，为了能更加愉快地学（tuí）习（feì），就少不了要自带电脑，用电便开始成了一种问题，于是便有一种神奇的数据结构诞生了！这就是山东省oi专用数据结构——插排树（如图）

牛客练习赛24

小K为了能更好的学（tuí）习（feì），所以他想尽量的往后做，所以现在请你帮帮他，他最远可以离讲台多远。

已知插排树的根节点在讲台上，有且仅有一个根节点（根节点入度为0），最远距离即所有插排的长度，小K电脑线的长度忽略不计

本题良心大样例下载地址： https://kench.co/tree.zip

输入描述:

第一行一个整数n表示有n个节点
然后n-1行，每行三个整数a,b,c，表示插排a是接在插排b上的，插排a的长度为c

输出描述:

一个整数n表示最远距离

示例1

输入

复制

输出

复制

说明

1=>3=>7=>9

备注:

对于30%的数据 n<233
对于70%的数据 n<2333

对于100%的数据 n<50000

c小于20

a,b小于等于n

PS：这个题一看就是dfs，但是不知道怎么下手。最后看了大佬的代码，才反应过来，就是相当于遍历求路径最大。

AC代码：

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
vector<pair<int,int> >mp[maxn];
int ma=0;
void dfs(int x,int sum)
{
    if(!mp[x].size())
    {
        ma=max(ma,sum);
        return ;
    }
    for(int i=0;i<mp[x].size();i++)
        dfs(mp[x][i].first,sum+mp[x][i].second);
}
int main()
{
    int n;cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&b,&a,&w);
        mp[a].push_back(make_pair(b,w));
    }
    for(int i=1;i<=n;i++)
        dfs(i,0);
    cout<<ma<<endl;
    return 0;
}

E-青蛙

链接：https://www.nowcoder.com/acm/contest/157/E
来源：牛客网

题目描述

有一只可爱的老青蛙，在路的另一端发现了一个黑的东西，想过去一探究竟。于是便开始踏上了旅途

一直这个小路上有很多的隧道，从隧道的a进入，会从b出来，但是隧道不可以反向走。

这只青蛙因为太老了，所以很懒，现在想请你帮帮慢，问他最少需要几步才可以到达对面。

将小径看作一条数轴，青蛙初始在0上，这只青蛙可以向前跳也可以向后跳，但每次只能跳一格，每跳一格记作一步，从隧道进到隧道出算做一步。

输入描述:

第一行两个数m,n；表示黑色物品在数轴m点上，数轴上总共有n个隧道
接下来n行，每行a，b两个数，表示从a进会从b出

10 <= m,n <= 233

0<a,b<=m

输出描述:

一个数ans表示最小步数

示例1

输入

复制

输出

复制

说明

0-->1-->2-->10-->9-->8-->15-->16

牛客练习赛24

PS：这是一道很明显的搜索题直接上代码。

AC代码：

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=5e3+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int a[300],m,n;
struct node
{
    int x,step;
};
void bfs()
{
    queue<node>Q;
    bool vis[300];me(vis,0);
    node now,next;
    now.x=0,now.step=0,vis[0]=1;
    Q.push(now);
    while(!Q.empty())
    {
        now=Q.front();
        Q.pop();
        if(now.x==m)
        {
            cout<<now.step<<endl;
             return ;
        }
        if(now.x+1<=m&&!vis[now.x+1])
        {
            next.step=now.step+1,next.x=now.x+1;
            vis[now.x+1]=1;
            Q.push(next);
        }
        if(now.x-1>=0&&!vis[now.x-1])
        {
            next.step=now.step+1,next.x=now.x-1;
            vis[now.x-1]=1;
            Q.push(next);
        }
        if(a[now.x]&&!vis[a[now.x]])
        {
            next.step=now.step+1,next.x=a[now.x];
            vis[a[now.x]]=1;
            Q.push(next);
        }
    }
}
int main()
{
    cin>>m>>n;
    me(a,0);
    for(int i=0;i<n;i++)
    {
        int x,y;cin>>x>>y;
        a[x]=y;
    }
    bfs();
    return 0;
}

F-三轮

链接：https://www.nowcoder.com/acm/contest/157/F
来源：牛客网

题目描述

小k有一个三轮，它最多可以装105大小的东西
小k有n种商品，他要准备出摊了

每种商品体积为vi，都有105件

输出凑成1~m的体积的总方案数

输出可能会很大，请对大质数19260817取模

输入描述:

第一行两个整数n,m，
接下来n行，每行一个数代表vi

输出描述:

一个数ans表示总方案数

示例1

输入

复制

2 8
1
3

输出

复制

说明

从1~m体积的方案数分别为：
1
1
2
2
2
3
3
3

备注:

不要忘记取模！！！
n,m,vi <= 50000

PS：好像出题方也不知道dp能过，听说他们本来想考其他知识点的。

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e6+10;
const int mod=19260817;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int dp[maxn],v[maxn];
int main()
{
    int m,n;
    while(~scanf("%d %d",&n,&m)){
        for(int i=1;i<=n;i++)
            scanf("%d",&v[i]);
        me(dp,0);dp[0]=1;
        for(int i=1;i<=n;i++)
            for(int j=v[i];j<=m;j++)
                dp[j]=(dp[j]+dp[j-v[i]])%mod;
        int ans=0;
        for(int i=1;i<=m;i++)
            ans=(ans+dp[i])%mod;
        printf("%d\n",ans);
    }
    return 0;
}

上一篇：【PAT甲级A1146】Topological Order (25分)（c++）

下一篇： 1019 数字黑洞 (20分)【java题解】

牛客练习赛24

题目描述

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

备注:

题目描述

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

备注:

题目描述

输入描述:

输出描述:

输入

输出

说明

备注:

题目描述

输入描述:

输出描述:

输入

输出

说明

题目描述

输入描述:

输出描述:

输入

输出

说明

备注:

牛客网中矩阵中的路径

牛客 数码（枚举优化+数论思维）

11.11最简单赚钱攻略，怎么做一个牛逼的新手淘宝客！

【牛客OJ】输入输出处理

牛客网 ---- 学数学

2019牛客暑期多校训练营（第二场）H Second Large Rectangle

牛客网_Go语言相关练习_判断&选择题（4）

荐 牛客网sql练习题解(43-51)

2020牛客暑期多校训练营（第四场）——Basic Gcd Problem

Java~利用二分查找完成牛客经典算法题--查找旋转数组的最小数字

牛客数码（枚举优化+数论思维）

荐牛客网sql练习题解(43-51)