如果对你有帮助，请点赞收藏，助我早日成为红名大佬

过几天更新美团面经，需要的同学可以关注

*【技术类 七】*

最大子段和

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

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

问题描述

最大子段和是一个经典问题，即对于一个数组找出其和最大的子数组。

现在允许你在求解该问题之前翻转这个数组的连续一段（如翻转{1,2,3,4,5,6}的第三个到第五个元素组成的子数组得到的是{1,2,5,4,3,6}），则翻转后该数组的最大子段和最大能达到多少？

输入描述

第一行有一个正整数n(1<=n<=100000)，代表数组长度。

第二行有n个整数(-1000<=ai<=1000)，代表给出数组。

输出描述

输出一个整数，代表若允许你翻转一个子数组 ，则翻转后所得数组的最大子段和最大能到多少。

如样例中可以翻转[2,3]这个子数组得到{-1,-5,3,2,-1,3}，此时最大子段和为3+2-1+3=7。

也可以翻转[3,6]这个子数组得到{-1,3,3,-1,2,-5}，此时最大子段和为3+3-1+2=7。

若翻转[1,3]这个子数组得到{-5,3,-1,2,-1,3}，则最大子段和为3-1+2-1+3=6。

输入样例1

6

-1 3 -5 2 -1 3

-------------------------------

小团的括号序列

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

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

问题描述

定义括号序列为仅由左圆括号”(”和右圆括号”)”组成的字符串。

一个括号序列是合法的当且仅当其是空串，或可以写成(A)，或可以写成AB，其中A和B是合法括号序列。例如A=()是合法的，则()()=AA与(())=(A)均是合法的。

现在小团有一个长度为n的括号序列，他希望你删除其中的连续一段使得剩下的两端拼接起来是一个尽可能长的合法括号序列。

输入描述

第一行有一个整数n(1<=n<=100000)，代表括号序列的长度。

第二行有一个长度为n的括号序列，且开头为左圆括号，结尾为右圆括号。

输出描述

输出一个整数，代表删掉中间某一段后剩下来的合法括号序列的长度的最大值。

如样例中，删除第二个或第四个左圆括号，剩下的括号序列()(())或(()())均合法，且长度为6。

输入样例1

7

(()(())

输出样例1

6

----------------------------------------

*【技术类 六】*

旅行

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

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

问题描述

​ 小团去旅行了，一路上它记录下来沿途经过的城市。中途有几个城市记录错误了，她凭借记忆恢复了之前的旅行记录，现在小团想请你帮她看看恢复出来的旅行记录是否是可行的记录

你有一份这个地区的地图，这个地方一共有n个城市，有m条不同的道路，每条道路直接连接这n个城市中的两个，使得这两个城市可以双向直达。一个旅行记录是可行的，当且仅当记录中的相邻两个城市均可以直达，即，存在一条连接这两个城市的道路。

输入描述

​ 第一行一个整数T，表示接下来有T组数据

​ 每组数据第一行第一个数n，表示城市数，第二个数m表示道路数，第三个数k表示小团的旅行记录长度。

​ 每组数据接下来m行，每行两个数u,v（1<=u,v<=n, u≠v），表示u，v之间有道路连接。

​ 每组数据接下来一行，有k个数，依次表示旅行记录中的记录。

输出描述

​ 输出T行，每行输出一个字符串，YES或NO，表示这个旅行记录是可行的或者不可行的。

数据范围

其中，60%的数据保证，1<=T<=5，1<= n<=10，1<=m<=n*(n-1)/2，1<=k<=100。

100%的数据保证，1<=T<=10，1<=n<=30，1<=m<=n*(n-1)/2，1<=k<=1000。

输入样例

2

4 2 3

1 2

2 3

1 2 3

4 2 3

1 2

2 3

1 2 4

输出样例

YES

NO

样例说明

一共有两组数据。

第一个数据，1 2之间可以直达，2 3也可以直达，是可行的方案。

第二个数据，1 2 之间可以直达，但2 4 之间没有道路，无法直达。

------------------------

立方

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

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

问题描述

​ 小团正在大周游世界。她来到了立方之国，想要通过城门必须通过守卫的考验。

守卫给出了n个位置，每个位置上有一个数字，以及m个立方之碑，它可以将立方之碑放在这n个位置上，一放上去那个位置的数就会变成它原本的立方，比如，2变成8，-3变成-27。但因为位置比较小，每个位置最多放一个。守卫想知道你能否通过放置最多m个（也可以不放）立方之碑，让n个位置对应的数之和成为指定的数val。如果方案存在，请输出YES，否则输出NO。

输入描述

第一行一个整数T，表示接下来有T组数据

每组数据第一行三个整数n，m，val，分别表示位置的数量，立方之碑的数量以及指定的数。

​ 每组数据第二行n个整数，a[1],a[2],…,a[n]，表示这n个位置初始的数是多少。

输出描述

​ 输出T行，每行输出一个字符串，YES或NO，表示这个方案存在或不存在。

数据范围

其中，60%的数据保证，1<=T<=5，1<=m<=n<=10，-100<=a[i]<=100，-10,000,000 <=val<=10,000,000

100%的数据保证，1<=T<=10，1<=m<=n<=20，-1,000<=a[i]<=1,000，-10,000,000,000 <=val<=10,000,000,000

输入样例

2

2 1 10

1 2

4 3 37

1 1 2 3

输出样例

NO

YES

样例说明

一共有两组数据。

第一组，一共有2个位置，1个立方之碑，无论立方之碑放在第一个位置还是第二个位置还是不妨立方之碑，都无法满足要求，输出NO。

第二组，一共有4个位置，3个立方之碑，如果在第三个和第四个位置放置了立方之碑，这4个位置上的数就会变成1 1 8 27，它们的和是37，满足要求，输出YES。

-------------------------------------

*【技术类 第期】*

糖果

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

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

问题描述

​ 小美有很多盒子和很多糖果。她某天突发奇想玩起了套娃游戏。她将盒子放进另外的盒子里，而某些盒子里又有糖果。套到最后小美不知道每种盒子里总共含有多少糖果了，请你帮帮她。

小美将第1种盒子定义为其内只放有1颗糖果的盒子。

小美在第i(i>1) 种盒子里放了 a[i] 个 b[i] 种类的盒子。（1≤b[i]<i）

最后小美想知道每种盒子都含有多少糖果。

输入描述

​ 第一行一个整数 n，表示盒子的种类数。

​ 第二行n-1个数，第i个数为a[i+1]。

​ 第三行n-1个数，第i个数为b[i+1]。

输出描述

​ 一行输出n个数，第i个数表示第i种盒子里有多少糖果。答案对1,000,000,007取模。

输入样例

3

2 3

1 2

输出样例

1 2 6

样例说明

第1种盒子永远只有1颗糖（见上面定义）

第2种盒子有两个第1种盒子，而每个第1种盒子里有1颗糖，所以第2种盒子共有2颗糖。

第3种盒子有三个第2种盒子，而每个第2种盒子里有两个第1种盒子，因此第3种盒子共有6个第1种盒子，所以第3种盒子里共有6颗糖。

数据范围和说明

对于60%的数据，盒子的种类数n满足1<=n<=1,000，a[i] 满足 1 <= a[i] <= 1,000

对于100%的数据，盒子的种类数n满足1<=n<=100,000，a[i] 满足 1 <= a[i] <= 100,000

-------------------------------

洗牌

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

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

问题描述

​ 小美在玩扑克牌！她有n张扑克牌，每张上面都有一个数字，这n张扑克牌上面的数字分别是1,2,…,n。

现在她想对这些牌进行洗牌，洗到她觉得足够混乱为止。她觉得混乱当且仅当不存在一个i

使得第i个位置的扑克牌上的数字正好是i。

小美现在想知道一共有多少种排列，满足她认定的混乱条件。

可能数量太多啦，所以如果超过100种，她只想知道字典序最小的前100种。当然如果不到100种，就请你全部告诉她啦。

* 两种排列被认为是不同的当且仅当存在一个位置j，两种排列在位置j处为不同的数。

假设有两个不完全相同的序列a[1],a[2],…,a[n]以及b[1],b[2],…,b[n]。假设前k位均相同，即a[i]=b[i] (成立，而第k+1位不同，那么当a[k+1]<b[k+1]时我们认为a序列的字典序小于b序列的字典序。

以样例输入2为参考，可以更好的帮助理解。

输入描述

​ 第一行一个整数 n，表示扑克牌数量。

输出描述

第一行输出一个数s，表示共有s种满足小美的混乱条件的排列。

接下来若干行按字典序从小到大输出满足小美混乱条件的排列，每行一个仅由1,2,…,n组成的排列，第i个数字表示第i个位置上的扑克牌上面的数字。如果满足要求的排列数超过了100，仅输出字典序前100小的排列。

输入样例

3

输出样例

2

2 3 1

3 1 2

输入样例2

4

输出样例2

9

2 1 4 3

2 3 4 1

2 4 1 3

3 1 4 2

3 4 1 2

3 4 2 1

4 1 2 3

4 3 1 2

4 3 2 1

输入样例3

1

输出样例3

0

数据范围和说明

对于60%的数据，扑克牌的数量n满足 1<=n<=6

对于100%的数据，扑克牌的数量n满足 1<=n<=10

------------------------------------

*【技术类 四】*

序列问题

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

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

问题描述

小美有一个长度为n的序列A，她定义序列中第i个数的prev[i]值为前i-1个数中比A[i]小的最大的值，即(j<i且a[j]<a[i]中最大的a[j])，若不存在这样的数，则prev[i]的值为0。现在她想要你帮忙计算对于所有的i，prev[i]i之和是多少，即Σiprev[i]。

输入描述

第一行是一个整数n表示序列的长度。

接下来一行n个数用空格隔开，第i个数表示A[i]的大小。

输出描述

一行一个整数，表示答案。

输入样例1

5

1 6 3 3 8

输出样例1

39

数据范围和说明

30%的数据保证 n<=20，1<=A[i]<=100。

60%的数据保证 n<=1000，1<=A[i]<=1000。

100%的数据保证 n<=100000，1<=A[i]<=100000。

奇怪的键盘

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

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

问题描述

小美得到了一个奇怪的键盘，上面一共有53个按键，包括26个小写字母、26个大写字母和空格。这个键盘的奇怪之处如下：

l 当小美按下一个按键时，该按键可能会被多次触发，即输出一连串按下按键所对应的字符。

l 键盘会时不时地自动按下空格键。

在这个键盘来进行输入时，小美保证了相邻两次按下的按键一定不同以及不主动按下空格键，现在给你小美使用这个键盘输入一个字符串后得到的结果，请你还原小美原本想要输入的这个字符串。

输入描述

一行，一个包含小写字母、大写字母和空格的字符串，表示小美输入后得到的结果。

输出描述

输出一行，表示小美原本想要输入的字符串。

输入样例1

a iC C C GmyyyySp p

输出样例1

aiCGmySp

数据范围和说明

30%的数据保证 输入的字符串长度<=20

60%的数据保证 输入的字符串长度<=1000

100%的数据保证 输入的字符串长度<=100000

----------------------------------------

找数

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

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

问题描述

小美和小团在玩游戏。小美将会给出n个大小在1到n之间的整数，然后小美会再告诉小团一个整数k，小团需要找到一个最小的整数x满足以下条件：

l 整数x的大小在1到n之间

l 在小美给出的n个整数中，恰好有k个数比x小

输入描述

第一行是一个数T，表示有T组数据。

对于每组数据：

第一行有两个整数n和k，分别表示小美将会给出n个数以及她给出的整数k。

接下来一行有n个用空格隔开的正整数，表示小美给出的n个正整数。

输出描述

对于每组数据：

如果存在满足要求的数x，第一行先输出“YES”（不含引号），第二行输出数x的值。

如果不存在满足要求的数x，输出“NO”（不含引号）。

输入样例1

2

6 6

1 6 6 2 1 3

6 3

1 6 5 2 2 5

输出样例1

NO

YES

3

数据范围和说明

30%的数据保证 n<=10, 0<=k<=n, T<=10

60%的数据保证 n<=1000, 0<=k<=n, T<=10

100%的数据保证 n<=100000, 0<=k<=n, T<=10

序列问题

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

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

问题描述

小美有一个长度为n的序列A，她定义序列中第i个数的prev[i]值为前i-1个数中比A[i]小的最大的值，即(j<i且a[j]<a[i]中最大的a[j])，若不存在这样的数，则prev[i]的值为0。现在她想要你帮忙计算对于所有的i，prev[i]i之和是多少，即Σiprev[i]。

输入描述

第一行是一个整数n表示序列的长度。

接下来一行n个数用空格隔开，第i个数表示A[i]的大小。

输出描述

一行一个整数，表示答案。

输入样例1

5

1 6 3 3 8

输出样例1

39

数据范围和说明

30%的数据保证 n<=20，1<=A[i]<=100。

60%的数据保证 n<=1000，1<=A[i]<=1000。

100%的数据保证 n<=100000，1<=A[i]<=100000。