很久不写题,手法生疏.. 做个简短记录吧,或是卡的比较久的题,或是手生忘记怎么写的题.
- Dynamic Median:堆
- Ultra-QuickSort:线段树+离散化/树状数组+离散化/归并
- 重要逆序对:归并/线段树+离散化/树状数组+离散化
Dynamic Median
不算困难的题目… 用对顶堆解决:建一个最大堆 max_heap
和一个最小堆 min_heap
,保持:
max_heap
的堆顶始终小于等于min_heap
的堆顶;- 两个堆的元素个数差不超过 \(1\). 事实上,保持
max_heap
元素更多,且比min_heap
多不超过 \(1\) 个元素即可.
写完之后先 TLE 一发,稍作优化之后便是 RE + WA…???经过多次修改尝试(炸OJ)之后,发现是 unsigned int
的问题…负数的情况会和 int
有所不同…
简单总结一下:priority_queue
的 size()
方法返回值是 unsigned int
,所以不要乱做减法…
贴一份 AC 代码吧…
1 |
|
Ultra-QuickSort
求逆序…数字范围很大,因此需要离散化. 因为结果可能爆 int
而 WA 很多发…(当然,也有树状数组的做法,以及归并的做法)
线段树做法
严格来说这份代码采取的思路并不能算作真正的离散化. 这里的做法是对每个 \(a_i\),把下标 \(i\) 与值 \(a_i\) 都存下来,存到 \((val,idx)\) 这样结构的二元组中,那么初始状况下,所有二元组是按照 \(idx\) 排序的,我们需要求 \(val\) 序列的逆序数. 这等价于将 \(val\) 排序后,求 \(idx\) 序列的逆序数. 而 \(idx\) 的取值范围就是 \([1,n]\),因此只需要开规模为 \(n\) 的线段树即可.
1 |
|
归并排序做法
一个很标准的用归并求逆序的做法…
1 |
|
重要逆序对
归并做法
一直不会的归并排序…学♂习一下..
1 |
|
线段树做法
夏令营和算法期末考试都写挂的题…(都写的是线段树,但甚至没有过样例Orz)一定要用线段树写过…
一开始妄想直接从 Ultra-Quicksort 的代码改,但 val 序列的重要逆序很难转换为 idx 序列的逆序(也可能是我没想到). 因此转而考虑将序列 \(a_1,\ldots,a_n\) 直接离散化,依次将其插入线段树,对每个 \(i\) 都查询比 \(2a_i\) 大的个数,并存到答案中.
但是这样会出问题:\(2a_i\) 可能超过原先 \(a\) 的取值范围,从而导致一些问题. 解决办法很简单,倒序插入,然后查询小于 \(a_i/2\) 的数即可. 随后因为 \(a_i/2\) 可能不是整数的情况费了一番功夫…然后才成功 AC…
果然是菜…
1 |
|