改进思路因为题目中说图中没有环因此我们可以通过 DP 解决此题所以我们就可以通过记忆化递归防止进行无效的 dfs 。AC代码点开有惊喜2. 鬼子进村赛时思路本题有 3 个最本质的操作单点修改和查询加区间查询因此我考虑使用线段树解决此题。单点修改和查询比较简单只需遍历到叶子节点修改或查询其信息因此区间查询便十分重要以至于此题没有做出来 QwQ 。改进思路略微借鉴本题题解便会发现我们只需找出此节点右边第一个被摧毁房子的位置 和左边第一个被摧毁房子的位置 而士兵可移动的距离则是 。那如何判断此区间是否存在 或 我们只需要统计区间长度 以及区间未被摧毁房子的个数 , 看 是否比 小如果是则此区间存在 或 的位置相应的如果都没有被摧毁的房子则返回 -1 或 1 。注意在寻找 和 之前要先判断这个房子是否被摧毁否则答案会出错在进行修改之前需要进行建树统计每个节点的 , 并将所有 赋值为 1 方便后面进行修改以及查询AC代码点开有惊喜3. Radio Transmission 无线传输赛时思路题目中字符串 是由某个子串 重复至少 2 次形成的。我们需要找到 的最短长度本质是寻找 中能构成其重复结构的最小单元长度。因此我便认为此题所用到的算法应包括 KMP 可惜后来没时间继续想了 QwQ 。改进思路问题的本质确实已经被我想到了可还有几点不全在 KMP 中我们常定义 nex[x] 表示最长前缀及后缀的子串长度。答案推导若字符串 是由子串 重复 次构成 则总长度 本质是 重复 次的长度即 两式相减得 即最短重复子串 的长度。AC代码点开有惊喜4.木棍分割前言没有赛时思路,考场上甚至没有来得及看此题 QwQ 。思路本题主要由两个问题组成最长段的最小长度和组成此长度的方案数量而且前者答案还为后者的限定条件的这么一个问题当我们找到问题的根本后就要去思考解决此类问题的算法有哪些因此我们确定了此题我们的算法二分加 DP 最长的最短肯定可以直接想到二分而方案数量则一般用 DP 解决。问题一二分因为最长的最短长度具有单调性当长度 可以则 ~ 之间的答案也都能成立所以我们可以二分长度而 check 函数也比较简单能不分割就不分割看最后分割次数是否大于 即可。注意的初始值为 a[i] 的最大值而 的值则为 a[i]这样可以防止一些没用的判断降低点时间复杂度毕竟这题卡常。时间复杂度其中S是所有木棍的总长度问题二DP状态申明前i根木棍分割成若干段每段长度不超过 ans 的方案数状态转移方程其中j满足即所有满足最后一段长度不超过ans的j的位置前缀和优化计算前缀和数组 其中则 其中 是满足 的最小滑动窗口确定使用双指针维护 的位置避免重复计算遍历顺序外层循环遍历段数 从 到 需要计算不同段数下的方案数并累加得到总方案数内层循环遍历前 根木棍从 到 按顺序计算每个状态 确保在计算 时所有依赖的状态 已经计算完成边界条件表示空分割方案数为当 时 表示前 根木棍的分割方案数为最终答案