拼多多2020秋招笔试真题

1、多多的魔术盒子

【题目描述】有N个魔术盒子（编号1～N），其中编号为i的盒子里有i个球

每次选择一个数字X（1<=X<=N），把球数量大于等于X个的盒子里的球减少X个

求最少的次数将所有盒子里的球减少为空

【解题思路】

从题意中易分析得，目标的次数随着N的增长为单调不降函数

设N的最少操作次数为K，N / 2需要的次数为K - 1；即可以通过选择X = N / 2， 将原问题变成N / 2的子问题

而对于N=1的边界情况，需要K=1次操作，因此可以得到通项公式： Log(N) / Log(2) + 1

时间复杂度: O(1)

空间复杂度: O(1)

另外还可以采取其他递推，递归，动态规划的方法均可，可以得到同样的结果

考虑知识点：

递推，递归，动态规划，实现

【参考代码】

#include <iostream>
#include <cmath>
  
using namespace std;
  
int main()
{
  int T, n;
  cin >> T;
  while (T--) {
    cin >> n;
    printf("%d\n", (int)(log(n) / log(2)) + 1);
  }
  return 0;
}

2、多多的排列函数

【题目描述】给出一个N的全排列数组{A_i}，定义函数F

F(1)=A₁

F(i)=|F(i-1)-A_i|,(i>1)

对于100%的数据：1<=N<=100,000

求在所有可能的数列{A_n} 中，F(N)的最小值和最大值分别是多少？

【解题思路】

数排列的数组：

将数字从大到小排列，两两相减取绝对值即可；另外还可以通过找规律分析，最小值只有0和1两种可能，周期为4。

对于最大值，N减去F(N-1)的最小值即可。

时间复杂度: O(N)

空间复杂度: O(N)

【参考代码】

#include <iostream>
 
using namespace std;
 
int a0[100010], a1[100010];
int b0[100010], b1[100010];
 
int main()
{
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
 
    int c0, c1;
    for (int i = 1; i <= N; i++) a0[i] = N - i + 1;
    for (int i = 1; i <  N; i++) a1[i] = N - i; a1[N] = N;
 
    b0[1] = a0[1];
    for (int i = 2; i <= N; i++) b0[i] = abs(b0[i - 1] - a0[i]);
 
    b1[1] = a1[1];
    for (int i = 2; i <= N; i++) b1[i] = abs(b1[i - 1] - a1[i]);
 
    cout << b0[N] << " " << b1[N] << endl;
  }
 
  return 0;
}

3、多多的电子字典

【题目描述】有一个只由单词a和b组成的词典。每个单词，a的数量不超过N，b的数量不超过M。求字典序中第K小的单词

· 对于40%的数据：0<K<100,000

· 对于100%的数据：0<N, M<50, 0<K<1,000,000,000,000,000

【解题思路】

对于40%的数据，可以通过枚举a和b加上排序比较的方法可以暴力求出

时间复杂度：O(K)

空间复杂度：O(K)

而对于100%的数据：

第一步，求N个a和M个b可以组成多少个不同的单词，可以使用动态规划计数 （也可以用其他公式计数）

F[i][j] 表示使用i个a和j个b时，可以组成的单词个数

转移方程： 

最后一位填了'a': F[i + 1][j] += F[i][j]

最后一位填了'b': F[i][j + 1] += F[i][j]

初始条件：

F[0][0] = 1

第二步，从高位开始枚举，当前最高为‘a’，那么剩余N - 1个a可选和M个b可选

可以有sum = Σ(f[i][j]) （其中 0 <= i <= N - 1, 0