LOJ 一本通例题 题解

CSDN同步

这里是本人在 LOJ 上刷的一本通题目的综合题解,不定时更新。具体更新策略 戳这儿.

如果题目较简单,则本人会 简略地阐述思路等,然后 根据具体需要,给出伪代码,贴链接全代码,或不给代码。 注释较少或没有。

如果题目较有思维难度,则本人会 详细地讲解解题过程,然后 给出伪代码 或 帖链接全代码。 注释较少。

如果题目较有码量,则本人会 粗略地讲解策略,但侧重于讲解实现方式,给出 帖链接全代码 或 直接贴全代码。 注释较多。

如果题目既有思维难度,又有码量,则本人会 详细讲解解题过程,并讲解实现方式,给出 贴链接全代码 或直接贴全代码。 注释较多。

以上内容,特此说明。但总会阐明简要题意,分析时间复杂度等。且如果内容实在过多,会考虑分支题解。

如果本人水平能解决数据加强的情况,会竭力讲数据加强。数据加强表示本人的程序可以实现的较大水平。

LOJ #10000. 「一本通 1.1 例 1」活动安排

简要题意:给定若干 左闭右开 的区间 ([s_i , f_i )),求最多的区间数使得它们两两没有交集。

显然,用 ( ext{pair}) 数组将这些区间排序,然后用 ( exttt{last}) 记录上一次取的区间末尾(初始为 (0)).

从小到大取,如果能取,则 (ans gets ans+1),并更新 ( exttt{last}).

时间复杂度:(O(n log n)). 数据加强:(n leq 10^6). 实际得分:(100pts).

Link 代码

LOJ #10001. 「一本通 1.1 例 2」种树

简要题意:有 (h) 个要求,每个要求即 ([l,r]) 区间中种上 (e) 棵树。求满足所有条件的最少种数棵树。

显然,结构体存储要求并按结尾排序。然后,尽量多的在区间末尾种树,因为这样可以对后面的区间造成较大贡献。

时间复杂度:(O(n imes h)). 实际得分:(100pts).

Link 代码

数据加强:(n,h leq 10^6),用线段树维护种树过程,有诸多细节。

LOJ #10002. 「一本通 1.1 例 3」喷水装置

简要题意:

给定一个 (l imes w) 的草坪和 (n) 个喷头,每个喷头的圆心都在中线上,离左边 (L) 米,浇灌范围 (W) 米。求最少的喷头能浇灌整个草坪。

仍然,用 ( ext{pair<double,double>}) 存储,计算当前喷头能浇灌到的 最左位置和最右位置

然后,按照 LOJ #10000. 「一本通 1.1 例 1」活动安排 的思路解决即可。

注意判断 (-1) 的情况。

时间复杂度:(O(T imes n log n)). 实际得分:(100pts).

Link 代码

LOJ #10003. 「一本通 1.1 例 4」加工生产调度

简要题意:

(n) 个产品分别在 (A)(B) 两个车间加工,并且必须先在 (A) 车间加工后才可以到 (B) 车间加工。求加工顺序使得时间最小。

显然对于两件物品 (x,y)(min(A_x , B_y) < min(A_y , B_x))(x) 先加工,否则 (y) 先加工。

以此进行排序,然后一遍统计即可。

时间复杂度:(O(n log n)). 实际得分:(100pts).

Link 代码

数据加强:(n leq 10^6)(1 leq A_i , B_i leq 10^{12}).

原文地址:https://www.cnblogs.com/bifanwen/p/12642537.html