拼多多2020实习笔试题题解
题解是交卷后做的，不保证AC。
题目1
题目描述
给出长虔都为n的两个整数数组a[n]和b[n]，特殊运算 S = a[0]*b[0] + ... + a[n-1]*b[n-1]，你可以改变a数组的顺序使得运算S得到的值最小，给出最终的最小值。
数组长度n大于50，对于每个元素X，0<=X<=100。
输入描述
输入一共三行。 第一行为n，表示两个数组的长度。 第二行包括n个数字，用空格隔开，是a数组的值。 第三行包括n个数字，用空格隔幵，是b数组的值。
输出描述
输出一行，包含一个数字，表示最小的S值。
示例1
输入
3
1 1 3
10 30 20
输出
80
题解
水题。先对数组a、b排序，一个升序遍历一个降序遍历。
代码：
n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())), reverse=True)
res = 0
for i in range(n):
res += a[i] * b[i]
print(res)
题目2
题目描述
小明给儿子小小明买了一套英文字母卡片（总共包合52张，区分大小写）,小小明把卡片丢在地上玩耍，并从中取出若干张排成一排，形成了一个卡片序列。 此时．小明需要将卡片序列中的重复字母剔除（同一个字母的大小写只保留一个）。 请问，所有可能的结果中，字母序最 小（不区分大小写）的序列的第一张卡片上是哪个字母？
输入描述
一行输入，包合一个非空字符串，表示卡片序列，长度为 N（1＜=N＜=52）。
输出描述
一行输出，包合一个字母（如果结果是大写字母，则需要转成小写）。
示例1
输入
xaBXY
输出
a
说明
剔除完后的结果为abxy
题解
这道题题意比较绕。大意就是，52个字母中的若干个组成的一个序列，对于每对重复字母（不区分大小写），都剔除其中一个，由于剔除的位置不同，处理后的序列有多种情况，从中找到字母序最小的，返回其首字母。
例如，xaBXY，其中x重复出现，剔除其中一个x，有两种情况：aBXY、xaBY，前者的字母序最小，所以返回其首字母a。 又如，bBa，有两种情况：Ba、ba，两者不区分大小写是一样的，首字母是b。 又如，cDadC，字母序最小的序列是adC，返回a。
理清楚题意后，解决起来就比较简单。考虑哪些字母可能成为序列的首字母。从左往右扫描，如果遇到只出现一次的字母，由于该字母不会被剔除，所以其后的字母将不会成为首字母，将该字母加入待选首字母并结束扫描；如果遇到出现两次的字母，若第一次遇到该字母，则将该字母加入待选并继续扫描，但若第二次遇到该字母，就需要停止扫描了，因为如果剔除前一个该字母，则当前位置的该字母将会被保留，所以其后的字母将不会成为首字母。
代码：
from collections import Counter
s = input().lower()
cnt = Counter(list(s))
rec = set()
heads = []
for c in s:
if cnt[c] == 1:
heads.append(c)
break
else:
if c in rec:
break
else:
heads.append(c)
rec.add(c)
print(min(heads))
题目3
题目描述
小镇沿街分布（可以理解为都在数轴上），有n家银行（位置以数轴的坐标表示，金额表示可以被抢走的金额），两个绑匪试图分别抢劫一个银行，为了让警方多奔波他们商定选择的两个银行距离不小于d，请问符合约定的情况下他们能抢到的总金额最大是多少？
输入描述
输入包括 n+1 行。
第一行包含两个数字n和d（1<=n<=200000，1<=d<=100000000），n表示银行的数量，d表示约定的距离。
下面n行，每一行包括两个数字a, b（1<=a,b<=100000000），分别表示坐标和金额，空格分隔。
输出描述
输出一个数字，表示可以获得的最大金额。
示例1
输入
6 3
1 1
3 5
4 8
6 4
10 3
11 2
输出
11
题解
首先，需要对银行按位置排序。对于每家银行，找到其右侧符合距离限制的金额最大值。
由于每次都需要某位置及其右侧的金额最大值，不妨先计算出来，存为后缀max数组。然后，对于每家银行，找到其右侧符合距离限制且最近的银行，取其后缀max数组的值，即右侧银行可获得的最大金额，并更新可获得的最大金额。
代码：
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, d;
cin >> n >> d;
vector<pair<int, int> > banks(n, make_pair(0, 0));
for (int i = 0; i < n; i++) {
cin >> banks[i].first >> banks[i].second;
}
sort(banks.begin(), banks.end(), [](pair<int, int> a, pair<int, int> b) {
return a.first < b.first;
});
vector<int> rmax(n, banks.back().second);
for (int i = n - 2; i >= 0; i--) {
rmax[i] = max(banks[i].second, rmax[i+1]);
}
int res = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (banks[j].first - banks[i].first >= d) {
res = max(res, banks[i].second + rmax[j]);
break;
}
}
}
cout << res << endl;
return 0;
}
题目4
题目描述
一个合法的圆括号表达式满足一下条件： 1．""空字符串被认为是合法的 2．如果字符串"X"与"Y"是合法的，则"XY"也被认为是合法的 3．如果字符串"X"是合法的，则"(X)"也是合法的 例子："", "()", "()()", "(())"这些都是合法的 现给出两个不保证合法的由圆括号组成的字符串，你需要交错这两个圆括号序列（在组成的新字符串中，每个初始字符串都保持原来的顺序）得到一个新的合法的圆括号表达式（不同的交错方式可能会得到相同的表达式，这种情况分开计数），求共有多少结果合法的交错方式（无法得到合法的圆括号表达式则输出0），输出结果模 10^9+7 的值(^符号是乘方的意思）
输入描述
输入包括两行，分别是两个只有"(和")"组成的字符串，长度小于2500
输出描述
输出为一个数字，表示合法的交错方式数量模上10^9+7的结果
示例1
输入
(()
())
输出
19
题解
好吧，不会。。。