美团4.2号笔试5道算法题个人记录(答案在评论区)

1，不能超过

时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给出一个序列包含n个正整数的序列A，你可以从中删除若干个数，使得剩下的数字中的最大值和最小值之差不超过x，请问最少删除多少个数字。
输入
输入第一行仅包含两个正整数n和x，表示给出的序列的长度和给定的正整数。(1<=n<=1000,1<=x<=10000)

接下来一行有n个正整数，即这个序列，中间用空格隔开。(1<=a_i<=10000)

输出
输出仅包含一个正整数，表示最少删除的数字的数量。

样例输入
5 2
2 1 3 2 5
样例输出
1

提示

极端情况下，当删除到仅剩1个数时，最大值和最小值的差为0，故不会出现无解的情况。
2，空间回廊
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：
有一款叫做空间回廊的游戏，游戏中有着n个房间依次相连，如图，1号房间可以走到2号房间，以此类推，n号房间可以走到1号房间。
这个游戏的最终目的是为了在这些房间中留下尽可能多的烙印，在每个房间里留下烙印所花费的法力值是不相同的，已知他共有m点法力值，这些法力是不可恢复的。

小明刚接触这款游戏，所以只会耿直的玩，所以他的每一个行动都是可以预料的：

一开始小明位于1号房间。

如果他剩余的法力能在当前的房间中留下一个烙印，那么他就会毫不犹豫的花费法力值。

无论是否留下了烙印，下一个时刻他都会进入下一个房间，如果当前位于i房间，则会进入i+1房间，如果在n号房间则会进入1号房间。

当重复经过某一个房间时，可以再次留下烙印。

很显然，这个游戏是会终止的，即剩余的法力值不能在任何房间留下烙印的时候，游戏终止。请问他共能留下多少个烙印。

输入
输入第一行有两个正整数n和m，分别代表房间数量和小明拥有的法力值。(1<=n<=100000,1<=m<=10^18)

输入第二行有n个正整数，分别代表1~n号房间留下烙印的法力值花费。(1<=a_i<=10^9)

输出
输出仅包含一个整数，即最多能留下的烙印。

样例输入
4 21
2 1 4 3
样例输出
9

提示
样例解释：
显然是所有房间都留下两个烙印，然后剩下1点法力值，仅能在2号房间再留下一个烙印.

3，小仓的射击练习4（DP？）
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
小仓酷爱射击运动。今天的小仓想挑战自我。小仓有N颗子弹，接下来小仓每次会自由选择K颗子弹进行连续射击，全中靶心的概率为p[k]。如果成功小仓将获得a[k]的得分，并且可以使用余下子弹继续射击，否则今天的挑战结束。小仓想知道在最佳策略下，自己能得到的最高期望分数是多少。

输入
第一行一个数N，代表子弹数量。

第二行N个数p[]，第 i 个数代表p[i]。

第三行N个数a[]，第 i 个数代表a[i]。

1<=N<=5000 0<=p[i]<=1 0<=a[i]<=1000

输出
一个数表示最高期望得分，保留两位小数。

样例输入
2
0.80 0.50
1 2
样例输出
1.44

提示
样例1解释
选择用一颗子弹射击：如果命中则再用余下子弹射击（仅剩一颗子弹故只能选择一颗）：0.80 * 1 + 0.80 * 0.80 * 1= 1.44
选择用两颗子弹射击：0.5 * 2 = 1.00
此时最高期望得分为1.44

输入样例2
3
0.90 0.10 0.10
2 1 1
输出样例2
4.88

选择用一颗子弹射击：如果命中则再用一颗子弹进行射击，如果命中则再用一颗子弹进行射击（即3轮均使用了一颗子弹进行）：0.90 * 2 + 0.90 * 0.90 * 2+0.90 * 0.90 * 0.90 * 2= 4.878≈4.88 此种情况的期望得分最高，故为4.88

4，拆分
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给定长度为n的串S，仅包含小写字母。定义

公式中，|A|代表字符串A的长度

也就是说如果子串是一个ABA型的字符串，且满足长度限制，则f(l,r)=1，否则等于0。（注意：形如“ababab”也可视为ABA型）

例如当n=2时，原式为f(1,1)+f(1,2)+f(2,2)。

输入
第一行一个字符串S

第二行一个数字k

输出
输出题目描述中式子的值

样例输入
abcabcabc
2
样例输出
8

提示
1<=n<=2000 , S[i]为小写字母

样例解释：
在这个字符串中，有f(1,5),f(1,8),f(1,9),f(2,6),f(2,9),f(3,7),f(4,8),f(5,9)的值为1，其他为0，故和为8。以f(1,5)为例，选择的子串是abcab，令A=“ab”，B=“c”,则|A|>=k且|B|>=1,因此f(1,5)等于1，以此类推。

5，max xor min（单调栈？）
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给你一个长度为n的序列a，请你求出对每一个1<=l<r<=n的区间中最大值和最小值的异或和的异或和。

例如序列为{1,3,5},不同的a(1,2)=1^3,a(1,3)=1^5,a(2,3)=(3^5),a(1,2)^a(1,3)^a(2,3)=0，所以最后的答案是0。

输入
输入第一行仅包含一个正整数n，表示序列的长度。(1<=n<=10^5)

接下来一行有n个正整数a_i，表示序列a。(1<=a_i<=10^9)

输出
输出仅包含一个整数表示所求的答案。

样例输入
3
1 3 5
样例输出
0