拼多多笔试

1、给定n个关卡，每个关卡要么有boss要么有商人，总共有m种宝石。玩家手里最多只能拿一块宝石。n和m在1e6量级。
boss关输入类似“b 5”，表示打完boss会掉落第5种宝石。
商人关输入类似“m 6 20”，表示商人会以20元的价格收第6种宝石。每位商人只收一种宝石。
问闯完n关后，玩家最多挣多少钱？
样例：
6 2
b 1
b 2
m 2 20
b 2
m 2 20
m 1 30
输出40，表示买卖两次2号宝石，挣40块。

2、给定一棵树，树根为1，每条边有一个权重0或1，表示道路通或不通。
要求从根节点派出施工队修复所有道路，施工队不会走回头路，问最少派出多少施工队？
样例：
4
1 2 1
2 3 0
2 4 1
输出：1，表示派出一支施工队从1到2到4，即可修复12和24这两条损坏的道路。

3、给定数组a，只可能包含-8、-4、-2、-1、0、1、2、4、8。问最大子数组积为多少？空数组当做1。
如果没有≥1的子数组，输出-1；否则，输出子数组的左右端点（0-indexed），乘积相同的子数组，选取规则按：子数组长度越长越好、子数组越靠右越好。
样例：
4
2 0 -2 8 -1
输出：2 4，表示选取-2 8 1这一段，乘积为16。

4、输入多组样例，每组给定一个只包含正数的数组a，任意一次操作可以选取一个x，把a中的所有x都变为0。
问最少多少次操作可以把a变成“非递减数组”？
非递减数组表示a中任意1≤i<n均有a[i]≥a[i-1]。
样例：
5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1
输出：
1
2
4
3
0

#春招#  #笔试#