2023.11.15 信息学日志
1. CF1409E Two Platforms
题目描述
https://www.luogu.com.cn/problem/CF1409E
题目概况
来源：Codeforces
洛谷难度：
题眼剖析:
- 题目仅有 2 个板子，如果默认放好一个板子，另一个板子放在这个板子右侧的最优位置。
根据分析引入了 2 个概念：
- 当板子以某个点为开头所能覆盖的点数
- 在某一个点后放置板子的最优位置
顺着这条思路想处理方法：
- 定义 f [ i ] f_{[i]} f[i] 表示板的左边顶着点 i i i 的横坐标，所能覆盖的点的数量，这个可以用二分去做。（显然让板的端点顶着某题目所给点是优秀的策略）
- 这是定义 m x [ i ] mx_{[i]} mx[i] 表示 max ( f [ j ] ) ( i ≤ j ≤ n ， j ∈ Z ) \max(f_{[j]})(i\leq j\leq n，j\in \mathbb{Z}) max(f[j])(i≤j≤n，j∈Z)
稍微转一下就OK了
时间复杂度： O ( n ⋅ l o g 2 ( n ) ) \Omicron(n \cdot log_2(n)) O(n⋅log2(n))
AC。
2. CF1804D Accommodation
题目描述
https://www.luogu.com.cn/problem/CF82C
题目概况
来源：Codeforces
洛谷难度： 蓝题 \color{blue}蓝题 蓝题
CF难度： 2000 2000 2000
标签：贪心 枚举