0914得物秋招笔试复盘

1.
题目大意：计算所有合法栈操作序列的总得分。一个操作序列包含n次入栈和n次出栈，出栈时的得分为当前栈深度对应的系数乘以出栈元素的值。

解题思路：
动态规划。定义状态dp(i, j)为已入栈i个元素，当前栈中有j个元素时的方案数与总得分。状态转移考虑入栈第i+1个元素或出栈一个元素两种情况，将子问题的方案数和得分进行合并计算。

2.
题目大意：给定两个数组A和B以及一个模数mod，从A和B中各选一个数a和b，求(a + b) % mod的最小值。

解题思路：
将两数组所有元素对mod取模。对其中一个数组（例如B）排序。遍历A中的每个元素a，在B中二分查找最接近mod - a的元素b。具体地，查找第一个不小于mod - a的元素，以及数组B中的最小元素，这两个是唯二的候选最优解，更新全局最小值。

3.
题目大意：
在一棵带点权的树上，寻找一条简单路径，使得路径上节点权值序列的逆序对数量最大。
解题思路：枚举所有路径。以每个节点为起点，通过深度优先搜索（DFS）遍历所有从该点出发的简单路径。在DFS过程中，使用树状数组（BIT）动态维护当前路径上各权值的出现次数，从而高效计算每增加一个节点时新增的逆序对数量，并更新全局最大值。回溯时需在树状数组中撤销修改。
#发面经攒人品##牛客AI配图神器#