题意： 给出 $B$ 地区的村庄数 $N$，村庄编号从 $0$ 到 $N-1$，和所有 $M$ 条公路的长度，公路是双向的。并给出第 $i$ 个村庄重建完成的时间 $t_i$，你可以认为是同时开始重建并在第 $t_i$ 天重建完成，并且在当天即可通车。若 $t_i$ 为 $0$ 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 $Q$ 个询问 $(x, y, t)$，对于每个询问你要回答在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果无法找到从 $x$ 村庄到 $y$ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $x$ 或村庄 $y$ 在第 $t$ 天仍未重建完成 ，则需要返回 $-1$。

我是 FSTer，打个 div.3 居然 $B$ 题就被卡。。。为什么不先做后面的题。。。

开始复习计划~~

一些算法。

题意：某一村庄在一条路线上安装了 $n$ 盏路灯，每盏灯的功率有大有小(即同一段时间内消耗的电量有多有少)。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。现在已知老张走的速度为 $1m/s$，每个路灯的位置(是一个整数，即距路线起点的距离，单位：$m$)、功率($W$)，老张关灯所用的时间很短而可以忽略不计。请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少(灯关掉后便不再消耗电了)。

转载于 洛谷 11 月月赛 I 讲评

A. Good ol’ Numbers Coloring

题意：给你两个数 $a$ 和 $b$，现在对全体自然数进行染色处理。

染色规则如下：

1. $0$ 为白色；
2. 如果 $x\geq a$，并且 $x-a$ 是白色，那么 $x$ 是白色；
3. 如果 $x\geq b$，并且 $x-b$ 是白色，那么 $x$ 是白色；
4. 如果以上条件均不满足，那么这个数是黑色。

题意：给定两个数 $n,k$ 和两个序列 $a[],f[]$，可以有 $k$ 次操作把 $a[]$ 中一个元素减 $1$，然后把 $a[]$ 和 $f[]$ 两两配对，求乘积最大的那个数的最小值。

最大值最小，二分答案。

很明显，要让乘积尽量小，那么我们把 $a$ 数组从小到大排序，再将 $f$ 数组从大到小排序，这样能使乘积尽量平均，从而使乘积最大最小。

题意：有一个长方体的水杯，底面为一个边长为 $a$ cm 的正方形，高 $b$ cm，现在往里加入 $x$ cm$^3$ 的水，然后让水杯倾斜(只有底面一条边着地)，求能够倾斜的最大角度。

一道很有趣的思考题，要分两种情况讨论。

对于第一种情况成立的条件是 $2x\leq a ^2 b$，而第二种情况成立的情况为 $2x>a ^2 b$。(即如果两倍的水能否装满杯子为界限)。

题意：给你一个数 $m$ ($1\leq m\leq 1000000000$)，把 $m$ 分成 $ans$ 个数，且每两个大于 $1$ 的数都不相同，求出当 $ans$ 最小时，输出 $ans$ 和从小到大的 $ans$ 个数。

很明显，看到这么大的数据范围，也只有二分这种 O(logN) 的能够做到了。

题意：给一段长度为 $n$ ，每个位置上的数都不同的序列 $a[1..n]$ 和 $q$ 和问答，每个问答是 $(x, y, r)$ 代表 $RMQ(a, x, y) = r$, 要你给出最早的有矛盾的那个问答的编号。（此处 $RMQ$ 指最小值）。

要找到最早的有矛盾的那个问答，我们可以采取二分问答，每次处理 $1\sim p$ 内的问答，看看是否出现矛盾。