玄题杂讲

wwwwwza · 2024-09-13 18:23:31 · 个人记录

题目：

oiClass #307. cats 的最小生成树

cats 有一个有 n 个点，m 个边的可能有重边的无向图。边有边权，其中第 i 条边的边权为 i。

在一次操作中，cats 会找出这个图的最小生成树，然后将图中所有属于最小生成树的边移除。cats 会不断重复以上操作直到图不连通为止。

现在，你需要告诉 cats 图中的每一条边是在第几次操作中被移除的。若一条边在操作结束时未被移除，你需要输出 -1。可以证明在以上条件下，cats 每次选择的最小生成树一定是唯一的。

注：一个有 n 个点的图的最小生成树即为这个图的所有的包含全部 n 个点和刚好 n-1 条边的连通子图中使子图所有边的边权总和最小的子图。

oiClass #P2692. 采油

一家石油公司最近在一片区域开采石油,这片区域可以看作一个二维平面，其中 x 轴平行于地面，x 坐标表示地表的水平位置，而 y 轴垂直于地面，y 坐标表示深度。

这片区域内还有 n 个石油矿，每个石油矿都可以看作一条平行于 x 轴的线段，其中石油的储量即为该线段的长度，如下图就对应着样例一的输入：

现在这家石油公司想要挖一个石油井，石油井可以看作一条与 x 轴相交的直线（如上图中蓝色虚线所示），通过挖石油井，这家石油公司能获取到所有与石油井有公共点的石油矿内的石油（端点处或者在线段内均算）。

你的任务就是替这家公司找到一个挖石油井的方案，使得其能获得最大储量的石油，为了方便，你只需要输出最大储量即可。

oiClass #1184. 城堡保卫战

小S 的城堡正在被大量的怪物袭击，小S必须组织有效的保卫战。

共有 n 个怪物正在袭击城堡，第 i 个怪物的攻击力为 a_i，防御力为 b_i。城内有 m 个怪物猎人，第 j 个怪物猎人的生命值为 h_j。

猎人可以和怪物对战，当猎人和第 i 个怪物对战时，猎人需要消耗连续的 b_i 秒时间攻击怪物，这段时间怪物也会攻击猎人，使猎人每秒初减少 a_i 的生命值。

一旦猎人的生命值小于或等于 0，猎人就会死亡，无法继续对战。若猎人未死亡，则 b_i 秒之后该怪物即被猎人消灭。

这些怪物有一个超能力：每当一个怪物被消灭后，其余的所有怪物的攻击力和防御力都会增加 d。

由于请猎人作战的费用十分昂贵，小S 打算请一个猎人消灭尽可能多的怪物。当然，小S 可以自由决定猎人以何顺序消灭哪些怪物。

小S 想知道，对于每一个 j=1,2,\dots,m，如果请第 j 个猎人，最多能消灭多少个怪物。

oiClass #P3676. 小明的树

小明有一棵以 1 为根的 n 个节点的树，树上每一个非根节点上有一盏灯，他有一个 2 \thicksim n 的排列 a_1,a_2,\dots,a_{n-1}。他还有一个计数器，初始为 0。

他会按照排列依次点亮这 n-1 盏灯，每进行一次点灯操作后，他会检查整个树是否是美丽的，如果是美丽的，计数器会加上此时点灯的节点形成的连通块的个数。