偷偷拿出一点美团官方真题【技术类 第二期】

声明：

1. 总共9期，慢慢发，是去年秋招的，之后春招有新的了，我再弄过来。也可以私聊我，直接看全部的word文档
2. 资料来源于美团的 廖YQ （人名）
3. 有问题可以问，每天看到了就会回复（但是牛客不是时刻登录的，请见谅）
4. 如果对你有帮助，可以点赞收藏，我也想成为 <红名大佬>
5. 电脑端应该好看一点

【技术类 第二期】

小美的健身操

时间限制: 2000/1000 MS (Java/Others)

内存限制: 524288/524288 K (Java/Others)

问题描述

​ 小美开始学习健身操。我们可以将一套健身操简化为两个动作（记为动作0，动作1）和中途休息（即不做任何动作）的组合。

​ 如果小美在健身操要求做某个动作时做出错误的动作，或者说在应该中途休息是做了某个动作，则被称为“错误操作”（应该做某个动作而没有做某个动作不算“错误操作”）。如果一段连续的错误操作的持续时间小于阈值k，则被称为“小错误”。

​ 例如，要求的动作为：1~3时刻动作0，小美的实际动作为：0~4时刻动作0，阈值为2，则小美有两次“小错误”，分别在0~1时刻和3~4时刻。

​ 再例如，要求的动作为：1~3时刻动作0，小美的实际动作为：2~4时刻动作1，阈值为2。虽然2~3和3~4都是“错误操作”，但是它们是连续的，所以只算一段错误操作，时间等于2，达到阈值，因此小美没有“小错误”。

给出健身操要求的动作以及小美的实际动作，求小美有多少次“小错误”。

输入描述

​ 第一行三个正整数n,m,k(1≤n,m≤200,1≤k≤10^6 )，分别表示健身操的动作数量，小美的实际动作数量，阈值。

​ 接下来n行，每行三个正整数l,r,v，表示健身操的动作为，l~r时刻，动作v。保证按时间升序给出指令，各个动作的时间段没有重叠的部分。

​ 接下来m行，每行三个正整数l,r,v，表示小美的实际动作为，l~r时刻，动作v。保证按时间升序给出指令，各个动作的时间段没有重叠的部分。

​ 0≤l≤r≤10^6

输出描述

​ 仅一行，一个整数，小美的“小错误”的次数。

输入样例

​ 3 3 2

​ 1 2 0

​ 5 6 1

​ 8 10 1

​ 0 3 0

​ 5 6 0

​ 7 9 1

输出样例

​ 4

样例解释

​ 分别在0~1,2~3,5~6,7~8

坐公交

时间限制: 2000/1000 MS (Java/Others)

内存限制: 65536/65536 K (Java/Others)

问题描述

小美想坐公交去找小团玩。美团市中共有n个公交站，编号为1到n。同时也有m条公交线路，编号为1到m。小美想知道对于每一对公交站(i,j)从编号为i的站坐公交到编号为j的站至少需要乘坐几条不同的公交线路。

输入描述

第一行有两个整数n,m(1<=n<=500,1<=m<=500,1<=n+m<=500)，代表公交站的个数和公交线路的条数。

接下来n行，每一行开头有一个整数k(1<=k<=m)，代表从这个站可以乘坐k条不同的公交线路。接下来有k个整数，代表这k条公交线路的编号。

输出描述

输出一个n×n的矩阵，矩阵中第i行第j列的数代表从编号为i的站做到编号为j的站至少需要乘坐多少条不同的公交线路。矩阵中每行中的元素由单个空格隔开，且行末不能有空格。

输入样例1

3 2

1 1

2 1 2

1 2

输出样例1

0 1 2

1 0 1

2 1 0