3
洛谷做题笔记
source link: https://bebinca.github.io/2022/01/18/%E6%B4%9B%E8%B0%B7%E5%81%9A%E9%A2%98%E7%AC%94%E8%AE%B0/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
洛谷做题笔记
Created2022-01-18|Updated2022-01-19|Algorithm
Word count:540|Reading time:1min|Post View:29
洛谷做题的笔记，只打算给自己看所以描述语言非常简单混乱。
题单：一个动态更新的洛谷综合题单 – Studying Father’s blog
代码备份：bebinca/algorithm-practice: Part2.2开始 (github.com)
下划线代表可以再做一次，加粗是相关知识点。
- P1177 sorting 快速排序 nlogn
- mid=arr[(i+j)/2]
- 中间元素mid作为key，i++找第一个大于等于mid的，j–找第一个小于等于mid的，如果i<=j则交换，继续操作直到i>j停止，对两边做quicksort
- P1309 瑞士轮
- 赢的score+1，输的score不变，所以win和lose是两个有序数组，对其做mergesort即可，复杂度R*N
- P1908 逆序对
- mergesort求逆序对
- 树状数组【待更新
- P1024 一元三次方程组求解
- 每个解之间间隔>=1，所以[i, i+1)内最多一个解，枚举i并对每个区间内做二分求解即可
- 中间出过一次MLE，原因是对保留两位小数结果相同的判定太松了。因为四舍五入算法：正数+0.5，负数-0.5，所以判定方法是*100之后做四舍五入取int值相等。
- P2678 跳石头
- 最短距离实际上是有范围的（现在所有石头的最短距离 - 起点终点的距离），对这个范围做二分，判断是否符合最多拿m个石头的条件。
- 判断方法：如果当前距离小于枚举距离则要拿掉石头；拿掉石头数量超过m则不符合条件。
- P1902 刺杀大使
- 思路和跳石头一样，伤害值是有范围的，二分枚举判断是否符合条件
- 不同的知识点在于n*m个房间排列这种类型的bfs
- P1314 聪明的质检员
- 二分（只在现有重量范围内），前缀和
- P1083 借教室
- 差分数组，前缀和。O(n+m)就可以，有点trick，在遍历每天计算这一天符不符合要求的时候，如果不符合要求，我从后往前尝试撤回订单，这个撤回操作的代价是常数
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK