拼多多软开秋招笔试——算法真题

时间：2024.9

1、多多君最近在给多多字典中的单词进行排序，单词都是由大写的英文字母A。Z组成。
一般的字典是按照字典序进行排序：从左到石逐一比较两个单词中字符，遇到某一位的字符更小的单词则排在前面，例如:
A<B<BA<BAC<C。
多多君想定义一种新的比较方式来给多多字典排序：
1.包含"PDD"的单词要排在不包含"PDD"的单词的前面
2. 同为包含"PDD"的单词、以及不包含"PDD"的单词之中，则还是按照字典序小的排在前面。
多多君想知道，对于给定N个单词的多多词典，按照新的排序方式的前M个单词分别是什么。
输入描述：第一行，两个整数N和M，分别表示总的单词数，以及要进行排序的前M个单词数。(1 <= N <= 1.000, 1 <= M <≡ N）
接下来N行，每行分别表示一个单词(由大写英文字母组成，1<=单词长度<100)。
输出描述：输出M行，按照新的比较方式，按顺序每行分别输出一个单词。

输入：
3 1
ABC
APDD
PDD
输出：APDD
说明：因为APDD和PDD均包括PDD，所以这两个单词要排在ABC前面。而在都包含PDD的单词之中，APDD的字典序小于PDD，因此根据新的排序方式可得
APDD <PDD < ABC，即排在第一位的单词是:APDD

2、多多得到了一个由n个整数 a1, a2,… an 构成的数组a，这n个整数的平均值表示为k(注意k可能不是一个整数)。
多多想从数组a中删除两个数字，并使得剩下的n-2 个整数的平均值仍然等于K。
多多现在需要你帮助计算出对于数组a，有多少组数字 [ai,aj](1<=i<j<= n) 删除后剩下整数的平均值等于原数组的平均值。
输入描述：第一行包含一个整数t(1<=t<= 104)，表示有t组测试数据，每组测试数据包含两行。第一行包含一个数字n(3<=n<=2*10^5)，n表示数组中整数的个数，
接下来第二行包含n个整数a1, a2,… an，其中对于任意1<=i<=n 都有 0 <= a¡<10^9，所有测试用例中n数值的和不会超过 2*10^5。
输出描述：对于每组测试数据，分别输出一个整数：
代表有多少组数字[ai,aj](1<=i<j<=n)使得删除这两个数字后剩余n-2个整数的平均值等于原数组a中n个整数的平均值

输入：
4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7
输出：
6
0
2
3
说明：第一组测试用例中，删除任意两个数字都满足要求，共有6种组合，第二组测试用例中，没有能满足要求的组合，第三组测试用例中，删除第1个和第3个数，或者删除第4个和第5个数字，共有2种组合，第四组测试用例中，删除第1个和第7个数字，或者删除第2个和第6个数字，或者删除第3个和第5个数字，共有3种组合。

3、对于一个长度为n的整数序列 a1,a2,...a，是否存在等长的序列 b,b2.·.,bn，对于任意1≤i≤n存在1≤j,k≤n，使得ai=bj-bk
输入描述：第一行一个整数t，表示测试用例的数量。(1<t< 10)，对于每组测试用例：第一行是一个整数n，表示序列长度。(1≤n≤10)，第二行是n个整数:a1,a2,···,an，以空格隔开(-10^6 < ai<10^6)。
输出描述：对于每组测试用例，分别输出一行：如果存在满足条件的序列b1,b2,…,bn输出"yes"，否则输出"no"。

输入：
1
2
33 33
输出：
yes

输入：
3
1
-74
2
0 65
3
-81 42 29
输出：
no
yes
no

4、多多炸鸡店为了回馈老客，自动只换成一张免单敬量的汉堡积分，且每100个汉堡积分券，可以免费吃任意汉堡。免单券的有效期为3天，例如第1天获得免单券后，可以在第2、3、4天使用，到了第5天会自动过期失效，且使用免单券吃掉的汉堡不能获得汉堡积分
多多君希望你能帮助他找到一个最省钱的吃汉堡计划：未来N天每天要吃一个汉堡的情况下最少要花多少钱。
输入描述：第一行，一个整数T，表示测试用例的组数(1 <= T <= 10 )，对于每组测试用例：
第一行，1个整数N，表示未来要吃汉堡的天数。(1<= N <= 1000），接下来N行，每行一个整数Pi，表示第i天多多君要购买的汉堡价格。(1<= Pi <= 50)
输出描述：输出一行，一个整数，表示吃完所有汉堡的最小花费

输入：
1
3
50
50
40
输出：
100