洛谷做题的笔记，只打算给自己看所以描述语言非常简单混乱。

题单：一个动态更新的洛谷综合题单 – 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，在遍历每天计算这一天符不符合要求的时候，如果不符合要求，我从后往前尝试撤回订单，这个撤回操作的代价是常数