2023 夏季集训 D1 贪心二分
0x00 前言
24OI FXJ 大佬来给我们讲课 Orz Orz.
讲课好难 TAT.
0x10 贪心
0x11 经典贪心
写了 Best Cow Line G/S 和 田忌赛马
一位小伙从同学那里要来了一份 Best Cow 代码 Debug 但没有发现代码没有输入, 这是他思路 3 小时后发生的 hack.
田忌赛马太水了, \(O(n^2)\) 就能过.
0x12 邻项交换
邻项交换问题主要表现为 「排序一个序列, 使其想的某些特点极端化」.
都是大式子题.
显而易见排序只需要知道交换两个相邻项是否不劣.
排序的 cmp 函数可以推式子.
一个特殊问题: 为什么退完的式子一定是合法的 cmp ?
考虑 cmp 3大性质.
- cmp 会得出 \(a=a\) 的结论
- cmp 中 若 \(a < b, b < c\) 则 \(a < c\)
- cmp 中 若 \(a = b, b = c\) 则 \(a = c\)
这在 国王游戏 中体现不明显, 但在 王后游戏 中体现很明显.
具体内容可参见王后题解区, 大佬们讲的非常好
0x13 反悔贪心
理解反悔两字之前先回顾一下贪心的特点.
- 使用已有的 局部最优解 推导全局最优解.
- 其中已选择的内容不会被踢出去.
而反悔就是针对第二部分.
若新的最优解需要踢掉原有的内容就可以自由踢掉, 并且踢掉的元素不会回归, 这就是反悔的内涵.
P.S. 种树 无论如何两个坑相离直接踢掉中间所有的坑(适用于所有两种情况), 可用反证法证明
0x20 二分
「Stop learning useless algorithms, go and solve some problems, learn how to use binary search.」
由于 YXL 老师已经详细讲过, 这里直接贴例题.
秦腾与教学评估, Sereja and Prefixes(on CF380A), Telephone Lines S, Save the nature(on CF1223C), Balance Beam(on AT_agc040_d, 极难)
0x21 三分
教练说 D2 会出题, 加急讲的
求单峰函数的顶点.