欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客练习赛24

程序员文章站 2022-06-07 13:06:23
...
A 石子阵列

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

题目描述

xb有m种石子,每种无限个,Ta想从这些石子中取出n个,并按顺序排列起来,为了好看,相邻的石子不能相同。xb想知道有多少种排列的方法。

输入描述:

第一行有两个正整数n,m。

输出描述:

第一行一个整数,表示在m种石子中取出n个的排列方案数模1000000007后的值

示例1

输入

复制

1 1

输出

复制

1

示例2

输入

复制

2 3

输出

复制

6

示例3

输入

复制

3 3

输出

复制

12

备注:

对于100%的测试数据:
1 ≤ n, m ≤ 1000
数据量较大,注意使用更快的输入输出方式。

题解:规律题

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<bitset>
using namespace std;
typedef long long ll;
ll mod=1000000007;
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    ll ans=m;
    n--;
    for(int i=1;i<=n;i++){
        ans*=1ll*(m-1);
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}
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

示例2

输入

复制

3
1 2
1 3

输出

复制

1

示例3

输入

复制

4
1 2
2 3
2 4

输出

复制

3

备注:

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

题解:刚开始的时候想的是用 dfs 求最大子树,后来爆了,用并查集过的。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
int per[1000005];
set<int>ss;
map<int,int>mapp;
int find(int x){
    if(per[x]==x)
        return x;
    else
        return per[x]=find(per[x]);
}

void U(int x,int y){
    int xx=find(x);
    int yy=find(y);
    if(xx!=yy)
        per[xx]=yy;
}

int main(){
    int n,a,b;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        per[i]=i;
    int m=n-1;
    for(int i=0;i<m;i++){
        scanf("%d %d",&a,&b);
        if(a==1||b==1)
            continue;
        U(a,b);
     /*   if(a[i]==1){
            if(!ss.count(b[i]))
                ss.insert(b[i]);
        }
        if(b[i]==1){
            if(!ss.count(a[i]))
                ss.insert(a[i]);
        }*/
    }
    for(int i=2;i<=n;i++){
        int xx=find(i);
        mapp[xx]++;
    }
    map<int,int>::iterator it;
    int ans=0;
    for(it=mapp.begin();it!=mapp.end();it++){
        ans=max(ans,it->second);
    }
    printf("%d\n",ans);
    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。
数据量较大,注意使用更快的输入输出方式。

题解:水题

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
vector<int>v[3];
char s[1000005];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    scanf(" %s",s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='B'){
            v[0].push_back(i);
        }
        else
            v[1].push_back(i);
    }
    while(m--){
        char c;
        int d;
        scanf(" %c %d",&c,&d);
        if(c=='B'){
            if(d>v[0].size())
                printf("-1\n");
            else
                printf("%d\n",v[0][d-1]);
        }
        else{
           if(d>v[1].size())
                printf("-1\n");
            else
                printf("%d\n",v[1][d-1]);
        }
    }
    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

输入

复制

9
2 1 2
3 1 2
4 1 1
5 2 3
6 2 1
7 3 1
8 3 4
9 7 5

输出

复制

8

说明

1=>3=>7=>9

备注:

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

对于100%的数据 n<50000

c小于20

a,b小于等于n

题解:刚开始想用 dfs,后来发现 子结点的值==根结点值+边上的权值,找最值就好了

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
int a,b,c;
map<int,int>mapp;
int main(){
    int n;
    scanf("%d",&n);
    int m=n-1;
    while(m--){
        scanf("%d %d %d",&a,&b,&c);
        mapp[a]=mapp[b]+c;
    }
    int ans=0;
    map<int,int>::iterator it;
    for(it=mapp.begin();it!=mapp.end();it++){
        ans=max(ans,it->second);
    }
    printf("%d\n",ans);
    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

输入

复制

16 4
2 10
8 15
12 5
13 6

输出

复制

7

说明

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

牛客练习赛24

题解:水题,直接 bfs

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
map<int,int>mapp;
int v[500]={0};
int n,m;
struct fun{
    int x;
    int ss;
};

int bfs(int x){
    v[x]=1;
    fun t;
    t.x=x;
    t.ss=0;
    queue<fun>qq;
    qq.push(t);
    while(!qq.empty()){
        fun g=qq.front();
        if(g.x==n){
            return g.ss;
        }
        qq.pop();
        int xx;
        for(int i=0;i<3;i++){
            if(i==0){
                xx=g.x+1;
            }
            else if(i==1){
                xx=g.x-1;
            }
            else if(i==2){
                if(mapp.count(g.x)){
                    xx=mapp[g.x];
                }
                else
                    continue;
            }
            if(xx<0||xx>n||v[xx])
                continue;
            v[xx]=1;
            t.x=xx;
            t.ss=g.ss+1;
            qq.push(t);
        }
    }
    return -1;
}
int main(){
    int a,b;
    scanf("%d %d",&n,&m);
    while(m--){
        scanf("%d %d",&a,&b);
        mapp[a]=b;
    }
    printf("%d\n",bfs(0));
    return 0;
}
F 三轮

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

题目描述

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

每种商品体积为vi,都有1e5件

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

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

输入描述:

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

输出描述:

一个数ans表示总方案数

示例1

输入

复制

2 8
1
3

输出

复制

17

说明

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

备注:

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

题解:动态规划 dp[j]=dp[j]+dp[j-a[i]];   %操作 比 —操作慢多了

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
ll a[50005],dp[50005]={0};
ll mod=19260817;

int read(){
    int x=0,f=1; char ch;
    while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1;
    while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9');
    return x*f;
}
int main(){
    int n,m;
    n=read();
    m=read();
    for(int i=0;i<n;i++)
        a[i]=read();
    dp[0]=1;
    for(int i=0;i<n;i++){
        for(int j=a[i];j<=m;j++){
            dp[j]=dp[j]+dp[j-a[i]];
            if(dp[j]>mod)
                dp[j]-=mod;
        }
    }
    ll ans=0;
    for(int i=1;i<=m;i++){
        ans+=dp[i];
        if(ans>mod)
            ans-=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

 

相关标签: 牛客