2020美团实习⽣招聘笔试题
⾸先想申明⼀下，我并不是明年毕业的应届⽣，写这些笔试题是为以后⼯作做准备，所以我的代码并没有提交检测过，欢迎⼤家指点错误！题⽬为美团4⽉2号在⽜客⽹的笔试，⼀共五道题，难度挺⼤的，除了那道动态规划其他题我都没能想到完全正确的解法，后来在这⾥学习了⼀波，⼤佬的博客写的⽐较简单，我理解了很久然后全部写了⼀遍。
第⼀题不能超过
给出⼀个序列包括n个正整数的序列A，从中删除⼏个数使得序列中最⼤值减去最⼩值⼩于等于x，请问最少删除⼏个数字。
输⼊第⼀⾏为n和x，表⽰序列的长度和x，1<=n<=1000,1<=x<=10000;
第⼆⾏是n个正整数a[i]。
输出⼀个正整数，表⽰最少删除的数字数量。
样例如下：
输⼊
5 2
2 1
国庆节祝福的句子
3 2 5
输出
1
分析
这题因为n很⼩，复杂度O(n^2)是完全可以接受的，那么我们先排个序，然后遍历序列，以当前a[i]作为最⼩值，看序列中在[a[i], a[i]+x]范围内的有多少个数，⽐如说有sum个数，更新ans = min(ans, n-sum)。
评论⾥⾯很多⼈说只过了64%，可能测试数据有问题吧。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>月嫂哪家公司好
using namespace std;
int x, n;
int num[1010];
int main()
{
cin >> n >> x;
for(int i =0; i < n; i++) cin >> num[i];
sort(num, num+n);
int ans = n;
for(int i =0; i < n; i++){
侯佩岑 概览
int sum =0;
for(int j = i; j < n; j++)
if(num[j]-num[i]<= x)
sum++;
else break;
if(n - sum < ans) ans = n - sum;
}
cout << ans << endl;
return0;
}
题⽬⼆
有n个房间成环状排列，1号房间连2号，2号连三号。。。n号连着1号，在第i个房间留下⼀个烙印需要花费a[i]点法⼒，⼩明初始位于1号房间，共有m点法⼒，⼩明很耿直，他到⼀个房间如果有⾜够的法⼒留下印记他就⼀定会花费a[i]点法⼒留下印记然后到下⼀个房间，法⼒不够的话就直接去下⼀个房间，当⼩明的法⼒值⽆法在任何房间留下印记的时候游戏就结束了，那他⼀共可以留下⼏个印记。
输⼊第⼀⾏包括n 和 m，表⽰房间数和初始法⼒值，1<=n<=100000,1<=m<=10^18;
第⼆⾏有n个正整数a[i]，表⽰每个房间留下印记需要的法⼒值，
1<=a[i]<=10^9；
输出为⼀个整数，表⽰游戏结束时留下的印记数。
样例如下：
输⼊
4 21
2 1 4 3
输出
9
先把四个房间⾛⼀遍，有四个印记，剩余法⼒11，再⾛⼀遍，⼜有四个印记，剩余法⼒1，在第⼆个房间留下第九个印记，游戏结束。
分析
说实话我不是很看的懂，所以⼜去学习了⼀下，⼤概明⽩了，树状数组是⽤来存储前缀和的，原数组a[i]，前缀和数组我设为fro[i]，把⼋个数字拿来举例:
fro[1] = a[1]
fro[2] = a[1] + a[2]
fro[3] = a[3]
fro[4] = a[1] + a[2] + a[3] + a[4]
fro[5] = a[5]
fro[6] = a[5] + a[6]
fro[7] = a[7]
fro[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]
⾸先我们需要知道x&(-x)是什么，x & -x 代表⼆进制表⽰下除最右⼀位 1 保留，其它位全部为 0， 例如6&（-6） 得到 2 00000110 & 11111010 = 00000010。
我们在构造树状数组时不断进⾏x += x&(-x)，所以a[1]在fro[1]、fro[2]、fro[4]、fro[8]中都存在，a[3]除了出现在fro[3]中，还出现在fro[4]中，因为3的⼆进制是11，右边第⼀位就是1，11 + 1 = 100，⽽4的右边第⼀次出现1的位置是第三位，100 + 100 =
1000，所以fro[8]⾥也包含了a[3]。
我们获取前缀和的时候就⽤x -= x&(-x)，⽐如我现在想得到前七项的和，7的⼆进制是111，sum += fro[7]，111 - 001 = 110，sum += fro[6]，110-010=100，sum+=fro[4]，100-100=0，没得了。
那这题怎么搞呢，
太精彩了但是需要花⼀点时间理解。直接举例来说明，⽐如这个样例，现在⼀圈需要10点法⼒值，有21点法⼒值，所以可以跑两圈也就是得到⼋个印记，剩下1点法⼒值⼩于⼀圈的10点，说明从某个房间开始就已经⼤于1点了，在这个样例2 1 4 3⾥，从第⼀个房间开始就⼤于1点了，那么把第⼀个房间去掉，怎么去掉呢？⽤update(i, -a[i])就可以了，这样就能把fro⾥所有有a[i]的位置都处理⼀遍，实际的效果是相当于把a[i]置0，当然，实际的a数组并没有变动，变动的只是fro数组。那么现在fro对应的a序列就成了0 1 4 3，⼀圈下来还是⼤于1点，那么再⼀次第⼀个⼤于1的前缀，显然是第三个房间，现在a序列变成了0 1 0 3，⼀圈需要4点法⼒，还是⼤于1点，那再来⼀次，变成0 1 0 0，好了现在可以循环⼀圈了，法⼒值消耗完毕，游戏结束。第⼆种游戏结束的情况就是序列全为0了，这⾥为了⽅便获取结束条件设了⼀个res来保存还有⼏个不为0的数。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
long long m;
long long a[100010], fro[100010];//fro = Prefix sum of tree array int lowbit(int x)
{
return x&(-x);
}
void update(int pos,long long num)
{
一年级下册数学期中测试卷while(pos <= n)
{
fro[pos]+= num;
pos +=lowbit(pos);
}
}
long long get_sum(int pos)
{
long long sum =0;
while(pos >0)
{
sum += fro[pos];
pos -=lowbit(pos);
}
return sum;
}
int main()
{
cin >> n >> m;
long long sum =0;
for(int i =1; i <= n; i++){
cin >> a[i];
update(i, a[i]);
sum += a[i];
}
int res = n;
long long power = m;
long long ans =0;
while(res && power){
long long cnt = power / sum;
power %= sum;
ans += cnt * res;
int L =1, R = n;
while(L < R){
int mid =(L + R)/2;
if(get_sum(mid)> power)
R = mid;
else L = mid +1;
}
update(L,-a[L]);
res--;
sum -= a[L];
}
cout << ans << endl;
return0;
}
题⽬三
⼩仓喜欢射击，初始有N颗⼦弹，⼩仓⾃由选择k颗⼦弹进⾏射击，命中的概率为p[k]，命中的话获得a[k]的分，然后可以使⽤剩下的⼦弹继续进⾏射击，没有命中的话今天的游戏结束，⼩仓能获得的得分最⼤期望是多少。
第⼀⾏为⼀个数N，表⽰⼦弹数量。
第⼆⾏N个数p[i]，表⽰⼀次性⽤i颗⼦弹命中的概率。
第三⾏N个数a[i]，表⽰⼀次性⽤i颗⼦弹命中以后可以获得的分数。
1<=N<=5000 0 <= p[i] <= 1 0<=a[i]<=1000
输出⼀个最⾼期望得分，保留两位⼩数。
样例如下：
输⼊1
2
0.8 0.5
1 2
输出1
1.44
输⼊2
3
0.9 0.1 0.1
2 1 1
输出2
4.88
解释：样例⼀中选择⼀颗⼦弹，如果命中再继续⽤⼀颗，期望是0.8*1+0.8*0.8*1 = 1.44，如果选两颗⼦弹⼀起射出，期望是0.5*2=1，所以最⼤期望是1.44；
古典梳妆台样例⼆，如果直接⽤三颗，期望是0.1*1，如果先⽤两颗再⽤⼀颗，是0.1*1+0.1*0.9*2，如果先⽤⼀颗再⽤两颗，是0.9*2+0.9*0.1*1，⼀颗⼀颗⼜⼀颗，是0.9*2+0.9*0.9*2+0.9*0.9*0.9*2；
分析
有点被样例影响，开始我以为只能选择k颗然后⼀直⽤下去，那么直接遍历就好了，后来细读题⽬才知道是动态规划问题，现在⽤了k颗，获得的分数期望是p[k]*a[k]，那么下⼀次初始就是N-k颗，并且需要成功才能继续，那就是
dp[N] = p[k]*a[k] + p[k]*dp[N-k]，这⾥的k显然从1到N取⼀个能使dp[N]最⼤的，还是⽐较容易想到的。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N;
int a[5010];
double p[5010], dp[5010];
int main()
{
cin >> N;
for(int i =1; i <= N; i++) cin >> p[i];
for(int i =1; i <= N; i++)  cin >> a[i];
memset(dp,0,sizeof dp);
for(int i =1; i <= N; i++)
for(int j =1; j <= i; j++)
dp[i]=max(dp[i], dp[i-j]*p[j]+ a[j]*p[j]);
printf("%.2f", dp[N]);
return0;
}
题⽬四
给⼀个字符串s和⼀个正整数k，s仅包含⼩写字母，问s有多少个ABA型的⼦串，这⾥A的长度⼤于等于k，B的长度⼤于等于1。
输⼊第⼀⾏为s，第⼆⾏为k。
输出个数。
样例：
输⼊
abcabcabc
2
输出
8
解释：
abcab [1, 5]
abcabcab [1, 8]
注册个体工商户abcabcabc [1, 9]
bcabc [2, 6]
bcabcabc [2, 9]
cabca [3, 7]
abcab [4, 8]
bcabc [5, 9]
分析
乍⼀眼以为是kmp，写了⼀发然后GG，不太好搞，还是看了，然后学习了⼀下字符串哈希化，看了⼀篇写的很好的博客可是不到了，我把我的理解整理如下：
字符串哈希化就是把字符串变成⼀个整数，这样⽐较两个字符串是否相等的时候就只需要⽐较他俩对应那个整数是否相同，节约了判断的复杂度，我们当然可以把字符串所有⼦串都存进⼀个unordered_map<string, long long> ⾥，但是构造所有⼦串⼯作量太⼤，不够优雅，所以选择哈希化。⾸先需要准备⼀个p，⼀个mod，例如我现在有字符串“abcda"，那么
hash[1]=0*p +'a'-'a'=0;0对应⼦串"a"
hash[2]= hash[1]*p +'b'-'a'=1;1对应⼦串"ab"
hash[3]= p +2；对应"abc"
hash[4]= p*(p+2)+3；对应"abcd"
hash[5]= p^3+2*p^2+3*p；对应"abcda"
现在我想获取⼦串[2, 3]即"bc"的值，那就⽤hash[3]-hash[2-1]*p^(3-2+1)
⼦串[5, 5]，hash[5]-hash[4]*p^(5-5+1) = 0和字串[0, 0]相等。
理论研究我也整不太明⽩，反正p取⼀个质数，⽐如103、131、163、233等，然后因为字符串转成的数字会很⼤所以取余，mod可以选择1e9+7这样的质数，那么我们在计算hash值过程中要⾮常注意取余，我打算就⽤⼤佬的这个⽅法：
LL getHash(int l,int r){
return(has[r]-has[l-1]*bas[r-l+1]%mod+mod)%mod;
}
这⾥bas数组是预处理出来的p^(r-l+1)，因为减法有可能出现负数但是负数不能取余所以+mod。
这样将字符串进⾏哈希化以后就可以很⽅便的得知[1, k]⼦串是否等于[j, j+k]⼦串了，也就是很容易判断是否是ABA型。
那么我们遍历i和j查看是否有[i, i+k-1] = [j, j+k-1]就能知道是否是ABA型，当前的j满⾜这个等号后，还需要继续查看[i, i+k+cnt] 是否等于[j, j+k+cnt]，i+k+cnt⼩于j-1，j+k+cnt⼩于n，这样算下来我们会有[i, j+k-1]~[i, j+k+cnt]这些符合条件的⼦串。但是，这样获得的⼦串会有重复，例如：
aaaaaaaaa
当i为1， j 为5时，此时[1,2]=[5,6]，继续查看发现[1, 3]=[5, 7]此时获得的ABA⼦串是[1, 6]和[1, 7];
⽽当i为1， j为6时，此时[1,2]=[6,7]，获得的ABA⼦串是[1, 7]；
重复了！所以对于⼀个i，可⾏的ABA⼦串为[i，j+k-1]~ [i , j+k+cnt]，我们把每⼀个j对应的[j+k-1, j+k+cnt]放进vector中排序进⾏区间合并，然后计算去重后的ABA⼦串数量。
不知不觉把⾃⼰绕进去了。。。还是看代码吧。
代码