Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

UVA1146 Now or later

有 $n$ 架飞机需要着陆。 每架飞机都可以选择“早着陆”和“晚着陆”两种方式之一,且必须选择一种。 第 $i$ 架飞机的早着陆时间为 $E_i$,晚着陆时间为 $L_i$,不得在其他时间着陆。 你的任务是为这些飞机安排着陆方式,使得相邻两个着陆时间间隔的最小值(称为安全间隔)应尽量大。

$n \leq 2000,0 \leq t \leq 10 ^ 7$

阅读全文 »

P6397 [COI2008] GLASNICI

一条直线上有 $n$ 个信使,将他们按照从左至右的顺序以 $1$ 至 $n$ 编号。换句话说,设 $i$ 号信使的的坐标为 $d_i$,则对于 $1 \leq i \lt n$, $d_i \leq d_{i + 1}$。

信使传递一条消息的方法如下:

  • 在任意时刻(不一定是整数时刻),任一信使(无论是否已知消息)都可以自由选择向左移动或者向右移动或者原地不动。其移动的速度为每秒 $1$ 单位长度。
  • 当两个信使相距不超过一给定实数 $k$ 时,双方可以进行消息传递,也即如果两人中有一人已知该消息,则两人都知道了该消息。消息传递是瞬间发生的,不消耗时间。

现在 $1$ 号信使得到了一条消息,请求出最小的让所有信使都得到该消息的用时。

$1 \leq n \leq 10^5,0 \leq k \leq 10^6$

阅读全文 »

CF363D Renting Bikes

模拟赛补题计划 ON

有 $n$ 个学生要租车,一共有 $m$ 辆车,每辆车有一个价钱 $p_i$,每个学生有自己的钱 $b_i$,并且他们的钱只能自己用,每个人只能租一辆车。他们有 $a$ 公用的钱,求出

  1. 最多有多少个人能租到车

  2. 在保证尽量多的人租到车的前提下,每个人出的自己的钱总和最小是多少。

$n \leq 10^5$

阅读全文 »

P1772 [ZJOI2006]物流运输

物流公司要把一批货物从码头 1 运到码头 $m$。由于货物量比较大,需要 $n$ 天才能运完,共有 $m$ 个码头。

物流公司会设计一条固定的运输路线,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。

一次修改路线会带来 $k$ 的成本。因此物流公司希望能够订一个 $n$ 天的运输计划,使得总成本尽可能地小。

$n \leq 100,m \leq 20$

阅读全文 »

P2426 删数

有 $n$ 个不同的正整数数 $x_1,x_2,x_3…x_n$ 排成一排,我们可以从左边或右边去掉连续的 $i (1 \leq i \leq n)$ 个数(只能从两边删除数),剩下 $n - i$ 个数,再把剩下的数按以上操作处理,直到所有的数都被删除为止

每次操作都有一个操作价值,比如现在要删除从i位置到k位置上的所有的数。操作价值为$|x_i - x_k| * (k - i + 1)$,如果只去掉一个数,操作价值为这个数的值问如何操作可以得到最大值,求操作的最大价值。

$n \leq 100$

阅读全文 »

UVA1560 Extended Lights Out

有一个由按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。

即,如果灯原来是点亮的,就会被熄灭;如果灯原来是熄灭的,则会被点亮。在矩阵角上的按钮改变3盏灯的状态;在矩阵边上的按钮改变4盏灯的状态;其他的按钮改变5盏灯的状态。

请你写一个程序,确定需要按下哪些按钮,恰好使得所有的灯都熄灭。

根据上面的规则,我们知道

  1. 第2次按下同一个按钮时,将抵消第1次按下时所产生的结果。因此,每个按钮最多只需要按下一次

  2. 各个按钮被按下的顺序对最终的结果没有影响

  3. 对第1行中每盏点亮的灯,按下第2行对应的按钮,就可以熄灭第1行的全部灯。

如此重复下去,可以熄灭第1、2、3、4行的全部灯。同样,按下第1、2、3、4、5列的按钮,可以熄灭前5列的灯。

阅读全文 »