【题解】牛客网NOIP赛前集训营-提高组（第四场）
A. 动态点分治
B. 区间
• 求出现在 𝑙,𝑟 内的形如 
的数
• 模拟题意就好了，注意一下 𝑘 = 1 或 𝑘 = 0 的边界 • 吗？
• 坑点：有可能
，但是 𝑘𝑥 溢出了，溢出之后刚好又在 𝑙,𝑟 甚至 𝑥,𝑟 之间
• 模拟题意就好了，注意一下 𝑘 = 1 或 𝑘 = 0 的边界 • 吗？
• 坑点：有可能
• 应对措施：如果
，则 break
B. 区间
• 找一个最长的区间，使得区间里存在一个数是区间里每个数的因数
• 三方四方暴力不讲了
• 三方四方暴力不讲了
• 平方暴力：枚举 𝑖，往两边扩展到不能扩展为止（60pts）
• 注意到：如果 𝑖 的区间扩展到了 𝑗，那么 𝑗 的区间一定是 𝑖 的区间的子区间（因为 𝑗 是 𝑖 的一个倍数），从而不可能更新答案
• 注意到：如果 𝑖 的区间扩展到了 𝑗，那么 𝑗 的区间一定是 𝑖 的区间的子区间（因为 𝑗 是 𝑖 的一个倍数），从而不可能更新答案
• 我们可以考虑按一个顺序枚举 𝑖，每次只要一个点被区间经过，就可以不用扩展它的区间
• 按 𝑎𝑖 从小到大的顺序扩展 𝑖，这样每一个数最多被扩展过两次（从左和从右分别一次）
• 时间复杂度为排序复杂度 𝑂 (𝑛log𝑛)
• 还能更快吗？
• 还能更快吗？
• 考虑点 𝑖 扩展出的区间的左右端点 
,
• 不一定单调不降，但如果 
，那么就说明 𝑖 会被 𝑖 − 1 的区间扩展到，从而不可能更新答案
• 这种情况我们不妨就令 
，因为即使这样 也不可能更新答案，但这样 就单调了
• 用单调性线性求出 和 ，用每个 𝑖 更新答案即可
• 时间复杂度 𝑂 (𝑛)
C. 灭虫
• 在这种前提下，甚至按顺序选择区间的顺序都难以决定 
• 对于这种情况，可以假设上面这条线画到了第二条的开头处，这样在后一条线的转移时即可处理 
• 在枚举起点（𝒑𝒊）靠右的点（也就是下面这个）上考虑这种情况 
• 设下面的区间是 𝑖，上面的区间是 𝑗，我们可以得到
这样一个区间
• 你需要从每一对 𝑙𝑖,𝑝𝑖 和 𝑝𝑖,𝑟𝑖 中选一个区间，使得选出的区间并的长度最大（变量名称修改了）
• 这题看起来就非常复杂，因为区间可能会出现很鬼畜的相交
• 这题看起来就非常复杂，因为区间可能会出现很鬼畜的相交
• 在这种前提下，甚至按顺序选择区间的顺序都难以决定
• 兵来将挡，我们必须直接面对这种情况
• 先大概确认一下思路
• 先大概确认一下思路
• 对于这种情况，可以假设上面这条线画到了第二条的开头处，这样在后一条线的转移时即可处理
• 同理，对称的往左的情况，我们既可以这样假设，也可以换一种方式假设
• 对于这种情况
• 在枚举起点（𝒑𝒊）靠右的点（也就是下面这个）上考虑这种情况
• 相当于插入了这样的一个区间
• 同理为了解决上一页所描述的区间的问题，我们也需要做一些相应的操作
• 现在可以考虑定义 DP 状态了
• 现在可以考虑定义 DP 状态了
• 按照 𝒑𝒊 从小到大的顺序放置每个区间
• 记录 𝑓 𝑖,𝑗 表示决定了前 𝑖 个区间，且已知覆盖的最右点是 𝑗 时的最大覆盖量
• 那么我们就可以用这样两种假设（即每一个区间可以只算一个前缀）的思想来转移了
• 对于鬼畜情况
• 设下面的区间是 𝑖，上面的区间是 𝑗，我们可以得到
• 考虑完所有 𝑗 后，这样的区间会有)
个，它们具有相同的左端点和不同的右端点
• 然后枚举每个位置 𝑘 ，用包含它的区间更新其 DP 值，这个可以用一个后缀 max 来实现（下标是右端点），也可以用堆这样的数据结构来暴力维护
• 时间复杂度 )
或 )
std
华为工作强度 834人发布
投递百度等公司10个岗位 >
查看18道真题和解析