【学习记录】2023年暑期ACM训练

发布时间 2023-07-19 16:26:50作者: marshuni

学习记录

集训正式开始前一天，搬东西到了机房，在我的老古董笔记本上配置好了环境。这半个月来基本没有写代码，目前非常生疏。
晚上在VJudge上拉了个热身赛，做了些简单的签到题，稍微找回了些手感。有一道计算几何的题目有思路，但是卡在了代码实现上，毕竟还没有系统学过。

主题：贪心、差分、二分、双指针、搜索
今天白天尚没有统一布置题单，所以还是自己按这个主题找一些题目来练。

Luogu P1209 修理牛棚
- 很好想思路的贪心，找出前m-1个连续的空牛棚（相连数从多到少排序），将总牛棚数减去这一部分即可。需要特别考虑左右端点处以及m多于空牛棚总数的情况。
邻项交换法

Luogu P1596 Lake Counting
- 一道简单的BFS，写这道题纯粹是为了练练手。~~以及增加一些切题的成就感。~~
Luogu P4799 世界冰球锦标赛
- 通过这道题掌握了折半搜索的思想和upper_bound()的用法。
- 虽然提交的时候T了一个点但是用O2优化过了……无事发生

Luogu P1873 砍树
- 非常经典的二分答案，实现思路很简单。然而某人到今天还是没有摸透二分怎么调试，还是用+1 -1以及随机修改各种判断条件来玄学调试……
Luogu P3853 路标设置
- 二分答案模板题，但其实好像还有别的思路也能做？总之最终写了二分。参考《算法竞赛进阶指南》上的二分章节明确了一些概念，二分终于没有出现卡死循环的状况了，可以说是一遍过。

Luogu P1102 A-B数对
- 一道普及-难度的题目，然而实操起来并没有一遍过。尽管需要用到的算法很简单，但如何设计这样的双指针还是有一定思维难度。若把双指针设计为左右端点，则会遇到一个问题：当找到一组可行的解之后，是先动左端点还是先动右端点？无疑这种思路会漏解。
- 正确的做法是枚举左端点，设置两个右端点，分别定位于可行被减数区间的左端和右端（中间的全部都是相同的数且满足要求），这样只要两指针下标相减就能得到这一左端点下的解的个数。
Luogu P8775 青蛙过河
- 这道题用二分答案和双指针都能写，然后两种方法都试了一次。在双指针部分卡了很久，最终玄学调试过关。同样这道题用双指针也是枚举左端点，然后找最小的符合条件的右端点，并在找到后更新区间长度的最大值。
- 题目本身难在思路，即发现跳跃能力 y 是合法的 ⟺ 所有长度为 y 的区间内的石头高度和 ≥2x这一规律。然后就是找区间的问题了。
- 但是双指针的写法掌握得还不够熟练，在边界的处理部分纠结了很久。
Luogu P1147 连续自然数和
- 简单题，只需要掌握双指针的思想很快就能写出来。

对顶堆基于堆的数据结构，在保留较好时间复杂度的同时，解决了朴素堆不便求第k大/小元素的问题。

Luogu P1168 中位数
- 对顶堆能解决的最经典题型。每一轮放入两个数，再维持大根堆和小根堆中元素的数目，使其始终差1即可。奇数个元素的那个堆的堆顶即中位数。
Luogu P2085 最小函数值
- 采用了部分对顶堆的思想辅助接替，维护一个“前m小的函数值”的大根堆，保证快速遍历各个可能的函数值。