首页 > 与众不同
开通博客写题解
头像 sunny_forever
发表于 2021-08-12 16:55:10
离散化 + dp + ST 表 参考楼上大佬的题解，总结出下面的思路 r[i]：以 i 作为左端点时，其右端点的位置. 则以 i 为起点时，目标序列的最大长度为 r[i] - i + 1 r[i] 具有非减性质，这为二分提供了前提条件 对于区间[L,R]，求其内部最长"好序列" 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 MYCui_
发表于 2020-12-22 19:11:53
题意简化： 给定一个长度为的序列，m个询问,每次询问一个区间内最长的没有重复数字的子序列,以及 <= 样例: 9 2 2 5 4 1 2 3 6 2 4 0 8 2 6 output: 6 5 思路一: 简单暴力，枚举区间内的子序列，然后O扫一遍，总的时间复杂度是O 思路二: 借助线段树， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 夏荷浅梦
发表于 2019-08-15 22:25:48
思路：这里首先定义几个数组：表示以i结尾的最长完美序列的开头位置，为以2为底i的对数，f数组为每段区间l到r之间的st数组的最大值,为上次出现的位置。然后考虑如何更新st数组，首先，明显st数组是单调递增的，也就是大于等于，其次，它肯定大于等于的上一次的出现位置。考虑L到R这段区间，以R右侧为右端点 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”