笔试做出来3道半

2025/3/9 10:00第一题 数学题 100%第二题 dp，区分反转/不反转 66%第三题 dp， 可能漏了边界条件 90%。第四题 排序+哈希，后来意识到同身高可能占多排且中间有其他身高插入的情况来不及改了。 44%

阿里云选择若干（单选，多选，分值：3 分* 15）+编程*3（分值：15，15，25），选择不是太好做。为什么要默认大家都知道你说的“排列”就是从1开始呢？如果把题目说明白一点，是怕大家都用一维dp做出来吗？不会, 暴力骗了25%；不会，暴力加贪心骗了75%；拼多多编程*4（分值：25，25，25，25）。模拟，注意负数最大输出时取绝对值；二维dp只过了66%，考虑60%的数据小于10^3， 对这部分数据暴力，其余部分沿用二维dp，最终过了80%；二维dp，dp[i][j]表示前i页书用j小时去读，最大的知识量；注意很多状态都是无用的，给定当前页数为k时，遍历时间j的时候定义时间的上界为min...

1. 贪心 100%2. 前缀和 + 数学优化 100%i 就是用反转的地方，j 就是用反转后走到的地方-preSum[i] + (preSum[j] - preSum[i]) = -2 x preSum[i] + preSum[j]也就是找两个值（0 <= i < j <= n-1），使得当走到 i 时，preSum[j] 值要取最小或者最大值这里用两个数组保存 preSum[i~n-1] 的最大和最小值，最后依次遍历，当遍历到 preSum[i] 时，取 preSumMaxPost[i+1] 或 preSumMinPost[i+1] 作为 preSum[j]，比较最大值PS：需要考虑特殊情况，就是一次反转都没用，那就直接 res = max(res, abs(preSum[i+1])); 即可3. 动态规划/记忆化搜索 100%动态规划一时紧张没写出来，转头写了记忆化搜索，搜索的条件就是当前页码、剩余分钟数4. 排序 + 贪心 100%先排序获得所有身高可选的所有座位号，然后贪心再次把每种身高的座位号按照优先前排、再优先最右侧进行排序，最后按照到场顺序，依次选择每种身高的座位号

读两个带空格的字符串按要求模拟：直接按题意模拟即可，太久没写带空格的字符串读入，cin.getline嗯调半天； 给一个二叉树，每个节点定义一个坐标值，子节点的坐标可以根据父节点的坐标算出来，每次询问一对节点的曼哈顿距离：dfs一遍后直接输出即可； 给一个数组，求：考虑的贡献，枚举，计算到里有多少个满足条件的数即可，。