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

时间限制&＃xff1a;C/C&＃43;&＃43; 1秒&＃xff0c;其他语言2秒

空间限制&＃xff1a;C/C&＃43;&＃43; 262144K&＃xff0c;其他语言524288K
64bit IO Format: %lld

题目描述

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

输入描述:

第一行有两个正整数n&＃xff0c;m。

输出描述:

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

示例1

输入

复制

1 1

输出

复制

1

示例2

输入

复制

2 3

输出

复制

6

示例3

输入

复制

3 3

输出

复制

12

备注:

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

  公式 ans&＃61;m*(m-1)^(n-1)

  需要用快速幂

  AC:

#include
#include
#include
#define LL long long
using namespace std;LL quick1(long long a,long long b,long long mod)
{LL res&＃61;1;while(b){if(b&1) res&＃61;(res*a)%mod;b>>&＃61;1;a&＃61;(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;
}


时间限制&＃xff1a;C/C&＃43;&＃43; 2秒&＃xff0c;其他语言4秒
空间限制&＃xff1a;C/C&＃43;&＃43; 32768K&＃xff0c;其他语言65536K
64bit IO Format: %lld

题目描述

    PH试纸&＃xff0c;是一种检测酸碱度的试纸&＃xff0c;试纸红色为酸性&＃xff0c;蓝色为碱性。

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

输入描述:

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

输出描述:

共m行&＃xff0c;第i行一个整数&＃xff0c;表示查询结果&＃xff0c;若颜色ci出现次数少于qi次&＃xff0c;则输出-1&＃xff0c;否则输出颜色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%的测试数据&＃xff1a;
1 ≤ n, m ≤ 1000000
所有输入数据不超过1000000。
数据量较大&＃xff0c;注意使用更快的输入输出方式。

直接用数组记录,很简单

ac:

#include
#include
#include
using namespace std;
char str[1000001],ctr;
int r[1000001]&＃61;{0},b[1000001]&＃61;{0};int main()
{int n,m,x,y,z;scanf("%d%d",&n,&m);scanf("%s",&str);x&＃61;y&＃61;0;for(int i&＃61;0;i}

时间限制&＃xff1a;C/C&＃43;&＃43; 1秒&＃xff0c;其他语言2秒
空间限制&＃xff1a;C/C&＃43;&＃43; 32768K&＃xff0c;其他语言65536K
64bit IO Format: %lld

题目描述

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

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

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

本题良心大样例下载地址&＃xff1a; https://kench.co/tree.zip

输入描述:

第一行一个整数n表示有n个节点
然后n-1行&＃xff0c;每行三个整数a,b,c&＃xff0c;表示插排a是接在插排b上的&＃xff0c;插排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&＃61;>3&＃61;>7&＃61;>9

备注:

对于30%的数据 n<233
对于70%的数据 n<2333对于100%的数据 n<50000c小于20a,b小于等于n

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

  ac:

#include
#include
#include
#include
using namespace std;int main()
{int n,x,y,z,a[50001]&＃61;{0},d[50001]&＃61;{0},c[50001]&＃61;{0},maxs&＃61;0;scanf("%d",&n);for(int i&＃61;1;imaxs)maxs&＃61;c[i];}printf("%d\n",maxs);return 0;
}


时间限制&＃xff1a;C/C&＃43;&＃43; 1秒&＃xff0c;其他语言2秒
空间限制&＃xff1a;C/C&＃43;&＃43; 32768K&＃xff0c;其他语言65536K
64bit IO Format: %lld

题目描述

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

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

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

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

输入描述:

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


输出描述: