2020美团点评笔试题目( 技术综合-后台方向)

1、照镜子

时间限制: 3000MS
内存限制: 589824KB

题目描述:

小团有一个n×m的矩阵A, 他知道这是小美用一种特殊的方法生成的,具体规则如下:

小美首先写下一个n×m的矩阵,然后小美每一次将这个矩阵上下翻转后接到原矩阵的下方。小美重复这个过程若干次(甚至可能是0次,也就是没有进行过这一操作),然后将操作后的矩阵交给小团。

小团想知道,小美一开始写下的矩阵是什么。因为小美可能有多种一开始的矩阵,小团想得到最小的矩阵(这里的最小指矩阵即n×m的面积最小)。

输入描述

输入包含两个整数n,m,表示小团矩阵的大小。
接下来n行,每行m个正整数,第 i 行第 j 列表示矩阵第 i 行第 j 列的数。
1≤n≤100000,1≤m≤5,矩阵内的数小于等于10

输出描述

输出包含一个矩阵,一共n’行m列,表示小美一开始最小的矩阵。

样例输入

8 3
1 0 1
0 1 0
0 1 0
1 0 1
1 0 1
0 1 0
0 1 0
1 0 1

样例输出

1 0 1
0 1 0

提示

样例解释
小美一开始的矩阵可能有以下3种:

1

1 0 1
0 1 0

2

1 0 1
0 1 0
0 1 0
1 0 1

3

1 0 1
0 1 0
0 1 0
1 0 1
1 0 1
0 1 0
0 1 0
1 0 1

其中最小的矩阵为第一种。

2、小团的装饰物

时间限制: 3000MS
内存限制: 589824KB

题目描述:

小团需要购买m样装饰物。商店出售n种装饰物,按照从小到大的顺序从左到右摆了一排。对于每一个装饰物,小团都给予了一个美丽值ai。

小团希望购买的装饰物有着相似的大小,所以他要求购买的装饰物在商店中摆放的位置是连续的一段。

小团还认为,一个装饰物的美丽值不能低于k,否则会不好看。

现在,请你计算小团有多少种不同的购买方案。

输入描述

输入第一行包含三个数n,m,k

接下来一行n个整数ai ( 1≤ i ≤n ),空格隔开,表示商店从左到右摆放的每个装饰物的美丽值。

n , m≤100000

1≤ai ,k≤10^9

输出描述

输出一个数,表示小团购买的方案数。

样例输入

8 2 5
5 5 5 4 5 5 5 5

样例输出

5

提示

有[1,2][2,3][5,6][6,7][7,8] 共5段

3、填数游戏

时间限制: 3000MS
内存限制: 589824KB

题目描述:

小团和小美正在玩一个填数游戏,这个游戏是给一个等式,其中有一些数被挖掉了,你需要向其中填数字,使得等式成立。

比如 ___+12=34,那么横线填的一定是22

现在,这个游戏到了最后一关,这一关的等式很奇特:__+ __+ _+…+ __=n

这里可以填任意多个正整数(甚至可能是1个),只要这些数的和等于n即可。

但是,有一个额外的限制,填入的所有数必须小于等于k,大于等于1,填入的数的最大值必须大于等于d。

请你计算,有多少个不同的等式满足这些限制。由于答案可能很大,请将答案mod(998244353)后输出。

输入描述

输入包含三个数n,k,d(1≤d≤k≤n≤1000)

输出描述

输出包含一行,即方案数。

样例输入

5 3 2

样例输出

12

提示

样例解释
2+3=5
3+2=5
1+1+3=5
1+3+1=5
3+1+1=5
1+2+2=5
2+1+2=5
2+2+1=5
1+1+1+2=5
1+1+2+1=5
1+2+1+1=5
2+1+1+1=5
共12种填法

4、密室闯关

时间限制: 3000MS
内存限制: 655360KB

题目描述:

小团和小美正在密室中解密。他们现在来到了一个新的关卡面前。这一关是一个配合关卡,有n个巨大的齿轮摆成一排,每个齿轮上有两个按钮和按顺时针排成一环的26个大写字母。在齿轮的最上面有一个孔,透过孔可以看到齿轮上方的字母。

小团每次只能按下某个齿轮 r 的一个按钮。当按下按钮后,小美可以开始逆时针旋转齿轮r。如果小团按下的是该齿轮的第一个按钮,r会和r-1咬合,小美就可以逆时针旋转r一格,并且齿轮r-1会顺时针旋转一格。顺时针旋转一格会使得齿轮最上方的字母变为上一个字母,即Z变为X,B变为A。逆时针旋转一格会使得齿轮最上方的字母变为下一个字母。同理,如果小团按下的是第二个按钮,r会和r+1咬合,小美就可以逆时针旋转r一次,并且齿轮r+1会顺时针旋转一次。

小团和小美可以做这个操作若干次(也可以一次也不做),每次小团松开一个按钮后,两个咬合的齿轮会回归原位。这个齿轮组的某个状态所组成的字符串将会是通关密码。

但是请注意,每个齿轮的字母A和字母Z之间有一个凸起,这意味着任何一个齿轮都不能旋转一格从A到Z,也不能旋转一格从Z到A。同时请注意,第一个齿轮没有第一个按钮,最后一个齿轮没有第二个按钮。

现在,小团想计算出可以变化出多少种齿轮的组合,他会依据这个数字来计算是否可以暴力计算出密码。请你帮助他。

例如输入:

2

BB

3

ABA

包含了两组样例

对于样例1,有以下三种最终可能的组合:AC,BB,CA

对于样例2,有以下三种最终可能的组合:BAA,ABA,AAB

对于样例2,一开始的状态如图第一行所示,其中,红色箭头指向的是透过小孔看得见的字母。

小团选择第1个齿轮的第2个按钮按下,小美旋转后,会变为图第二行的状态

小团选择第3个齿轮的第1个按钮按下,小美旋转后,会变为图第三行的状态

输入描述

输入包含多组数据。对于每组数据,将会输入两行。

第一行会输入一个数n,代表齿轮的个数。

接下来一行n个大写字母,代表每个齿轮最开始能看见的字母。

n≤100,数据不会超过1000组。

输出描述

对于每组数据,输出一行一个数字,代表密码可能的组合数,对998244353取模。

样例输入

2
BB
3
ABA

样例输出

3
3

5、有规划的小团

时间限制: 3000MS
内存限制: 589824KB

题目描述:

小团是一个做事很有规划的人。他列了在暑假期间要做的很多事情,对于每一件事情他都标注了优先级和必要程度,其中优先级从1到9,必要程度从1到5(数值越大,对应的优先级或者必要程度越高)。他希望对这些事情进行排序,排序规则如下:

必要程度大的事情排在前面;如果两件事情的必要程度一样则优先级大的排在前面;如果必要程度和优先级都一样则保持初始顺序不变。

因为事情实在是太多了,所以小团需要你的帮助。你能否编写一段代码来告诉小团这些事情的顺序呢?

输入描述

单组输入。

第1行输入一个正整数n表示有n件需要完成的事情,这n件事情的初始编号分别为1、2、3、…、n。(n<=10000)

接下来n行,每行包含两个正整数a和b分别表示某一件事情的优先级和必要程度,两个数字之间用空格隔开。

输出描述

输出按照要求排序后所有事情的初始编号,两个编号之间用空格隔开。

样例输入

2
9 3
1 4

样例输出

2 1

你可能感兴趣的