牛客练习赛24
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专用数据结构——插排树(如图)
小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
题解:水题,直接 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;
}