牛客练习赛24-(石子阵列,PH试纸,插排树,青蛙)

石子阵列

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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
数据量较大，注意使用更快的输入输出方式。

  公式 ans=m*(m-1)^(n-1)

  需要用快速幂

  AC:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;LL quick1(long long a,long long b,long long mod)
{LL res=1;while(b){if(b&1) res=(res*a)%mod;b>>=1;a=(a*a)%mod;}return res;
}int main()
{int n,m;scanf("%d%d",&n,&m);printf("%lld\n",m*quick1(m-1,n-1,1000000007)%1000000007);return 0;
}

C

PH试纸

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

    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。
数据量较大，注意使用更快的输入输出方式。

直接用数组记录,很简单

ac:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[1000001],ctr;
int r[1000001]={0},b[1000001]={0};int main()
{int n,m,x,y,z;scanf("%d%d",&n,&m);scanf("%s",&str);x=y=0;for(int i=0;i<n;i++){if(str[i]=='R')r[++x]=i+1;else b[++y]=i+1;}for(int i=0;i<m;i++){scanf(" %c%d",&ctr,&z);if(ctr=='R'){if(x<z)printf("-1\n");else printf("%d\n",r[z]);}else{if(y<z)printf("-1\n");else printf("%d\n",b[z]);}}return 0;
}

D

插排树

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

一年一度的山东省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<50000c小于20a,b小于等于n

因为线板是唯一的,所以可以直接记录前驱,和线板长度,然后依次计算

  ac:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;int main()
{int n,x,y,z,a[50001]={0},d[50001]={0},c[50001]={0},maxs=0;scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d%d",&y,&x,&z);a[y]=x;d[y]=z;}for(int i=1;i<=n;i++){c[i]=c[a[i]]+d[i];if(c[i]>maxs)maxs=c[i];}printf("%d\n",maxs);return 0;
}

E

青蛙

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

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

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

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

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

输入描述:

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

输出描述:

一个数ans表示最小步数

 

示例1

输入

复制

16 4
2 10
8 15
12 5
13 6

输出

复制

7

说明

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

直接用广搜

ac:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f
using namespace std;
int vis[1024],mp[255][255],st,ed,n,m;struct node
{int x,step;
};void bfs()
{st=0;ed=m;queue<node> que;node q,p;p.x=0,p.step=0;que.push(p);vis[0]=1;while(!que.empty()){p=que.front();que.pop();if(p.x==ed){printf("%d\n",p.step);break;}q=p;q.x=p.x+1;q.step=p.step+1;if(!vis[q.x]&&q.x>=0&&q.x<=ed){vis[q.x]=1;que.push(q);}q.x=p.x-1;q.step=p.step+1;if(!vis[q.x]&&q.x>=0&&q.x<=ed){vis[q.x]=1;que.push(q);}for(int i=0;i<=ed;i++){if(mp[p.x][i]!=inf&&!vis[i]){q.x=i;q.step=p.step+1;vis[q.x]=1;que.push(q);}}}
}int main()
{int a,b;scanf("%d%d",&m,&n);memset(vis,0,sizeof(vis));for(int i=0;i<=m;i++)for(int j=0;j<=m;j++)mp[i][j]=inf;for(int i=0;i<n;i++){scanf("%d%d",&a,&b);mp[a][b]=1;}bfs();return 0;
}