首页 > Closest Equals
开通博客写题解
头像 __故人__
发表于 2020-09-15 16:49:28
分析 考虑只有一个区间有一对相同的值时才有答案。所以我们可以把所以点对存下来，这样是 。考虑如果有多个相同的话，其实只需要储存相邻的两个即可，这样就只有 级别的点对了。再考虑如果有一个大区间包含了一个小区间证明，如何任何时候大区间不可能是最优解，最后做一次区间最小值就好了。 代码 #includ 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-15 17:06:56
Closest Equals 题目大意: 给你一串数,有次询问,每次求问一个区间,问在区间内最近的两个相同的数的距离是多少 分析: 第一反应就是记录一下这个值上一次出现的位置,这就可以记录一次答案了 然后可以构造出一个新的序列,因为当某两个可行的数在另外两个可行的数内时,外面的数是没有贡献的 然后就 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-15 17:24:09
分析 当我们看到区间的多次查询时，首先想到的可能就是离线了我们尝试将查询的区间右端点排序那么我们在向右移动指针时如果前边出现了这个值那么就可以将Pre[i]更改为i-Pre[i]因为我们现在还没有扩展到右边的点所以我们可以直接区间查询的最小值线段树即可因为我们需要将数值作为下标，所以需要离散化一次 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 嘻嘻嘻嘻嘻嘻嘻
发表于 2020-09-16 00:10:55
题：https://ac.nowcoder.com/acm/problem/110867题意：给定n个数序列，m个询问[l,r]问l~r中距离最短的且a[x]==ay，输出最短距离（n,m<=5e5）分析： 同一种数的话只需要和其相邻比较； 其次，思考怎么这个pair会在选定的范围内； 考虑 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 熠丶
发表于 2020-09-17 14:23:32
做法：RMQ+二分 思路： 1.我们将相同的数作为一个区间存下来，将两个的坐标分别作为区间的左右端点。再把两个端点的差放在一个数组中，然后题目可以转化为数组区间找最小值。由此可以想到RMQst表2.因为存的左右端点是有序的，在每次询问时，我们可以二分查找，找到可以得出答案的范围。 代码 #inclu 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-10-04 16:51:02
CF 522D 最多存在个数对会贡献答案 就是每个数和前面第一个和自己相同的数,把下标记作 那么想象一下,现在要统计的最短相同数对距离 我们可以直接对所有的投射到线段树上去 线段树上的下标就是,值就是 这样我们查询的最小值,查到的所有的 都属于,而由于是下标,所以也肯定满足 由于每个区间只需要的数插 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”