美团2021校招笔试-编程题（算法编程题）

小美最近发现了一种有趣的游戏，给定一个队列q，小美会按照以下规则进行游戏：

每次从队列中取出一个数，如果这个数是当前队列中最小的值，那么小美就会丢掉这个数。否则小美就会把这个数重新加入队列。

小美会一直进行游戏直到队列变空为止，但是小美并没有多少耐心，因此她想知道她最多需要进行多少次操作才能结束游戏。

第一行一个数n表示队列中数的个数。()

第二行n个数，第i个数a_i表示队列中第i个被加进去的数的值。()

输出一个值表示小美需要操作的次数。

小团作为一名美团骑手，最喜欢的颜色就是黄和黑，因此对包含这两种颜色的事物都格外留意。

这天他发现有一棵树，树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点，在以其为根的子树中，所有与其颜色不同的节点的深度之和是多少。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。

第一行有一个数n，代表这棵树上一共有n个节点，编号为1~n。(1&ltn<=100000)

第二行有n个数，第i个数表示编号为i的节点的颜色，为0表示黄色，为1表示黑色。

第三行有n-1个数，第i个数表示编号为i+1的节点的父节点编号。

孙悟空现在正在天宫偷吃蟠桃，时间有限，王母娘娘一会儿就会回来，孙悟空要在王母娘娘回来之前尽可能多偷吃一点蟠桃。

你的任务是帮助孙悟空决定怎么吃蟠桃才能尽可能多吃。输出孙悟空最多可以吃掉的蟠桃数量。

特别说明：本题中不能直接使用排序库函数，如您使用了排序库函数，即便运行通过也会被判为0分。

第一行两个正整数N和P，N表示蟠桃的数量，P是王母娘娘还有多长时间后会回来。

接下来一行N个整数表示每个蟠桃吃掉所需的时间。

注意，掐着王母娘娘的回来的点吃完是很危险的，所以必须在王母娘娘回来前吃完，不能是回来时刚好吃完。

输出孙悟空最多能吃掉的蟠桃的数量。

小团正在装饰自己的书桌，他的书桌上从左到右有m个空位需要放上装饰物。商店中每个整数价格的装饰物恰好有一种，且每种装饰物的数量无限多。

小团去商店的时候，想到了一个购买方案，他要让右边的装饰物价格是左边的倍数。用数学语言来说，假设小团的m个装饰物价格为，那么对于任意的1≤i≤j≤m，是的倍数。

小团是一个节约的人，他希望最贵的装饰物不超过n元。现在，请你计算小团有多少种购买的方案？

输入包含两个数，n和m

输出一个数，结果对998244353取模，表示购买的方案数。

小团要组织一只队伍参加MT杯竞赛，某媒体赛前要对各参赛队伍实力进行评估，已知这个比赛要求每一个参赛方组织一支由x个人组成的A队，和y个人组成的B队，这个媒体在评估时会把A队的人员的平均实力值和B队人员的平均实力值相加，从而得到一个参赛方的综合实力评估。

       小团可选的人手有限，只有x+y个人可以供他选择，但是显然不同的人员安排会有不同的综合实力评估，他希望他的综合实力评估尽可能高，请你帮助他完成分队。

输入第一行包含两个正整数x，y，分别表示AB队的人数。(1<=x,y<=20000)

输入第二行包含x+y个正整数，中间用空格隔开，第i个数字表示第i个人的实力值，每个人的实力值不会超过20000，保证任意两个人都不会有相同的实力值。   

输出包含一个长度为x+y的字符串，每个字符是’A’或’B’，表示某人应该被分在A或B队。如果存在多种答案，则输出字典序最小的字符串。

小美要将N名员工分成若干组，且每组至少要有一名员工。每个组都会产生一个单位的收益，且对于第i名员工，如果其所在的组包含至少A[i]名员工（包括第i名员工自身），则该员工会额外贡献一个单位的收益。现在，小美请小团将N名员工分组，使得总收益最大。

第一行输入一个整数T（1<=T<=10），表示数据组数。

每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；

第二行输入N个由空格隔开的整数，表示A[1]到A[N]（1<=A[i]<=N）。

每组数据输出占一行，输出一个整数，表示总收益的最大值。

高一年级(1)班的小美老师需要对学生的考试成绩进行处理。单科考试的卷面总分为150分，考生得分一定为整数。

首先按照总分由大到小排序，如果总分相等则按照语文成绩由大到小排序。（输入保证没有两名学生的成绩完全相等）。

输入n个学生的学号和成绩（n<=1000），请输出按要求排序后所有学生的学号。

单组输入，第1行为n。

接下来n行每一行包含三个整数，分别为学号（>=1的任意正整数，同一组输入保证学号不重复）、语文成绩和数学成绩。

输出按要求排序后所有学生的学号，两个学号之间用空格隔开。

小团是一个莫得感情的CtrlCV大师，他有一个下标从1开始的序列A和一个初始全部为-1序列B，两个序列的长度都是n。他会进行若干次操作，每一次操作，他都会选择A序列中一段连续区间，将其粘贴到B序列中的某一个连续的位置，在这个过程中他也会查询B序列中某一个位置上的值。

我们用如下的方式表示他的粘贴操作和查询操作：

粘贴操作：1  k x y，表示把A序列中从下标x位置开始的连续k个元素粘贴到B序列中从下标y开始的连续k个位置上。原始序列中的元素被覆盖。（数据保证不会出现粘贴后k个元素超出B序列原有长度的情况）

查询操作：2 x，表示询问B序列下标x处的值是多少。

输入第一行包含一个正整数n，表示序列A和序列B的长度。(1<=n<=2000)

输入第二行包含n个正整数，表示序列A中的n个元素，第i个数字表示下标为i的位置上的元素，每一个元素保证在10^9以内。

输入第三行是一个操作数m，表示进行的操作数量。(1<=m<=2000)

接下来m行，每行第一个数字为1或2，具体操作细节详见题面。

小美有一个由N个点组成的二叉树，每个点有一个权值。定义二叉树每个点的开销为其权值与深度的乘积（每个点的深度为其到根节点的距离，即其到根节点的路径上的边数），二叉树的总开销即每个点的开销之和。小美按照二叉树的中序遍历依次记录下每个点的权值，即她记录下了N个数，第i个数表示位于中序遍历第i个位置的点的权值。之后由于某种原因，小美遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小美请小团求出最优二叉树的总开销。

第一行输入一个整数N（1<=N<=300），表示二叉树的点数。

第二行输入N个由空格隔开的整数，表示按中序遍历记录下的各个点的权值，所有权值均为不超过10^4的正整数。

输出一个整数，表示最优二叉树的总开销。

小团所在的班级今天去郊游了。小团的班级有个人，每个人有一个独一无二的正整数学号。因为小团的班级很大（n可能达到这么大！），点名成为了一个重大的问题。

小团作为班长，他想让同学们站成一列，他点名的方式如下：

1.如果当前点到的同学不在队列中，则加入队列中的第一个

2.如果当前点到的同学在队列中，则该同学出队，站到队列中第一个，并且不保留他之前的空位。

现在，给出小团的点名顺序，请你算出队列中同学是怎么排的。注意，点名可能存在重复，也可能只点名一部分同学。

输入第一行包含一个整数m，表示小团点名了多少次。注意，n不会在输入中给出。

接下来m行，每行一个整数，代表小团每次点名的学号。

输出包含若干个整数，每个整数一行，第i行代表最后站在队列第i位同学的学号。

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

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

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

单组输入。

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

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

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

小团有一棵树，这棵树有n个节点，编号为1-n。每个节点上有一个值。1号节点为整棵树的根。

现在，小团给小美一个难题：小美每次可以操作一个节点x，将变为，保持x所有的儿子不变，将x所有儿子的儿子变为，保持所有的儿子的儿子的儿子不变，以此类推。

代表位运算异或。

小团希望小美用尽可能少的次数，将所有的变为，请帮助小美计算这个最少的次数。

数据保证在有限步数内，能够将所有的变为

输入第一行包含一个整数n，代表节点数。

接下来n-1行，每行两个整数，代表树上的一条边

接下来一行，一共n个数，第i个数代表。

接下来一行，一共n个数，第i个数代表。

输出包含一行一个数，即小美的最少操作次数。

小美有一个2×2的矩阵，矩阵左上角、右上角、左下角、右下角的数字分别为0、A、B、C。

小美觉得该矩阵不够大，她按如下方法扩展该矩阵：

将2×2的矩阵扩展为4×4的矩阵，4×4的矩阵被分为左上角、右上角、左下角、右下角这4个2×2的矩阵，其中左上角为原2×2的矩阵，右上角为原2×2的矩阵每个位置上的数加上A，左下角为原2×2的矩阵每个位置上的数加上B，右下角为原2×2的矩阵每个位置上的数加上C；

将4×4的矩阵扩展为8×8的矩阵，8×8的矩阵被分为左上角、右上角、左下角、右下角这4个4×4的矩阵，其中左上角为原4×4的矩阵，右上角为原4×4的矩阵每个位置上的数加上A，左下角为原4×4的矩阵每个位置上的数加上B，右下角为原4×4的矩阵每个位置上的数加上C；

……

经过不断扩展，小美可以得到一个无穷大的矩阵。小美打算用该矩阵和小团玩游戏，即对小团进行N次提问，每次给出正整数X、Y，并问小团矩阵上第X行第Y列上的数是多少，由于该数可能很大，只要求小团回答该数除以10^9后的余数。

第一行输入四个由空格隔开的整数A、B、C和N（0<=A,B,C<10^9、1<=N<=10^5）。

接下来N行，每行输入两个由空格隔开的整数X和Y（1<=X,Y<=10^9）。

输出N行，每行输出一个整数，第i行输出第i次提问的答案，即矩阵对应位置上的数除以10^9后的余数。

小美有N张牌，牌上分别写有数字1到N，她打算用这些牌和小团玩洗牌游戏。小美将牌叠成一堆放在桌上，每次可以从桌上的牌堆的顶部取走一张牌，叠放在自己手上，或者将自己手上的牌堆的顶部或底部的一张牌交给小团，直到N张牌都交给小团。通俗地说，一开始桌上的牌堆有N张牌，小美手上的牌堆有0张牌，她每次可以将桌上牌堆顶的一张牌放到自己手上的牌堆顶，或者将手上牌堆顶或牌堆底的一张牌交给小团。小团收到的牌上面的数字（按收到的顺序）依次为A[1]到A[N]。现在，小美问小团是否有可能，初始时桌上的牌堆从顶部到底部，牌上所写的数字依次为1到N。

第一行输入一个整数T（1<=T<=10），表示数据组数。

每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；

第二行输入N个由空格隔开的整数，表示A[1]到A[N]（保证是1到N的一个排列）。

每组数据输出占一行，如果初始时桌上的牌堆从顶部到底部，牌上所写的数字依次为1到N是有可能的，则输出“Yes”，否则输出“No”（均不包括引号）。

小美和小团计划去邻国旅行。邻国有N座城市，城市间由N-1条双向道路连通，且保证从任意城市出发，沿着这些道路可以到达其它任意城市。小美和小团可以从任意城市出发，沿着城市间的道路，以任意顺序游览每座城市，并且可以在任意城市结束旅行。那么，小美和小团想知道，他们至少要在道路上行驶多少距离，才能保证游历每座城市。

第一行输入一个整数T（1<=T<=10），表示数据组数。

对于每组数据，第一行输入一个整数N（1<=N<=10^5）；

接下来N-1行，每行输入三个由空格隔开的整数X、Y和L（1<=X,Y<=N、1<=L<=10^4），表示第X座城市和第Y座城市间有一条长为L的双向道路。

小团是旅店老板，现在有连续的N个房间（从左到右分别编号从1到N），每个房间可以住一个旅客。

有P个游客通过美团酒店业务来到小团的旅店住宿，小团的任务是想办法给他们分配房间，要求相邻的两个房间不可以同时住上旅客。（比如3号房间和4号房间相邻，你可以两个房间都不住人，也可以3号房间住一个人4号不住，也可以3号不住4号房间住一个人，但不可以3号和4号都住人）

对于无法找到合法的方案进行分配的情况，输出0即可。

方案数不对具体的游客进行区分。例如1号房间住旅客A，3号房间住旅客B，和1号房间住旅客B，3号房间住旅客A视为同一种方案，即分配了1号和3号房间。

你的任务是给出有多少种分配的方案，方案数对10000取模即可。

保证 0 < P < N

一行两个以空格分开的自然数N和P。

对于40%的数据有2 <= N <= 10

对于60%的数据有2 <= N <= 100

对于100%的数据有2 <= N <= 1000

小团最近喜欢上了一种非常简单的扑克牌接龙游戏。

游戏的玩法是这样的：

将扑克牌洗牌后平均分为两堆，每人轮流出一张牌进行接龙。如果某个人出的牌的大小和接龙牌堆中一张已有牌的大小相同（不考虑花色），那么他可以将这两张牌以及中间所有的牌全部收走并据为己有。例如：如果在接龙的牌堆中有一个3，你再出一个3，那么这两个3以及它们中间的牌都归你所有。

两个人依次出牌，最后比谁收到的牌最多即可获胜。

我们把这个问题稍作简化，如果是一个人在玩这个游戏。现在给你一串数字和字母表示扑克牌的次序，请问最多的一次可以收走多少张牌。

单组输入，输入占两行。

第1行是牌的总数n。(n<=1e5)

第2行输入n个数字或者字符（对应2、3、4、5、6、7、8、9、10和A、J、Q、K），两两之间用空格隔开。

小美和小团所在的城市包含N个乡镇，乡镇被编号为1到N并按中心化管理，N个乡镇按层级构成树型关系：即以1号乡镇为中心(根)，对于2号到N号乡镇，i号乡镇的上级乡镇为A[i]号乡镇（1<=A[i]<i），或者说i号乡镇是A[i]号乡镇的一个下属乡镇。每个乡镇只有一个上级乡镇（除了1号乡镇没有上级乡镇）和若干个下属乡镇。

该城市由2(N-1)条单向道路连接各乡镇。除了1号乡镇，每个乡镇都有一条长为1的高速公路通向其上级乡镇，而其上级乡镇则有一条长为2的普通公路通向该乡镇。

现在，小美和小团打算在该城市开展外卖业务。若他们在某个乡镇设立站点，则从该乡镇出发距离不超过2的乡镇都可以享受到他们的外卖服务。那么，他们想知道至少要在多少个乡镇设立站点，才能使所有乡镇都享受到外卖服务。

第一行输入一个整数T（1<=T<=10），表示数据组数。

每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；

第二行输入N-1个由空格隔开的整数，表示A[2]到A[N]（1<=A[i]<i）。

每组数据输出占一行，输出一个整数，表示所需设立的站点数目的最小值。