 |
|
发布时间：2025-09-20 19:37:29
| 8.31小红书笔试（带答案） 8.31小红书笔试（带答案）\n解题思路：\n一、每日一题：快速计算非包裹子串\n面对 “统计每个前缀的非包裹子串数量” 问题，核心是 “总子串数减包裹子串数” 的反向思维。首先，长度为 i 的前缀总子串数是 i*(i+1)/2，可通过遍历实时累加（每次加当前前缀长度）。而包裹子串（首尾字符相同）的数量，只需用数组记录每个字符的出现频率 —— 若某字符已出现 f 次，新增该字符时会新增 f+1 个包裹子串（含自身构成的单字符子串）。最后用总子串数减去包裹子串数，即可高效得到每个前缀的答案，全程线性时间复杂度，轻松应对大字符串输入。\n \n二、品牌创意工坊：带约束的切割方案计数\n丝带切割需规避 “a 段后接 c 段” 的约束，用动态规划可精准解决。定义 dp [k] 为长度 k 的合法方案数，额外维护 endA [k] 记录 “长度 k 且最后一段为 a” 的方案数（因约束仅与 a 段后接 c 段相关）。递推时，以 a、b 结尾的方案可直接累加对应前序长度的 dp 值；以 c 结尾的方案需从对应前序长度的 dp 值中，扣除 “最后一段为 a” 的方案数（即 endA 值）。通过空方案（dp [0]=1）作为基底，逐长度递推，既能保证顺序不同算不同方案，又能高效处理约束，轻松应对多组测试数据。\n \n三、轰炸机：树上最大花费的策略选择\n这道题本质是 “选最优轰炸方式” 的树问题，核心分两种情况决策：若单炸城市（操作 1）比炸连通块（操作 2）贵，直接全用操作 1，总花费为 n*x；若操作 2 更贵，需最大化操作 2 的使用次数 —— 而操作 2 仅对独立连通块有效，因此要先求树的最大独立集（任意两节点无直接边的最大节点集合）。用树形 DP 计算最大独立集（dp0 [u] 表不选 u 的子树最大独立集，dp1 [u] 表选 u 的子树最大独立集），最终总花费为 “所有城市按操作 1 算的基础花费 + 最大独立集节点换用操作 2 的差价”，既保证全覆盖，又实现花费最大化。\n#大厂校招 #秋招信息差#秋招 #秋招笔试 #小红书 #小红书校招 #小红书秋招 #小红书笔试 #笔试#大厂秋招 |
