2023.11.15 信息学日志

2023-12-14 21:51:07

2023.11.15 信息学日志

1. CF1409E Two Platforms

题目描述

https://www.luogu.com.cn/problem/CF1409E

题目概况

来源：Codeforces

洛谷难度： 绿题 \color{green}绿题 绿题

CF难度： 1800 1800 1800

标签：二分 后缀最值

思路点拨

前期操作：

  • 显而易见纵坐标没什么用死
  • 本能将横坐标排序

题眼剖析:

  • 题目仅有 2 个板子，如果默认放好一个板子，另一个板子放在这个板子右侧的最优位置。

根据分析引入了 2 个概念：

  1. 当板子以某个点为开头所能覆盖的点数
  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

标签：贪心 枚举

思路点拨

在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_42178241/article/details/135002910
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。